大多数JAVA开发者都在使用Maps，尤其是HashMaps。HashMap是一种简单而强大的存储和检索数据的方法。但是有多少开发者知道HashMap内部是如何工作的呢？前几天为了深入了解这个基本的数据结构，看了很多java.util.HashMap的源码（Java7，然后是Java8）。在本文中，我解释了java.util.HashMap实现，介绍了JAVA8实现中的新特性，并讨论了使用HashMap时的性能、内存和已知问题。内存JAVAHashMap类实现接口Map。这个接口的主要方法有：Vput(Kkey,Vvalue)Vget(objectkey)Vremove(objectkey)BooleancontainsKey(objectkey)HashMaps使用一个内部类来存储数据：Entry.这个条目是一个简单的键值对，有两个额外的数据：对另一个条目的引用，以便HashMap可以存储键的散列的散列等，其中条目代表键。存储此哈希以避免每次HashMap需要时都计算哈希。这是JAVA7中Entry实现的一部分：HashMap将数据存储到多个条目的单链表（也称为桶或箱）中。所有列表都注册在一个Entry数组（Entry[]数组）中，这个内部数组的默认容量是16。下图显示了一个HashMap实例的内部存储，其中包含一个可以为null的条目数组。每个Entry都可以链接到另一个Entry，形成一个链表。所有具有相同哈希值的键都放在同一个链表（桶）中。具有不同哈希值的键可能最终会出现在同一个桶中。当用户调用put(Kkey,Vvalue)或get(Objectkey)时，该函数会计算出Entry所在的桶的索引。然后该函数遍历列表以查找具有相同键的条目（使用键的equals()函数）。在get()的情况下，函数返回与条目关联的值（如果条目存在）。在put(Kkey,Vvalue)的情况下，如果该条目存在，则函数将其替换为新值，否则它会在单链表的头部创建一个新条目（根据参数）。这个bucket的索引（链表）是通过map分3步生成的：首先获取key的hashcode。它重新散列哈希码以防止将所有数据放在内部数组的同一索引（存储桶）中的密钥的错误散列函数，它采用重新散列的哈希码并使用数组的长度（减去1）对其进行位掩码。此操作确保索引不能大于数组的大小。您可以将其视为计算上非常优化的模函数。这是处理索引的JAVA7和8源代码：为了高效工作，内部数组的大小需要是2的幂，让我们看看为什么。假设数组大小为17，掩码值为16（大小-1）。16的二进制表示为0…010000，因此对于任何哈希值H，使用按位公式“HAND16”生成的索引将是16或0。这意味着大小为17的数组将仅用于2桶：一个在索引0和一个在索引16，这不是很有效......但是如果你现在采用2的幂（如16）的大小，则按位索引公式为“HAND15”。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这就是数组大小为2的幂的原因。这机制对开发者是透明的：如果他选择一个大小为37的HashMap，Map会自动选择37之后的下一个2的次方（64）作为其内部数组的大小。在autoresizing获得索引后，函数（get、put或remove）访问/迭代关联的链表以查看是否存在给定键的现有条目。如果不修改此机制，可能会导致性能问题，因为该函数需要遍历整个列表以查看是否存在条目。假设内部数组的大小是默认值(16)，您需要存储200万个值。在最好的情况下，每个链表的大小为125,000个条目（2/16百万）。所以每个get()、remove()和put()将导致125000次迭代/操作。为了避免这种情况，HashMap可以增加其内部数组以保持链表非常短。创建HashMap时，可以使用以下构造函数指定初始大小和loadFactor：如果不指定参数，则默认initialCapacity为16，默认loadFactor为0.75。initialCapacity表示链表内部数组的大小。每次使用put(...)将新键/值添加到Map时，该函数都会检查是否需要增加内部数组。为此，map存储了2个数据：map的大小：表示HashMap中条目的数量。每次添加或删除条目时都会更新此值。athreshold：等于（内部数组的容量）*loadFactor，每次调整内部数组的大小后刷新。在添加新条目之前，put(...)检查大小是否大于阈值，如果是，则重新创建一个大小加倍的新数组。由于新数组的大小发生了变化，因此索引函数（返回按位运算“hash(key)AND(sizeOfArray-1)”）发生了变化。因此，调整数组大小会创建两倍数量的桶（即链表）并将所有现有条目重新分配到桶（旧的和新创建的）中。此调整大小操作的目的是减小链表的大小，以便put()、remove()和get()方法的时间成本保持较低。调整大小后，所有键具有相同散列的条目将保留在同一个桶中。但是，之前在同一个桶中的具有不同哈希键的2个条目在转换后可能不在同一个桶中。图片显示了调整内部数组大小之前和之后的表示。在递增之前，map必须遍历5个元素的列表才能获得条目E。调整大小后，相同的get()只是遍历2个元素的链表，调整大小后get()快2倍！注意：HashMap只是增加内部数组的大小，并没有提供减少它的方法。线程安全如果您已经了解HashMap，那么您就知道这不是线程安全的，但为什么呢？例如，假设你有一个只是将新数据放入Map的Writer线程和一个从Map读取数据的Reader线程，为什么它不起作用？因为在自动调整大小机制期间，如果一个线程试图放入或获取一个对象，map可能会使用旧的索引值而找不到条目所在的新桶。最坏的情况是当2个线程同时放入数据并且2个put()调用同时调整Map的大小。由于两个线程同时修改链表，因此Map可能会在其中一个链表中出现内部循环。如果您尝试使用内部循环获取列表中的数据，则get()将永远不会结束。HashTable实现是一个线程安全的实现，可以防止这种情况发生。然而，由于所有的CRUD方法都是同步的，所以这个实现非常慢。例如线程1调用get(key1)，线程2调用get(key2)，线程3调用get(key3)，那么同一时刻只有一个线程可以获取到它的值，而线程3可以同时访问数据时间。自JAVA5以来，存在一个更智能的线程安全HashMap实现：ConcurrentHashMap。只有桶是同步的，所以如果不意味着访问同一个桶或调整内部数组的大小，多个线程可以同时获取（）、删除（）或放置（）数据。最好在多线程应用程序中使用此实现。键不变性为什么字符串和整数是HashMap键的良好实现？主要是因为它们是不可变的！如果您选择创建自己的Key类而不使其不可变，则可能会丢失HashMap中的数据。查看以下用例：您有一个内部值为“1”的键您使用此键将对象放入HashMapHashMap从Key的哈希码（因此以“1”开头）生成哈希Map存储这个散列在一个新的在创建的条目中，您将密钥的内部值修改为“2”修改了密钥的散列值，但HashMap不知道（因为存储了旧的散列值）您尝试获取具有修改键的对象地图计算您的键（因此从“2”开始）以查找条目在案例1中的链表（桶）：由于您修改了键，地图试图在错误的桶中找到条目，但没有找到情况2：幸运的是，修改后的密钥生成与旧密钥相同的桶。然后映射遍历链表以找到具有相同键的条目。但是要找到key，map是先比较hash值，然后调用equals()比较。由于您修改后的密钥的哈希值与旧哈希值（存储在条目中）不同，因此映射不会在链表中找到该条目。这是Java中的一个具体示例。我在我的地图中放置了2个键值对，我修改了第一个键，然后尝试获取2个值。该映射仅返回第二个值，第一个值在HashMap中“丢失”：输出为：“test1=nulltest2=test2”。正如预期的那样，Map无法通过修改的键1检索到字符串1。JAVA8ImprovementsHashMap的内部表示在JAVA8中发生了很大变化。确实，在JAVA7中的实现需要1k行代码，而在JAVA8中的实现需要2k行。我之前说的大部分都是真的，除了条目的链表。在JAVA8中，您仍然有一个数组，但它现在存储包含与条目完全相同的信息的节点，因此也存储链表：这是JAVA8中节点实现的一部分：那么与JAVA7最大的区别是什么？那么，Nodes可以扩展为TreeNodes。TreeNode是一种红黑树结构，它存储了更多信息，因此它可以在O(log(n))中添加、删除或获取元素。仅供参考，这里是存储在TreeNode中的数据的详尽列表红黑树是自平衡二叉搜索树。它们的内部机制确保它们的长度始终在log(n)中，尽管有新添加或删除的节点。使用这些树的主要优点是，如果许多数据位于内表的同一索引（桶）中，则树中的搜索将花费O(log(n))而它将花费O(n)与链表。如您所见，树实际上比链表占用更多空间（我们将在下一节中讨论）。通过继承，内表可以同时包含Node（链表）和TreeNode（红黑树）。Oracle决定按照以下规则使用这两种数据结构：–如果内表中给定的索引（桶）有超过8个节点，则将链表转换为红黑树–如果给定的索引（桶）内表中节点数少于6个，将树转为链表此图为JAVA8HashMap的内部数组，包含两棵树（位于bucket0）和链表（位于bucket1、2、3）。Bucket0是一棵树，因为它有8个以上的节点。内存开销JAVA7HashMap的使用是以内存为代价的。在Java7中，HashMap将键值对包装在Entries中。条目具有：对下一个条目的引用预先计算的散列（整数）对键的引用对值的引用此外，Java7HashMap使用内部条目数组。假设一个JAVA7HashMap包含N个元素，其内部数组的容量为CAPACITY，则额外的内存开销大约为：sizeOf(integer)N+sizeOf(reference)(3*N+C)其中：整数的大小取决于等于或等于4字节的引用大小取决于JVM/OS/处理器，但通常为4字节。这意味着开销通常为16N+4CAPACITY字节提醒：自动调整映射大小后，内部数组的容量等于N之后的下一个2的幂。注意：从JAVA7开始，HashMap类具有惰性初始化.这意味着即使您分配了一个HashMap，在第一次使用put()方法之前，内部条目数组也不会在内存中分配（消耗4*CAPACITY字节）。使用JAVA8实现，获取内存使用情况变得有点复杂，因为节点可以包含与条目相同的数据或相同的数据加上6个引用和一个布尔值（如果它是TreeNode）。如果所有节点都是Nodes，那么JAVA8HashMap的内存消耗和JAVA7HashMap是一样的。如果所有节点都是TreeNodes，JAVA8HashMap的内存消耗变为：NsizeOf(integer)+NsizeOf(boolean)+sizeOf(reference)(9N+CAPACITY)在大多数标准JVM中，它等于44N+4CAPACITY字节性能问题SlantedHashMap和well-balancedHashMap在最好的情况下，get()和put()方法的时间复杂度是O(1)。但是，如果您不注意密钥的哈希函数，您可能会以非常慢的put()和get()调用而告终。put()和get的良好性能取决于将数据重新分区到内部数组（桶）的不同索引中。如果您的密钥的哈希函数设计不当，您将有一个倾斜的重新分区（无论内部数组的容量如何）。所有使用max-entry链表的put()和get()都会很慢，因为它们需要迭代整个链表。在最坏的情况下（如果大部分数据都在同一个桶中），您最终可能会遇到O(n)时间复杂度。这是一个视觉示例。第一张图显示了一个倾斜的HashMap，第二张图是一个平衡良好的图。在这种倾斜的HashMap的情况下，存储桶0上的get()/put()操作是昂贵的。获取条目K将需要6次迭代在这个平衡良好的HashMap的情况下，获取条目K将需要3次迭代。两个HashMap存储相同数量的数据并且具有相同的内部数组大小。唯一的区别是（键的）散列函数在桶中分配条目。这是JAVA中的一个极端例子，我创建了一个哈希函数，将所有数据放在同一个桶中，然后添加了200万个元素。在我的核心i5-2500k@3.6Ghz上，使用java8u40需要超过45分钟（我在45分钟后停止了该过程）。现在，如果我运行相同的代码，但这次我使用以下哈希函数，它需要46秒，这要好得多！这个散列函数比前一个有更好的重新分区，所以put()调用更快。如果我使用以下哈希函数运行相同的代码，它会提供更好的哈希重新分区，现在需要2秒。我希望你意识到哈希函数的重要性。同样的测试如果在JAVA7上运行，第一种和第二种情况的结果会更差（因为put的时间复杂度在JAVA7中是O(n)，而在使用HashMap时是O(log(n))），您需要为您的密钥找到一个散列函数，将密钥散布到最有可能的存储桶中。为此，您需要避免散列冲突。StringObject是一个很好的键，因为它有很好的散列函数。整数也很好，因为它们的哈希码是它们自己的值。调优开销如果您需要存储大量数据，您应该创建一个初始容量接近预期容量的HashMap。如果您不这样做，地图将假定默认大小为16，factorLoad为0.75。第11个put()会非常快，但第12个(160.75)将重新创建一个新的内部数组（及其关联的链表/树），新容量为32。第13到23个会很快，但第24个（320.75）将（再次）重新创建一个昂贵的新表示，使内部数组的大小加倍。内部调整大小操作将发生在第48次、第96次、第192次……put()调用时。内部阵列的完整重建在低容量时很快，但在高容量时可能需要几秒到几分钟。通过最初设置您的预期大小，您可以避免这些代价高昂的操作。但有一个缺点：如果你设置一个非常大的数组大小，比如2^28，而你只在数组中使用2^26个桶，你将浪费大量内存（在这种情况下大约2^30字节）。结论对于简单的用例，您不需要知道HashMap是如何工作的，因为您看不到O(1)和O(n)或O(log(n))操作之间的区别。但了解最常用数据结构之一的底层机制总是更好。此外，这是Java开发人员职位的典型面试问题。在大量情况下，了解其工作原理和键控哈希函数的重要性变得很重要。^28并且您只在数组中使用2^26个存储桶，您浪费了大量内存（在这种情况下大约2^30字节）。结论对于简单的用例，您不需要知道HashMap是如何工作的，因为您看不到O(1)和O(n)或O(log(n))操作之间的区别。但了解最常用数据结构之一的底层机制总是更好。此外，这是Java开发人员职位的典型面试问题。在大量情况下，了解其工作原理和键控哈希函数的重要性变得很重要。希望本文能帮助您深入了解HashMap的实现。你学过HashMap吗？
