[译]Java HashMap原理探究

相信每个JAVA开发者都用过Map，特别是HashMap。HashMap是一个简单但是强大的方式用于存储和获取数据。但是有多少人知道HashMap内部原理呢？前几天，为了深入理解这个基础数据结构，我阅读了java.util.HashMap（先阅读了Java7，然后看了Java8）中的大量的代码。在这篇文章中，我将详细解释java.util.HashMap的执行过程，以及目前在Java 8中的新的执行方式，并且探讨一下当使用HashMap时的性能、内存及已知的问题。

HashMap使用内部类Entry<K,V>来存储数据。这个条目是一个具备两个额外数据的键值对：

下面时在Java 7中Entry的部分实现：

static class Entry<K,V> implements Map.Entry<K,V> {   final K key;   V value;   Entry<K,V> next;   int hash;  …  }

HashMap将数据存储到多个条目的单线性链表中（也称为桶或箱）。所有的列表注册到一个Entry的数组中（Entry<K,V>[] array），这个数组磨人的长度时16.

上面的图展示了一个存储带有空数组的HashMap实例的内部存储情况。每个条目相互连接，形成了一个链表。

所有具有相同哈希值的键被放置到同一个链表（或称为桶）中。具备不同哈希值的键用完后会放置到相同的桶中。

当开发者调用put(K key, V value)或者get(Object key)时，这些函数计算了这个条目应当在桶中的哪个位置（索引）。然后，函数迭代列表，找到与这个条目相同key的条目（使用了equals()对键进行比较）。

在get()，该函数返回与该条目关联的值（如果条目存在）。

在put(K key, V value)中，如果条目存在，则函数使用新值进行覆盖，否则就在单链表的头部创建一个新条目（使用参数中的键值）。

Map生成桶（链表）索引分为以下三步：

下列在Java 7和Java 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（size-1）。代表16的二进制是0...010000，因此，对于任何哈希值H，使用按位与公式H AND 16计算得到的索引值要么是16要么是0.这就意味着长度为17的数组只能用于两个桶：索引值为0和索引值为16的桶——这样毕竟不是十分“高效”（译者注：压根就是浪费。）

但是，如果数组大小是2的幂，比如16，则按位与计算索引的公式变成了H AND 15。而15的二进制是0...001111，所以索引公式可以输出从0到15的任意值，所以大小为16的数组就能被完全利用起来。比如：

以上体现出来的就是为什么数组大小是2的幂值。这项机制对开发者来说是透明的：如果开发者创建了一个大小为37的HashMap，则Map会自动将37*2=64作为内部数组的大小。

当你创建一个HashMap，你可以使用下面的构造函数指定initialCapacity（初始大小）和loadFactor（负载系数）：

每次使用函数put(...)向Map中添加新的键值对时，函数首先检查是否需要扩充内部数组的大小。为了做到这一点，map存储了两个值： * map的尺寸：表示了HashMap中的条目数。每次添加或者移除条目时，这个值都会进行更新 * 阈值：阈值等于内部数组大小乘以负载系数，数值在每次内部数组重新分配大小之后刷新。

在添加新条目之前，put(...)会检查如果数组大小大于阈值，则会创建一个具有两倍大小的新数组。因为新数组大小已经改变，所以索引函数（按位与操作hash(key) AND (sizeOfArrya-1)）改变了。因此，调整数组大小为之前的2倍意味着可以存储更多的桶（链表），接着重新把现有已存在的条目分配到桶中（这些桶有旧值也有新被创建的值）。

扩容操作的目标在于减少链表的大小，因此来保持get(),put()和delete()函数较低的时间花费。扩容后，所有key具有相同哈希值得条目会放置在相同的桶中，但是两个具有不同哈希值的键的条目即使之前在相同的桶中，现在也不会被放置在相同的桶中了。

上图展现了内部数组调整大小前后的情况。在扩容前，为了得到条目E，map需要遍历链表中的5个元素，扩容后，相同的get()函数只需要遍历链表中的两个元素就可以得到条目E，扩容后get()比之前快了两倍多！

注：HashMap仅提供增加内部数组的大小，不支持减少数组大小操作。

因为如果碰上自动扩容，如果线程尝试读或者写入对象，map可能会使用旧的索引，而不是找到条目应该在的新的桶。

最坏的场景是两个线程同时向map中放置数据，然后两put()操作都同时调用了Map的扩容方法。因为两个线程在同一时间修改了链表，则Map很有可能在其内部链表之一中持续内部循环。如果你尝试在一个具有内部循环的Map中取数据，那么你得get()永远不会结束。

HashTable是线程安全的实现，避免了上面提到的这种情况的发生。但是，因为CRUD所有操作都被synchronized修饰，则这种实现十分缓慢。比如，如果线程1调用了get(key1)，线程2调用了get(key2)，线程3调用了get(key3)，一次只能有一个线程取到其值，及时3个线程同时执行，同时找到数据。

自从Java 5开始，存在了一个更聪明的线程安全的HashMap的实现：ConcurrentHashMap。只有桶是同步的，所以在不访问相同的桶或者扩容内部数组大小的情况下，Map支持多线程同时get(), remove()或者put()。在多线程应用中，使用这种实现显然是更好的选择

看下面的使用案例：

1、你有一个内部值为1的键

2、使用这个Key，向HashMap中put一个对象

3、HashMap以用这个Key（这里值为1）生成一个哈希值

4、Map在新创建的条目中存储了这个哈希值

5、修改Key的内部值为2

6、键的哈希值被修改，但是HashMap并不知情（因为旧的哈希值已经被存储起来了）

7、你尝试使用修改后的Key去HashMap中获取对象

