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

程序①号代码处可以看到：table 的实质就是一个数组，一个长度为 capacity 的数组。

对于 HashMap 及其子类而言，它们采用 Hash 算法来决定集合中元素的存储 位置。当系统开始初始化 HashMap 时，系统会创建一个长度为 capacity 的 Entry 数组，这个数组里可以存储元素的位置被称为“桶（bucket）”，每个 bucket 都有其指定索引，系统可以根据其索引快速访问该 bucket 里存储的元 素。

无论何时，HashMap 的每个“桶”只存储一个元素（也就是一个 Entry）， 由于 Entry 对象可以包含一个引用变量（就是 Entry 构造器的的最后一个参数 ）用于指向下一个 Entry，因此可能出现的情况是：HashMap 的 bucket 中只有 一个 Entry，但这个 Entry 指向另一个 Entry ——这就形成了一个 Entry 链 。如图 1 所示：

图 1. HashMap 的存储示意

height=240 src="http://img.ddvip.com/2009_11_28/1259370937_ddvip_330.jpeg" width=486>

HashMap 的读取实现

当 HashMap 的每个 bucket 里存储的 Entry 只是单个 Entry ——也就是没 有通过指针产生 Entry 链时，此时的 HashMap 具有最好的性能：当程序通过 key 取出对应 value 时，系统只要先计算出该 key 的 hashCode() 返回值，在 根据该 hashCode 返回值找出该 key 在 table 数组中的索引，然后取出该索引 处的 Entry，最后返回该 key 对应的 value 即可。看 HashMap 类的 get(K key) 方法代码：

public　V　get(Object　key) 　 { 　 //　如果　key　是　null，调用　getForNullKey　取出对应的　 value 　 if　(key　==　null) 　　 return　getForNullKey(); 　 //　根据该　key　的　hashCode　值计算它的　hash　码 　 int　hash　=　hash(key.hashCode()); 　 //　直接取出　table　数组中指定索引处的值， 　 for　(Entry<K,V>　e　=　table[indexFor(hash,　 table.length)]; 　　 e　!=　null; 　　 //　搜索该　Entry　链的下一个　Entr 　　 e　=　e.next)　　//　① 　 { 　　 Object　k; 　　 //　如果该　Entry　的　key　与被搜索　key　相同 　　 if　(e.hash　==　hash　&&　((k　=　e.key)　==　key 　　 ||　key.equals(k))) 　　 return　e.value; 　 } 　 return　null; 　 }

从上面代码中可以看出，如果 HashMap 的每个 bucket 里只有一个 Entry 时，HashMap 可以根据索引、快速地取出该 bucket 里的 Entry；在发生“Hash 冲突”的情况下，单个 bucket 里存储的不是一个 Entry，而是一个 Entry 链 ，系统只能必须按顺序遍历每个 Entry，直到找到想搜索的 Entry 为止——如 果恰好要搜索的 Entry 位于该 Entry 链的最末端（该 Entry 是最早放入该 bucket 中），那系统必须循环到最后才能找到该元素。

归纳起来简单地说，HashMap 在底层将 key-value 当成一个整体进行处理， 这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所 有的 key-value 对，当需要存储一个 Entry 对象时，会根据 Hash 算法来决定 其存储位置；当需要取出一个 Entry 时，也会根据 Hash 算法找到其存储位置 ，直接取出该 Entry。由此可见：HashMap 之所以能快速存、取它所包含的 Entry，完全类似于现实生活中母亲从小教我们的：不同的东西要放在不同的位 置，需要时才能快速找到它。

当创建 HashMap 时，有一个默认的负载因子（load factor），其默认值为 0.75，这是时间和空间成本上一种折衷：增大负载因子可以减

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