通过分析JDK源代码研究Hash存储机制

通过 HashMap、HashSet 的源代码分析其 Hash 存储机制

集合和引用

就像引用类型的数组一样，当我们把 Java 对象放入数组之时，并不是真正 的把 Java 对象放入数组中，只是把对象的引用放入数组中，每个数组元素都是 一个引用变量。

实际上，HashSet 和 HashMap 之间有很多相似之处，对于 HashSet 而言， 系统采用 Hash 算法决定集合元素的存储位置，这样可以保证能快速存、取集合 元素；对于 HashMap 而言，系统 key-value 当成一个整体进行处理，系统总是 根据 Hash 算法来计算 key-value 的存储位置，这样可以保证能快速存、取 Map 的 key-value 对。

在介绍集合存储之前需要指出一点：虽然集合号称存储的是 Java 对象，但 实际上并不会真正将 Java 对象放入 Set 集合中，只是在 Set 集合中保留这些 对象的引用而言。也就是说：Java 集合实际上是多个引用变量所组成的集合， 这些引用变量指向实际的 Java 对象。

HashMap 的存储实现

当程序试图将多个 key-value 放入 HashMap 中时，以如下代码片段为例：

HashMap<String　,　Double>　map　=　new　 HashMap<String　,　Double>();
map.put("语文"　,　80.0);
map.put("数学"　,　89.0);
map.put("英语"　,　78.2);

HashMap 采用一种所谓的“Hash 算法”来决定每个元素的存储位置。

当程序执行 map.put("语文" , 80.0); 时，系统将调用"语文"的 hashCode () 方法得到其 hashCode 值——每个 Java 对象都有 hashCode() 方法，都可 通过该方法获得它的 hashCode 值。得到这个对象的 hashCode 值之后，系统会 根据该 hashCode 值来决定该元素的存储位置。

我们可以看 HashMap 类的 put(K key , V value) 方法的源代码：

public　V　put(K　key,　V　value)
{
//　如果　key　为　null，调用　putForNullKey　方法进行处理
if　(key　==　null)
return　putForNullKey(value);
//　根据　key　的　keyCode　计算　Hash　值
int　hash　=　hash(key.hashCode());
//　搜索指定　hash　值在对应　table　中的索引　
int　i　=　indexFor(hash,　table.length);
//　如果　i　索引处的　Entry　不为　null，通过循环不断遍历　e　元 素的下一个元素
for　(Entry<K,V>　e　=　table[i];　e　!=　null;　e　=　 e.next)
{
Object　k;
//　找到指定　key　与需要放入的　key　相等（hash　值相同
//　通过　equals　比较放回　true）
if　(e.hash　==　hash　&&　((k　=　e.key)　==　key
||　key.equals(k)))
{
V　oldValue　=　e.value;
e.value　=　value;
e.recordAccess(this);
return　oldValue;
}
}
//　如果　i　索引处的　Entry　为　null，表明此处还没有　Entry
modCount++;
//　将　key、value　添加到　i　索引处
addEntry(hash,　key,　value,　i);
return　null;
}