通过分析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; 　 }

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

JDK 源码

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

上面程序中用到了一个重要的内部接口：Map.Entry，每个 Map.Entry 其实 就是一个

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!