javahashmap工作原理-java开发java经验技巧

《javahashmap工作原理-java开发java经验技巧》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、JavaHashMap211作原理-编程开发技术JavaHashMap工作原理木文由ImportNew・Wing翻译自coding-geek0欢迎加入翻译小组。转载请见文末要求。大部分Java开发者都在使用Map,特别是HashMapoHashMap是种简单但强人的方式去存储和获取数据。但有多少开发者知道HashMap内部如何工作呢？几天前,我阅读了java.util.HashMap的大量源代码(包括Java7和Java8),来深入理解这个基础的数据结构。在这篇文章中，我会解释java.util.HashMap的实现，描述Jav

2、a8实现中添加的新特性，并讨论性能、内存以及使用HashMap吋的一些已知问题。内部存储JavaHashMap类实现了Map〈K,V>接口。这个接口中的主要方法包扌乩•Vput(Kkey,Vvalue)•Vget(Objectkey)•Vremove(Objectkey)•BooleancontainsKcy(Objcctkey)HashMap使用了一个内部类Entry〈K,V>來存储数据。这个内部类是一个简单的键值对，并带有额外两个数据：•一个指向其他入口(译者注：引用对彖)的引用，这样HashMap可以存储类似链接列表这样的

3、对象。•一个用來代表键的哈希值，存储这个值可以避免HashMap在每次需要时都重新生成键所对应的哈希值。下面是Entry在Java7下的一部分代码:staticclassEntryimplementsMap.Entry{finalKkey;Vvalue;Entrynext;inihash;•••}HashMap将数据存储到多个单向Entry链表中(有时也被称为桶bucket或者容器orbins)0所有的列表都被注册到一个Entry数组中(Entry[]数组),这个内部数组的默认长

4、度是16。下而这幅图描述了一个HashMap实例的内部存储，它包含一个nullable对象组成的数组。每个对彖都连接到另外一个对彖，这样就构成了一个链表。uckets/bin所冇具冇相同哈希值的键都会被放到同一个链表(桶)中。具冇不同哈希值的键最终可能会在相同的桶中。当用户调用put(Kkey,Vvalue)或者get(Objectkey)时，程序会计算对彖应该在的桶的索引。然后，程序会迭代遍历对应的列表，来寻找具有相同键的Entry对象(使用键的equals()方法)。对于调用get()的情况，程序会返冋值所对应的Entry对

5、象(如果Entry对象存在)。对于调用put(Kkey,Vvalue)的情况,如果Entry对象已经存在,那么程序会将值替换为新值，否则，程序会在单向链表的表头创建一个新的Entry(从参数中的键和值)。桶(链表)的索引，是通过nmp的3个步骤生成的：•首先获収键的散列码。•程序重复散列码，來阻止针对键的糟糕的哈希函数，因为这有可能会将所有的数据都放到内部数组的相同的索引(桶)上。•程序拿到重复后的散列码，并对其使川数组长度(授小是1)的位掩码(bit-mask)o这个操作可以保证索引不会人于数组的人小。你可以将其看做是一个经过

6、计算的优化収模函数。卜•面是生成索引的源代码：//the"rehash"functioninJAVA7thattakesthehashcodeofthekeystaticinthash(inth){h八二(h»>20)八(h»>12);returnh八(h>>>7)八(h>>>4);//the"rehash"functioninJAVA8thatdirectlytakesthekeystaticfinalinthash(Objectkey){inth;return(key二二nul1)?0:(h二key.hashCode())八

7、(h>>>16);}//thefunctionthatreturnstheindexfromtherehashedhashstaticintindexFor(inth,intlength){returnh&dength~l);}为了更有效地工作，内部数组的大小必须是2的幕值。让我们看一下为什么：假设数组的长度是17,那么掩码的值就是16(数组长度-1)o16的二进制表示是0・・・010000,这样对于任何值H来说，“H&16”的结果就是16或者0。这意味着长度为17的数组只能应用到两个桶上：一个是0,另外一个是16,这样不是很冇

8、效率。但是如果你将数组的长度设置为2的幕值，例如16,那么按位索引的工作变成“H&15”。15的二进制表示是0-001111,索引公式输出的值可以从0到15,这样长度为16的数组就可以被充分使用了。例如：•如果H=952,它的二进制表示是0..011101110