快速业务通道

通过分析JDK源代码研究Hash存储机制 - 编程入门网

作者 佚名技术 来源 NET编程 浏览 发布时间 2012-06-23

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

时间:2010-12-08 IBM 李刚

通过 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)

时间:2010-12-08 IBM 李刚

JDK 源码

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

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

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

分享到: 更多

Copyright ©1999-2011 厦门凌众科技有限公司 厦门优通互联科技开发有限公司 All rights reserved

地址(ADD):厦门软件园二期望海路63号701E(东南融通旁) 邮编(ZIP):361008

电话:0592-5908028 传真:0592-5908039 咨询信箱:web@lingzhong.cn 咨询OICQ:173723134

《中华人民共和国增值电信业务经营许可证》闽B2-20100024  ICP备案:闽ICP备05037997号