大多数Java开发者都在使用Map，尤其是HashMap。HashMap是一种简单但功能强大的存储和检索数据的方法。但是有多少开发者知道HashMap内部是如何工作的呢？前几天看了很多java.util.HashMap（Java7和Java8）的源码，对这个基础数据结构有了更深刻的理解。在本文中，我解释了java.util.HashMap实现，描述了Java8实现中添加的新特性，并讨论了性能、内存和使用HashMap时的一些已知问题。内部存储JavaHashMap类实现了Map接口。该接口中的主要方法包括：Vput(Kkey,Vvalue)Vget(Objectkey)Vremove(Objectkey)BooleancontainsKey(Objectkey)HashMap使用内部类Entry来存储数据。这个内部类是一个简单的键值对，带有两个额外的数据：对其他条目的引用，以便HashMap可以像链表一样存储对象。用于表示密钥的哈希值。存储这个值可以避免HashMap每次需要的时候都重新生成key对应的hash值。以下是Java7下Entry的部分代码：staticclassEntryimplementsMap.Entry{finalKkey;Vvalue;Entrynext;inthash;…}HashMap将data存储在多个单向Entry链表（有时称为buckets或containerorbins）中。所有列表都注册在一个Entry数组（Entry[]数组）中，这个内部数组的默认长度为16。下图描述了一个HashMap实例的内部存储，它包含了一个可以为空的对象数组.每个对象都连接到另一个对象，从而形成一个链表。所有哈希值相同的key都会被放入同一个链表（bucket）中。具有不同哈希值的键可能最终会出现在同一个桶中。当用户调用put(Kkey,Vvalue)或get(Objectkey)时，程序会计算对象所在桶的索引。然后，程序遍历对应的列表，找到具有相同key的Entry对象（使用key的equals()方法）。对于调用get()的情况，程序会返回值对应的Entry对象（如果Entry对象存在的话）。对于调用put(Kkey,Vvalue)的情况，如果Entry对象已经存在，程序会用一个新值替换该值，否则，程序会在单向链接的头部创建一个新的Entry列表（来自参数键和值）。bucket（链表）的index是通过map的3个步骤生成的：首先，得到key的hashcode。该程序重复哈希代码以防止密钥的哈希函数错误，这可能会将所有数据放在内部数组中的同一索引（存储桶）中。该程序采用重复的哈希码并对其应用数组长度（最小为1）的位掩码。此操作确保索引不会大于数组的大小。您可以将其视为经过计算的优化模函数。这是生成索引的源代码：//JAVA7中的“rehash”函数，它采用keystatic的哈希码inthash(inth){h^=(h>>>20)^(h>>>12);returnh^(h>>>7)^(h>>>4);}//JAVA8中直接取key的“rehash”函数staticfinalinthash(Objectkey){inth;return(key==null)?0:(h=key.hashCode())^(h>>>16);}//从那里返回索引的函数hashedhashstaticintindexFor(inth,intlength){returnh&(length-1);}为了高效地工作，内部数组的大小必须是2的幂。让我们看看为什么：假设数组的长度是17，那么掩码的值是16（数组长度-1）。16的二进制表示是0...010000，所以对于任何值H，“H&16”的结果是16或0。这意味着长度为17的数组只能应用于两个桶：一个是0另一个是16，效率不是很高。但是，如果将数组的长度设置为2的幂值，比如16，则按位索引将变为“H&15”。15的二进制表示为0...001111，索引公式输出的值可以在0到15之间，所以可以充分利用长度为16的数组。例如：如果H=952，它的二进制表示是0..01110111000，对应的索引是0…01000=8如果H=1576，它的二进制表示是0..011000101000，对应的索引是0…01000=8如果H=12356146，其二进制表示为0..0101111001000101000110010，对应索引为0…00010=2如果H=59843，其二进制表示为0..01110100111000011，对应索引为0…00011=3此机制对开发者是透明的：如果他选择长度为37的HashMap，Map会自动选择大于37的下一个2（64）次方作为内部数组的长度。自动调整大小获取索引后，get()、put()或remove()方法会访问对应的链表，检查指定键的Entry对象是否已经存在。如果不修改，这个机制可能会导致性能问题，因为这个方法需要遍历整个列表，看看Entry对象是否存在。假设内部数组的长度默认为16，需要存储2,000,000条记录。在最好的情况下，每个链表将有125,000个Entry对象(2,000,000/16)。get()、remove()和put()方法每次执行时需要125,000次迭代。为了避免这种情况，HashMap可以增加内部数组的长度，从而保证链表中只保留少数Entry对象。创建HashMap时，可以通过以下构造函数指定初始长度和loadFactor：publicHashMap(intinitialCapacity,floatloadFactor)如果不指定参数，则默认initialCapacity值为16,loadFactor的默认值为0.75。initialCapacity表示内部数组链表的长度。每次使用put(...)方法向Map添加新的键值对时，该方法都会检查是否需要增加内部数组的长度。为了实现这一点，Map存储了两条数据：Map的大小：它表示HashMap中的记录数。我们在向其中插入或删除值时更新HashMap。阈值：等于内部数组的长度*loadFactor，当调整内部数组的长度时，阈值会同时更新。在添加新的Entry对象之前，put(...)方法会检查当前Map的大小是否大于阈值。如果它大于阈值，它会创建一个新数组，其长度是当前内部数组的两倍。因为新数组的大小发生了变化，索引函数（即返回“键的哈希&（数组长度-1）”的按位运算结果）也发生了变化。调整数组大小会创建两个新的桶（链接列表）并将所有现有的Entry对象重新分配给桶。调整数组大小的目的是减少链表的大小，从而减少put()、remove()和get()方法的执行时间。对于具有相同hash值的key对应的所有Entry对象，调整大小后会分配到同一个bucket中。但是，如果两个Entry对象的key的hash值不一样，但是之前在同一个bucket上，不能保证调整后还是在同一个bucket上。此图像描述了调整前后内部阵列的状况。在调整数组长度之前，为了得到Entry对象E，Map需要遍历一个包含5个元素的链表。调整数组长度后，同样的get()方法只需要遍历一个包含2个元素的链表，所以调整数组长度后get()方法的运行速度提高了一倍。线程安全如果你已经很熟悉HashMap，那么你一定知道它不是线程安全的，但是为什么呢？例如，假设你有一个Writer线程，它只会将现有数据插入到Map中，还有一个Reader线程，它会从Map中读取数据，那么为什么它不起作用？因为在自动调整大小机制下，如果一个线程试图添加或获取一个对象，Map可能会使用旧的索引值，这样就找不到Entry对象所在的新bucket。最坏的情况下，当2个线程同时插入数据时，2次put()调用会同时触发数组自动resize。由于两个线程同时在修改链表，所以Map在链表的内循环中退出是有可能的。如果你试图用一个内循环获取列表中的数据，get()方法将永远不会结束。HashTable提供了一个线程安全的实现来防止上述情况的发生。但是，由于所有同步CRUD操作都非常慢。比如线程1调用了get(key1)，然后线程2调用了get(key2)，线程2调用了get(key3)，那么在给定的时间内，只有1个线程能拿到它的值，但是3个线程都拿到了这些数据可以同时访问。从Java5开始，我们有了一个更好的、线程安全的HashMap实现：ConcurrentHashMap。对于ConcurrentMap，只有桶是同步的，这样如果多个线程不使用同一个桶或调整内部数组的大小，它们可以同时调用get()、remove()或put()方法。在多线程应用程序中，这种方法是更好的选择。键的不变性为什么使用字符串和整数作为HashMap键是一个很好的实现？主要是因为它们是不可变的！如果你选择自己创建一个类作为键，但这个类不保证不可变，那么你可能会丢失HashMap内部的数据。让我们看一下以下用例：您有一个内部值为“1”的键。你向HashMap中插入一个对象，它的键是“1”。HashMap从键的散列码（即“1”）生成散列值。Map将此哈希值存储在新创建的记录中。您更改密钥的内部值，将其更改为“2”。密钥的散列已更改，但HashMap对此一无所知（因为存储了旧散列）。您尝试通过修改后的键获取相应的对象。Map会计算新key的hash值（即“2”），找到Entry对象所在的链表（bucket）。Case1：既然修改了key，Map会去错误的bucket中找Entry对象，找不到。情况2：你很幸运，修改后的密钥生成的桶与旧密钥生成的桶相同。Map此时会遍历链表，已经找到key相同的Entry对象。但是为了找到一个键，Map首先通过调用equals()方法来比较键的散列。因为修改后的key会产生不同的hash值（旧的hash值保存在record中），那么Map就没有办法在链表中找到对应的Entry对象。下面是一个Java的例子，我们在Map中插入两个键值对，然后我修改第一个键，尝试获取这两个对象。你会发现Map只返回了第二个对象，而HashMap中已经“丢失”了第一个对象：i;}publicMyKey(Integeri){this.i=i;}@OverridepublicinthashCode(){returni;}@Overridepublicbooleanequals(Objectobj){if(objinstanceofMyKey){returni.equals(((MyKey)obj).i);}elsereturnfalse;}}MapmyMap=newHashMap<>();MyKeykey1=newMyKey(1);MyKeykey2=newMyKey(2);myMap.put(key1,"test"+1);myMap.put(key2,"test"+2);//修改key1key1.setI(3);Stringtest1=myMap.get(key1);Stringtest2=myMap.get(key2);System.out.println("test1="+test1+"test2="+test2);}}上面代码的输出是"test1=nulltest2=test2"。正如我们所预料的那样，Map不具备检索修改后的key1对应的字符串1的能力。Java8中的改进在Java8中，HashMap的内部实现发生了很多变化。确实，Java7用了1000行代码来实现，而Java8用了2000行代码。我上面描述的大部分内容在Java8中仍然适用，除了使用链表来保存Entry对象。在Java8中，我们仍然使用数组，但是会存储在Node中，其中包含与之前的Entry对象相同的信息，也会使用链表：以下是Node在Java8中实现的部分代码:staticclassNodeimplementsMap.Entry{finalinthash;finalKkey;Vvalue;Nodenext;那么与Java7相比，最大的区别是什么？那么，Node可以扩展为TreeNode。TreeNode是一个红黑树数据结构，它可以存储更多的信息，这样我们就可以在O(log(n))的复杂度下对一个元素进行增删改查。下面的例子描述了TreeNode保存的所有信息：staticfinalclassTreeNodeextendsLinkedHashMap.Entry{finalinthash;//inheritedfromNodefinalKkey;//inheritedfromNodeVvalue;//inheritedfromNodeNodenext;//继承自NodeEntrybefore,after;//继承自LinkedHashMap.EntryTreeNodeparent;TreeNodeleft;TreeNoderight;TreeNodeprev;booleanred;红黑树是一种自平衡的二叉搜索树。它的内部机制可以保证它的长度始终是log(n)，无论我们添加还是删除节点。使用这种树的主要优点是内部表中的许多数据具有相同的索引（桶）。此时，查找树的复杂度是O(log(n))，而对于链表来说，要进行同样的操作，复杂度是O(n)。如您所见，我们确实在树中存储了比链表中更多的数据。根据继承原则，内表可以包含Node（链表）或TreeNode（红黑树）。Oracle决定按照以下规则使用这两种数据结构：-对于内表中的指定索引（桶），如果节点数大于8，则将链表转换为红黑树.-对于内表中的指定索引（bucket），如果节点数小于6，则红黑树转为链表。此图描绘了Java8HashMap中的内部数组，其中包含树（桶0）和链表（桶1、2和3）。Bucket0是一个树结构，因为它包含了8个以上的节点。内存开销JAVA7使用HashMap来消耗一些内存。在Java7中，HashMap将键值对封装到Entry对象中。Entry对象包含以下信息：对下一条记录的引用预先计算的哈希值（整数）对键的引用对值的引用此外，Java7中的HashMap使用Entry对象的内部数组。假设一个Java7HashMap包含N个元素，其内部数组的容量为CAPACITY，那么额外的内存消耗约为：sizeOf(integer)*N+sizeOf(reference)*(3*N+C)其中：integer的大小为4字节引用的大小取决于JVM、操作系统和处理器，但通常为4字节。这意味着总内存开销通常为16*N+4*CAPACITY字节。注意：Map自动调整大小后，CAPACITY的值为大于N的下一个最小的2的次幂。注意：从Java7开始，H??ashMap采用了懒加载机制。这意味着即使您为HashMap指定了一个大小，记录使用的内部数组（花费4*CAPACITY字节）也不会在内存中分配，直到我们第一次使用put()方法。JAVA8在Java8的实现中，内存使用量的计算变得更加复杂，因为Node可能存储和Entry相同的数据，或者在此基础上增加6个引用和一个布尔属性（指定是否为TreeNode）。如果所有节点都只是Node，那么Java8HashMap消耗的内存与Java7HashMap相同。如果所有节点都是TreeNode，那么Java8HashMap消耗的内存变为：N*sizeOf(integer)+N*sizeOf(boolean)+sizeOf(reference)*(9*N+CAPACITY)inmoststandardJVM,结果上面的公式是44*N+4*CAPACITY字节。性能问题AsymmetricHashMapvsBalancedHashMap在最好的情况下，get()和put()方法的复杂度都是O(1)。但是，如果您不关心密钥的哈希函数，那么您的put()和get()方法可能会执行得很慢。put()和get()方法的高效执行取决于分配给内部数组（桶）不同索引的数据。如果密钥的哈希函数设计不当，您将得到一个非对称分区（无论内部数据的大小如何）。所有的put()和get()方法都会使用一个专用的链表，执行起来会很慢，因为需要遍历链表中的所有记录。在最坏的情况下（如果大部分数据都在同一个桶上），那么你的时间复杂度就变成了O(n)。下面是一个视觉示例。第一张图描述的是非对称HashMap，第二张图描述的是平衡HashMap。在这个非对称HashMap中，在bucket0上运行get()和put()方法会花费很多时间。获取记录K需要6次迭代。在这个平衡的HashMap中，只需要迭代3次就可以得到记录K。两个HashMap存储的数据量相同，内部数组的大小也相同。唯一的区别是键的哈希函数，它用于将记录分布到不同的桶中。下面是一个用Java写的极端例子，在这个例子中，我使用哈希函数将所有数据放入同一个链表（桶）中，然后添加2,000,000条数据。publicclassTest{publicstaticvoidmain(String[]args){classMyKey{Integeri;publicMyKey(Integeri){this.i=i;}@OverridepublicinthashCode(){return1;}@Overridepublicbooleanequals(Objectobj){...}}Datebegin=newDate();MapmyMap=newHashMap<>(2_500_000,1);for(inti=0;i<2_000_000;i++){myMap.put(newMyKey(i),"test"+i);}Dateend=newDate();System.out.println("Duration(ms)"+(end.getTime()-begin.getTime()));}}我的机器配置是corei5-2500k@3.6G，需要在java8u40下运行需要45分钟以上（我停了45分钟后的过程）。如果我运行相同的代码，但我使用以下哈希函数：@OverridepublicinthashCode(){intkey=2097152-1;returnkey+2097152*i;}运行需要46秒，比以前好很多。！新的哈希函数在处理哈希分区时比旧的哈希函数更合理，所以调用put()方法会更快。如果您现在运行相同的代码，但使用以下散列函数，它提供了更好的散列分区：@OverridepublicinthashCode(){returni;}现在只需要2秒！我希望您意识到哈希函数的重要性。如果在Java7上运行相同的测试，第一个和第二个更糟糕（因为Java7中的put()方法具有O(n)复杂度，而在Java8中是O(n)(log(n)).在使用HashMap的时候，需要为key找到一个hash函数，能够将key散布到最有可能的bucket中。为此，需要避免hash冲突。String对象是一个很好的key，因为它有一个很好的hash功能。整数也很好，因为它的哈希值是它自己的值。调整大小开销如果需要存储大量数据，则应在创建HashMap时指定初始容量，该容量应接近您想要的大小。如果不这样做，Map将使用默认大小，即16，factorLoad的值为0.75。前11次调用put()方法会很快，但是第12次（16*0.75）调用会新建一个长度为32的内部数组（以及对应的链表/树），第13次到第22次调用put()会很快，但是第23次(32*0.75)调用将（再次）重新创建一个新的内部数组，使数组的长度加倍。然后在第48次，第96次，第192次调用put()方法时会触发内部调整大小操作。如果数据量不大，重建内部数组的操作会很快，但是当数据量大，耗时可能从几秒到几分钟不等。通过在初始化时指定Map的预期大小，可以避免调整大小操作的开销。但是这里也有一个缺点：如果你把数组设置的很大，比如说2^28，但是你在数组中只使用了2^26个桶，那么你会浪费很多内存（在这个例子中大约是2^30字节）。结论对于简单的用例，您不需要知道HashMap是如何工作的，因为您看不到O(1)、O(n)和O(log(n))之间的区别。但了解这种常用数据结构背后的机制总是好的。此外，这是Java开发人员职位的典型面试问题。对于大数据量，理解HashMap的工作原理和理解哈希函数对键的重要性变得非常重要。希望本文能帮助大家深入了解HashMap的实现。