这里有一个在Java中的具体例子。我在Map中放置了两个键值对，修改了第一个Key，然后尝试获取这二个值。只有第二个值成功返回，第一个值丢失在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<MyKey, String> 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不能使用修改后的key去遍历得到它的值。

static class Node<K,V> implements Map.Entry<K,V> {         final int hash;         final K key;         V value;         Node<K,V> next;

那么到底与Java7中最大的不同在哪里呢？答案是Node现在可以继承TreeNode。一个TreeNode是一个红黑树结构，存储了足够多得信息，所以能在O(long(n))的复杂度下添加、删除和获取一个元素。

另外值得一提，下面是TreeNode内部存储的详尽的数据列表：

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {  final int hash; // inherited from Node<K,V>  final K key; // inherited from Node<K,V>  V value; // inherited from Node<K,V>  Node<K,V> next; // inherited from Node<K,V>  Entry<K,V> before, after;// inherited from LinkedHashMap.Entry<K,V>  TreeNode<K,V> parent;  TreeNode<K,V> left;  TreeNode<K,V> right;  TreeNode<K,V> prev;  boolean red;

红黑树是自平衡二叉查找树。他们的内部机制确保了无论是添加新的节点还是移除节点，长度总能保证在log(n)。使用树的最大优势在于万一在内部表中相同索引的桶中存储了大量的数据，使用树的搜索仅需要O(long(n))的复杂度，而链表搜索的复杂度为O(n)。

正如你看到的那样，树结构比链表使用了更多的空间，这点，我们在下一部分详细讨论。

通过继承，内部表可以同时包含Node（链表）和TreeNode（红黑树）。Oracle决定按照下面的规则使用两个数据结构：

上图展示了在Java8中一个HashMap内部既有树（0号桶）又有链表（1、2、3号桶）的情况。桶0是树因为它有超过8个节点。

内存开销

这里：

1、一个整形的大小是4个字节

2、引用的大小要看JVM、操作系统和处理器，但是通常是4个字节

这就意味着开销通常是 16 * N + 4 * CAPACITY个字节。

提示：在Map扩容后，内部数组的CAPACITY等于N的下一个是2的幂的数字。

备注：自从Java7开始，HashMap类有懒加载。也就意味着及时你分配了一个HashMap，内部条目数组在不使用put()方法放置对象时是不会被分配内存的。

如果所有的节点都是Node，那么Java8的HashMap的内存消耗和Java7中得HashMap应当是一样的。

如果所有的节点都是TreeNode，那么Java8中得HashMap得内存消耗则变成了： N * sizeOf(integer) + N * sizeOf(boolean) + sizeOf(reference)* (9*N+CAPACITY ) 在大多数标准的JVM中，通畅等于44 * N + 4 * CAPACITY个字节。

性能问题

最好的场景中，get()和put()方法均耗费O(1)的时间复杂度。但是，如果不注意键的哈希函数，则最终你可能在执行put()和get()时十分缓慢。性能良好的put()和get()取决于数据重新分配到不同索引的内部数组中。如果键的哈希函数设计不良，则可能会产生倾斜的重新分区（无论内部数组的容量有多大），所有与最长的链表打交道的put()和get()因为要便利整个链表，所以会变得很慢。在最坏的情况下（即所有的数据被放置在同一个桶中），时间复杂度就变成了O(n)。

下面是一个图例，第一幅图展示了一个倾斜的HashMap，第二张图展示了一个平衡的HashMap。

在这个倾斜的HashMap中，在0号桶执行get()和put()操作花费十分昂贵。得到条目K需要6次迭代。

在这个平衡的HashMap中，取得条目K仅需要3次迭代。两个HashMap存储的相同的数据，并且内部数组大小一样。唯一的区别在于键的哈希函数不同导致桶中条目的分布不同。

下面是一个极端的示例代码，这段代码中，我创建了一个哈希函数，将所有的数据放置在同一个桶中，然后我向桶中添加了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 <MyKey,String> 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; } 则仅需要46s，简直是巨大的进步！这个哈希函数比之前的函数具有更好的分配方案，所以put()的调用更快。

当我使用下面的哈希函数运行相同的代码：

@Override public int hashCode() { return i; }

仅需2s！

我希望你能通过上面的例子意识到哈希函数的重要性。如果使用相同的例子在Java7中运行，结果会更差，因为在Java7中put()得时间复杂度是O(n)而在Java8中则是O(log(n))。

当使用HashMap是，你需要找到一个合适的哈希函数，将你的键尽可能分配到最多的桶中。为了做到这个，你需要避免哈希碰撞。String类型的对象是键的很好选择，因为它有不错的哈希函数。整形也不错，因为它的哈希值就是他们自己本身的值。

如果你不这样做，Map会默认大小为16，负载率为0.75.那么前11个put()操作会很快，而第12个（16x0.75）会创建一个新的内部数组（关联之前的链表或者树），大小为32.那么第13到23个put()操作也会很快，但是第24个操作（32x0.75）又会花费昂贵来为内部数组的大小加倍。内部大小的调整操作会在第48、96、192...个put()操作调用时产生。当内部数组大小较小时，调整大小很快，但是当内部数组的容量不断扩大，重新调整大小的耗时会由秒级到分钟级。所以初始化期待的大小，可以避免这样昂贵的操作。

当然这样做也有缺点，如果你设置数组的大小非常大，比如2^28，而实际上仅仅使用了2^26个桶，那么会浪费大量的内存（大约为2^30个字节）。

在大数据量的情况下，了解哈希函数的内部原理和重要性是十分重要的。

我希望本文能帮助你对HashMap的实现有个更深的认识。