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

上面方法提供了一个根据 hashCode() 返回值来计算 Hash 码的方法：hash ()，这个方法是一个纯粹的数学计算，其方法如下：

static　int　hash(int　h) { 　　 h　^=　(h　>>>　20)　^　(h　>>>　12); 　　 return　h　^　(h　>>>　7)　^　(h　>>>　 4); }

对于任意给定的对象，只要它的 hashCode() 返回值相同，那么程序调用 hash(int h) 方法所计算得到的 Hash 码值总是相同的。接下来程序会调用 indexFor(int h, int length) 方法来计算该对象应该保存在 table 数组的哪 个索引处。indexFor(int h, int length) 方法的代码如下：

static　int　indexFor(int　h,　int　length) { 　　 return　h　&　(length-1); }

这个方法非常巧妙，它总是通过 h &(table.length -1) 来得到该对象 的保存位置——而 HashMap 底层数组的长度总是 2 的 n 次方，这一点可参看 后面关于 HashMap 构造器的介绍。

当 length 总是 2 的倍数时，h & (length-1)将是一个非常巧妙的设计 ：假设 h=5,length=16, 那么 h & length - 1 将得到 5；如果 h=6,length=16, 那么 h & length - 1 将得到 6 ……如果 h=15,length=16, 那么 h & length - 1 将得到 15；但是当 h=16 时 , length=16 时，那么 h & length - 1 将得到 0 了；当 h=17 时 , length=16 时，那么 h & length - 1 将得到 1 了……这样保证计算得到 的索引值总是位于 table 数组的索引之内。

根据上面 put 方法的源代码可以看出，当程序试图将一个 key-value 对放 入 HashMap 中时，程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置：如果两个 Entry 的 key 的 hashCode() 返回值相同，那它们的存 储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true，新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value，但 key 不会覆盖。如果 这两个 Entry 的 key 通过 equals 比较返回 false，新添加的 Entry 将与集 合中原有 Entry 形成 Entry 链，而且新添加的 Entry 位于 Entry 链的头部— —具体说明继续看 addEntry() 方法的说明。

当向 HashMap 中添加 key-value 对，由其 key 的 hashCode() 返回值决定 该 key-value 对（就是 Entry 对象）的存储位置。当两个 Entry 对象的 key 的 hashCode() 返回值相同时，将由 key 通过 eqauls() 比较值决定是采用覆 盖行为（返回 true），还是产生 Entry 链（返回 false）。

上面程序中还调用了 addEntry(hash, key, value, i); 代码，其中 addEntry 是 HashMap 提供的一个包访问权限的方法，该方法仅用于添加一个 key-value 对。下面是该方法的代码：

void　addEntry(int　hash,　K　key,　V　value,　int　 bucketIndex) { 　　 //　获取指定　bucketIndex　索引处的　Entry 　　 Entry<K,V>　e　=　table[bucketIndex];　//　① 　　 //　将新创建的　Entry　放入　bucketIndex　索引处，并让新的　 Entry　指向原来的　Entry 　　 table[bucketIndex]　=　new　Entry<K,V>(hash,　key,　 value,　e); 　　 //　如果　Map　中的　key-value　对的数量超过了极限 　　 if　(size++　>=　threshold) 　　　　 //　把　table　对象的长度扩充到　2　倍。 　　　　

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