前言
大多数JAVA开发人员都在使用Maps，尤其是HashMaps。HashMap是一种简单并且有效的存取数据的方式。但是有多少人知道HashMap内部是如何工作的么？前段时间，为了深入理解这个基础的数据结构，我阅读了 java.util.HashMap大部分源码(先是Java 7中，然后是Java 8)。在这篇文章中，我将解释java.util.HashMap的实现，并介绍JAVA 8实现的新功能，并讨论使用HashMaps时的性能，内存和已知的一些问题。
内部存储器
JAVA HashMap类实现接口Map 。该接口的主要方法是：
- V put(K键，V值)
- V get(对象键)
- V remove(对象键)
- 布尔containsKey(Object key)
HashMaps使用一个内部类来存储数据：Entry 。此项是一个简单的键值对，其中包含两个额外的数据：
- 对另一个Entry的引用，以便HashMap可以存储单个链接列表之类的条目
- 表示键的哈希值的哈希值。存储该哈希值是为了避免每次HashMap需要哈希时都进行哈希计算。
这是Java 7中Entry实现的一部分：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry next;int hash;
…
}HashMap将数据存储到多个单链接的条目列表(也称为buckets或bins)中。所有列表都注册在Entry数组(Entry []数组)中，并且此内部数组的默认容量为16。
下图显示了带有可空条目数组的HashMap实例的内部存储。每个条目可以链接到另一个条目以形成链接列表。
具有相同哈希值的所有键都放在相同的链表(存储桶)中。具有不同哈希值的键可以最终出现在同一存储桶中。
当用户调用put(K键，V值)或get(Object键)时，该函数将计算Entry所在的存储区的索引。然后，该函数遍历列表以查找具有相同键的Entry(使用键的equals()函数)。
对于get()，该函数返回与该条目关联的值(如果该条目存在)。
对于put(K键，V值)，如果该条目存在，则该函数将其替换为新值，否则它将在单链接列表的开头创建一个新条目(根据键和参数中的值)。
桶的索引(链接列表)由地图分3步生成：
- 它首先获取密钥的哈希码。
- 它会重新整理哈希码，以防止将所有数据放入内部数组的同一索引(存储桶)的键中的哈希功能不正确
- 它获取经过重整的哈希哈希码，并使用数组的长度(减1)对其进行位掩码。此操作可确保索引不能大于数组的大小。您可以将其视为在计算上经过优化的模函数。
这是处理索引的JAVA 7和8源代码：
// the "rehash" function in JAVA 7 that takes the hashcode of the key
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
// the "rehash" function in JAVA 8 that directly takes the key
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// the function that returns the index from the rehashed hash
static int indexFor(int h, int length) {
return h & (length-1);
}
为了有效地工作，内部数组的大小需要为2的幂，让我们看看为什么。
想象一下，数组大小为17，掩码值将为16(大小为-1)。16的二进制表示形式是0…010000，因此对于任何哈希值H，使用按位公式“ H AND 16”生成的索引将为16或0。这意味着大小为17的数组将仅用于2个存储桶：索引0的一个和索引16的一个，效率不高…
但是，如果您现在采用的是2的幂(如16)，则按位索引公式为“ H AND 15”。15的二进制表示形式是0…001111，因此索引公式可以输出0到15的值，并且大小为16的数组已完全使用。例如：
- 如果H = 952，则其二进制表示形式为0..0111011 1000，关联的索引为0…0 1000 = 8
- 如果H = 1576，其二进制表示形式是0..01100010 1000，则关联的索引是0…0 1000 = 8
- 如果H = 12356146，则其二进制表示形式为0..010111100100010100011 0010，关联的索引为0…0 0010 = 2
- 如果H = 59843，则其二进制表示形式为0..0111010011100 0011，关联的索引为0…0 0011 = 3
这就是为什么数组大小是2的幂的原因。此机制对开发人员是透明的：如果他选择大小为37的HashMap，则Map将自动为其内部数组的大小选择37(64)之后的下一个2的幂。
自动调整大小
获取索引后，函数(获取，放置或删除)访问/迭代关联的链表，以查看给定键是否存在现有的Entry。如果不进行修改，此机制可能会导致性能问题，因为该函数需要遍历整个列表以查看条目是否存在。想象一下，内部数组的大小是默认值(16)，您需要存储2百万个值。在最佳情况下，每个链接列表的大小为125 000个条目(2/16百万)。因此，每个get()，remove()和put()都会导致125 000次迭代/运算。为了避免这种情况，HashMap可以增加其内部数组，以保留非常短的链表。
创建HashMap时，可以使用以下构造函数指定初始大小和loadFactor：
public HashMap(int initialCapacity, float loadFactor)如果不指定参数，则默认initialCapacity为16，默认loadFactor为0.75。initialCapacity表示链表内部数组的大小。
每次使用put(…)在Map中添加新的键/值时，该函数都会检查是否需要增加内部数组的容量。为此，地图存储了2个数据：
- 地图的大小：它表示HashMap中的条目数。每次添加或删除条目时，都会更新此值。
- 一个阈值：等于(内部数组的容量)* loadFactor，并在每次调整内部数组的大小后刷新
在添加新的Entry之前，put(…)检查size是否大于阈值，以及是否重新创建大小加倍的新数组。由于新数组的大小已更改，因此索引函数(返回按位运算“ hash(key)AND(sizeOfArray-1)”)将发生变化。因此，数组大小的调整会创建更多的存储桶(即链接列表)，并将 所有现有条目重新分配到存储桶中(旧的和新创建的)。
调整大小操作的目的是减小链接列表的大小，以使put()，remove()和get()方法的时间成本保持较低。调整大小后，其键具有相同哈希值的所有条目将保留在同一存储桶中。但是，转换之前在同一存储桶中的两个具有不同哈希键的条目可能不在转换之后的同一存储桶中。
该图显示了调整内部数组大小之前和之后的表示。在增加之前，为了获得条目E，地图必须迭代5个元素的列表。调整大小后，相同的get()只是遍历2个元素的链接列表，调整大小后，get()快2倍！
注意：HashMap仅增加内部数组的大小，没有提供减小其大小的方法。
线程安全
如果您已经了解HashMaps，那么您知道那不是线程安全的，但是为什么呢？例如，假设您有一个Writer线程，该线程仅将新数据放入Map中，而一个Reader线程则从Map读取数据，为什么它不起作用？
因为在自动调整大小机制期间，如果线程尝试放置或获取对象，则映射可能会使用旧的索引值，而不会找到条目所在的新存储桶。
最坏的情况是两个线程同时放置一个数据，而两个put()调用则同时调整Map的大小。由于两个线程同时修改链表，因此Map可能在其链表之一中以一个内循环结束。如果您尝试通过内部循环获取列表中的数据，则get()将永远不会结束。
该哈希表的实现是线程安全的实现，从这种情况下阻止。但是，由于所有CRUD方法都是同步的，因此此实现非常慢。例如，如果线程1调用get(key1)，线程2调用get(key2)，线程3调用get(key3)，则一次只能获得一个线程的值，而其中的3个线程可以访问数据同时。
自Java 5以来，存在一个更安全的线程安全HashMap实现：ConcurrentHashMap。只有存储桶是同步的，因此如果多个线程不暗示访问同一存储桶或调整内部数组的大小，则可以同时获取()，remove()或put()数据。最好在多线程应用程序中使用此实现。
密钥不变性
为什么Strings和Integers是HashMap的键的良好实现？主要是因为它们是一成不变的！如果选择创建自己的Key类并且不使其不可变，则可能会丢失HashMap中的数据。
查看以下用例：
- 您有一个内部值为“ 1”的键
- 使用此键将对象放入HashMap
- HashMap从密钥的哈希码生成哈希(因此从“ 1”开始)
- Map 将此哈希存储 在新创建的Entry中
- 您将密钥的内部值修改为“ 2”
- 键的哈希值已修改，但HashMap不知道(因为存储了旧的哈希值)
- 您尝试使用修改后的密钥获取对象
- 映射会计算密钥的新哈希值(因此从“ 2”开始)以找到条目位于哪个链接列表(存储桶)中
- 情况1：由于您修改了密钥，因此地图会尝试在错误的存储桶中找到条目，但找不到它
- 情况2：幸运的是，修改后的密钥会生成与旧密钥相同的存储桶。然后，映射将遍历链接列表，以查找具有相同键的条目。但是要找到键，映射首先比较哈希值，然后调用equals()比较。由于修改后的键的哈希值与旧哈希值(存储在条目中)的哈希值不同，因此映射将在链表中找不到该条目。
这是Java中的具体示例。我在地图中放入了2个键值对，修改了第一个键，然后尝试获取2个值。从地图仅返回第二个值，第一个值在HashMap中“丢失”：
public class MutableKeyTest {
public static void main(String[] args) {
class MyKey {
Integer i;
public void setI(Integer i) {
this.i = i;
}
public MyKey(Integer i) {
this.i = i;
}
@Override
public int hashCode() {
return i;
}
@Override
public boolean equals(Object obj) {
if (obj instanceof MyKey) {
return i.equals(((MyKey) obj).i);
} else
return false;
}
}
Map myMap = new HashMap<>();
MyKey key1 = new MyKey(1);
MyKey key2 = new MyKey(2);
myMap.put(key1, "test " + 1);
myMap.put(key2, "test " + 2);// modifying key1
key1.setI(3);
String test1 = myMap.get(key1);
String test2 = myMap.get(key2);
System.out.println("test1= " + test1 + " test2=" + test2);
}
}输出为：“ test1 = null test2 = test 2”。如预期的那样，Map无法使用已修改的键1检索字符串1。
JAVA 8改进
HashMap的内部表示形式在JAVA 8中发生了很大变化。确实，JAVA 7中的实现需要1k行代码，而JAVA 8中的实现需要2k行代码。我之前说的大多数内容都是正确的，除了条目的链接列表。在JAVA8中，您仍然有一个数组，但是它现在存储的Node包含与Entries完全相同的信息，因此也是链接列表：
这是JAVA 8中Node实现的一部分：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node next;那么，JAVA 7的最大区别是什么？好吧，节点可以扩展到TreeNodes。TreeNode是一个红黑树结构，它存储着更多的信息，因此它可以在O(log(n))中添加，删除或获取元素。
仅供参考，这是TreeNode内部存储的数据的详尽列表
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
final int hash; // inherited from Node
final K key; // inherited from Node
V value; // inherited from Node
Node next; // inherited from Node
Entry before, after;// inherited from LinkedHashMap.Entry
TreeNode parent;
TreeNode left;
TreeNode right;
TreeNode prev;boolean red;红黑树是自平衡二进制搜索树。它们的内部机制确保尽管添加或删除了新的节点，它们的长度始终保持在log(n)中。使用这些树的主要优点是在许多数据都位于内部表的同一索引(存储桶)中的情况下，在树中进行搜索将花费O(log(n))，而在树中进行搜索则会 花费O(n)与链表。
如您所见，该树比链接列表占用了更多的空间(我们将在下一部分中讨论它)。
通过继承，内部表可以同时包含Node(链接列表)和TreeNode(红黑树)。Oracle决定使用以下规则使用这两个数据结构：–如果内部表中给定索引(存储桶)的节点超过8个，则链表转换为一棵红黑树 –如果给定索引(存储桶) )内部表中的节点少于6个，树被转换为链表
此图显示了JAVA 8 HashMap的内部数组，其中包含树(在存储桶0处)和链表(在存储桶1,2和3处)。值区0是一棵树，因为它有8个以上的节点。
内存开销
JAVA 7
HashMap的使用在内存方面要付出一定的代价。在JAVA 7中，HashMap将键值对包装在Entries中。条目具有：
- 对下一个条目的引用
- 预先计算的哈希(整数)
- 钥匙的参考
- 对值的引用
此外，JAVA 7 HashMap使用Entry的内部数组。假设JAVA 7 HashMap包含N个元素，并且其内部数组具有容量CAPACITY，则额外的内存开销约为：
sizeOf(整数)* N + sizeOf(参考)*(3 * N + C)
哪里：
- 整数的大小取决于4个字节
- 引用的大小取决于JVM / OS / Processor，但通常为4个字节。
这意味着开销通常为16 * N + 4 *容量字节
提醒：自动调整地图大小后，内部数组的容量等于N之后的下一个2的幂。
注意：从JAVA 7开始，HashMap类具有一个惰性的init。这意味着即使您分配了HashMap，条目的内部数组(花费4 * CAPACITY字节)也不会在内存中分配，直到第一次使用put()方法。
JAVA 8
使用JAVA 8实现时，获取内存使用情况变得有些复杂，因为Node可以包含与Entry相同的数据或相同的数据加上6个引用和一个布尔值(如果它是TreeNode)。
如果所有节点都是节点，则JAVA 8 HashMap的内存消耗与JAVA 7 HashMap相同。
如果所有节点都是TreeNodes，则JAVA 8 HashMap的内存消耗为：
N * sizeOf(整数)+ N * sizeOf(布尔值)+ sizeOf(引用)*(9 * N + CAPACITY)
在大多数标准JVM中，它等于44 * N + 4 *容量字节
性能问题
倾斜的HashMap与平衡良好的HashMap
在最佳情况下，get()和put()方法的时间复杂度为O(1)。但是，如果您不注意密钥的哈希函数，则可能会以非常慢的put()和get()调用结束。put()和get的良好性能取决于将数据重新分配到内部数组(存储桶)的不同索引中。如果您的键的哈希函数设计不当，您将有一个倾斜的分区(无论内部数组的容量有多大)。所有使用最大链接条目列表的put()和get()都会变慢，因为它们需要迭代整个列表。在最坏的情况下(如果大多数数据都在相同的存储桶中)，最终可能会带来O(n)的时间复杂度。这是一个视觉示例。第一张图片显示了倾斜的HashMap，第二张图片显示了均衡的图像。
在这种偏斜的HashMap的情况下，存储区0上的get()/ put()操作成本很高。获取条目K将花费6次迭代
在平衡良好的HashMap的情况下，获得条目K将花费3次迭代。两个HashMap都存储相同数量的数据，并且具有相同的内部数组大小。唯一的区别是(密钥的)哈希函数，用于在存储桶中分配条目。
这是JAVA中的一个极端示例，其中我创建了一个哈希函数，该函数将所有数据放入同一存储桶中，然后添加200万个元素。
public class Test {
public static void main(String[] args) {
class MyKey {
Integer i;
public MyKey(Integer i){
this.i =i;
}
@Override
public int hashCode() {
return 1;
}
@Override
public boolean equals(Object obj) {
…
}
}
Date begin = new Date();
Map myMap= new HashMap<>(2_500_000,1);for (int i=0;i<2_000_000;i++){
myMap.put( new MyKey(i), "test "+i);
}
Date end = new Date();
System.out.println("Duration (ms) "+ (end.getTime()-begin.getTime()));
}
}在我的核心i5-2500k @ 3.6Ghz上，使用Java 8u40需要超过45分钟(我在45分钟后停止了该过程)。
现在，如果我运行相同的代码，但是这次我使用以下哈希函数
@Override
public int hashCode() {
int key = 2097152-1;
return key+2097152*i;
}
需要46秒，这更好！此哈希函数的分区比上一个更好，因此put()调用更快。
如果我使用以下哈希函数运行相同的代码，则可以提供更好的哈希重新分区
@Override
public int hashCode() {
return i;
}
现在需要2秒钟。
我希望您认识到哈希函数的重要性。如果在JAVA 7上运行相同的测试，则对于第一种和第二种情况，结果会更糟(因为put的时间复杂度在JAVA 7中为O(n)与在Java 8中为O(log(n)))
使用HashMap时，您需要为密钥找到一个哈希函数，以将密钥散布到尽可能多的存储桶中。为此，您需要避免哈希冲突。字符串对象是一个很好的键，因为它具有良好的哈希功能。整数也很好，因为它们的哈希码是它们自己的值。
调整开销
如果需要存储大量数据，则应创建初始容量接近预期容量的HashMap。
如果不这样做，则Map的默认大小将为16，factorLoad为0.75。11个第一个put()将非常快，但是第12个(16 * 0.75)将重新创建一个新的内部数组(及其关联的链表/树)，其新容量为32。第13个到第23个将很快，但是第24个(32 * 0.75)将重新创建(再次)代价高昂的新表示形式，该表示形式将内部数组的大小加倍。内部调整大小操作将出现在put()的第48、96、192等处。在低音量下，内部阵列的完全恢复速度很快，但在高音量下，可能需要几秒钟到几分钟。通过最初设置您的期望大小，可以避免这些 昂贵的操作。
但是有一个缺点：如果您将数组大小设置得很高，例如2 ^ 28，而在数组中仅使用2 ^ 26个存储桶，则会浪费大量内存(在这种情况下，大约2 ^ 30个字节)。
结论
对于简单的用例，您不需要知道HashMaps的工作方式，因为您不会看到O(1)和O(n)或O(log(n))操作之间的区别。但是，最好了解最常用的数据结构之一的底层机制。此外，对于Java开发人员来说，这是一个典型的面试问题。
大量使用时，了解其工作原理并理解键的哈希函数的重要性就变得很重要。
我希望本文能帮助您对HashMap实现有一个深入的了解。
