Java提高篇——通过分析 JDK 源代码研究 Hash 存储机制

HashMap 和 HashSet 是 Java Collection Framework 的两个重要成员，其中 HashMap 是 Map 接口的常用实现类，HashSet 是 Set 接口的常用实现类。虽然 HashMap 和 HashSet 实现的接口规范不同，但它们底层的 Hash 存储机制完全一样，甚至 HashSet 本身就采用 HashMap 来实现的。

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

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

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

集合和引用

就像引用类型的数组一样，当我们把 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) 方法的源代码：

(ps:JDK 源码

在 JDK 安装目录下可以找到一个 src.zip 压缩文件，该文件里包含了 Java 基础类库的所有源文件。只要读者有学习兴趣，随时可以打开这份压缩文件来阅读 Java 类库的源代码，这对提高读者的编程能力是非常有帮助的。需要指出的是：src.zip 中包含的源代码并没有包含像上文中的中文注释，这些注释是笔者自己添加进去的。)

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; }

原标题：Java提高篇——通过分析 JDK 源代码研究 Hash 存储机制

关键词：JAVA