[译]Java HashMap原理探究
bcjv0401
8年前
<p>相信每个JAVA开发者都用过Map，特别是HashMap。HashMap是一个简单但是强大的方式用于存储和获取数据。但是有多少人知道HashMap内部原理呢？前几天，为了深入理解这个基础数据结构，我阅读了java.util.HashMap（先阅读了Java7，然后看了Java8）中的大量的代码。在这篇文章中，我将详细解释java.util.HashMap的执行过程，以及目前在Java 8中的新的执行方式，并且探讨一下当使用HashMap时的性能、内存及已知的问题。</p> <h2>内部存储</h2> <p>Java的HashMap类实现了接口Map<K,V>。这个接口的主要方法引入下：</p> <p>1、V put(K key, V value)</p> <p>2、V get(Object key)</p> <p>3、V remove(Object key)</p> <p>4、Boolean containsKey(Object key)</p> <p>HashMap使用内部类Entry<K,V>来存储数据。这个条目是一个具备两个额外数据的键值对：</p> <p>1、一个对其它Entry的引用，这样HashMap就可以像单链表一样存储条目</p> <p>2、一个哈希值展示了键的哈西值。存储这个值目的在于避免每次HashMap需要这个值时进行重复计算。</p> <p>下面时在Java 7中Entry的部分实现：</p> <pre> <code class="language-java">static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash; … }</code></pre> <p> </p> <p>HashMap将数据存储到多个条目的单线性链表中（也称为桶或箱）。所有的列表注册到一个Entry的数组中（Entry<K,V>[] array），这个数组磨人的长度时16.</p> <p><img src="https://simg.open-open.com/show/28ba016afbaaa0bd2169d665798c59de.jpg"></p> <p>上面的图展示了一个存储带有空数组的HashMap实例的内部存储情况。每个条目相互连接，形成了一个链表。</p> <p>所有具有相同哈希值的键被放置到同一个链表（或称为桶）中。具备不同哈希值的键用完后会放置到相同的桶中。</p> <p>当开发者调用put(K key, V value)或者get(Object key)时，这些函数计算了这个条目应当在桶中的哪个位置（索引）。然后，函数迭代列表，找到与这个条目相同key的条目（使用了equals()对键进行比较）。</p> <p>在get()，该函数返回与该条目关联的值（如果条目存在）。</p> <p>在put(K key, V value)中，如果条目存在，则函数使用新值进行覆盖，否则就在单链表的头部创建一个新条目（使用参数中的键值）。</p> <p>Map生成桶（链表）索引分为以下三步：</p> <p>1、首先取得键的hashcode</p> <p>2、重新对hashcode生成哈希值，以此来避免不稳定的哈希函数会导致map将所有的数据放在了内部数组的相同索引位置（即相同的桶中）</p> <p>3、接着取得重新哈希的值，使用数组的长度减一与之进行位与操作。这个操作确保索引的生成不会大于数组长度。你也可以把它看作一个被计算优化的模块化函数。</p> <p>下列在Java 7和Java 8中与索引相关的源码：</p> <pre> <code class="language-java">// 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); }</code></pre> <p> </p> <p>为了能够有效的工作，内部数组的大小必须时2的幂，下面让我们一起看下为什么有这个要求。</p> <p>假设数组的大小是17，那么掩码值就需要是16（size-1）。代表16的二进制是0...010000，因此，对于任何哈希值H，使用按位与公式H AND 16计算得到的索引值要么是16要么是0.这就意味着长度为17的数组只能用于两个桶：索引值为0和索引值为16的桶——这样毕竟不是十分“高效”（译者注：压根就是浪费。）</p> <p>但是，如果数组大小是2的幂，比如16，则按位与计算索引的公式变成了H AND 15。而15的二进制是0...001111，所以索引公式可以输出从0到15的任意值，所以大小为16的数组就能被完全利用起来。比如：</p> <p>>如果H=952，它的二进制表示为0...01110111000，分配给它索引就是0...01000=8</p> <p>>如果H=1576，它的二进制表示为0...011000101000，分配给它索引就是0...01000=8</p> <p>>如果H=12356146，它的二进制表示为0...0101111001000101000110010，分配给它索引就是0...00010=2</p> <p>>如果H=59843，它的二进制表示为0...01110100111000011，分配给它的索引就是0...00011=3</p> <p>以上体现出来的就是为什么数组大小是2的幂值。这项机制对开发者来说是透明的：如果开发者创建了一个大小为37的HashMap，则Map会自动将37*2=64作为内部数组的大小。</p> <h2>自动调整大小</h2> <p>获得索引后，函数get(), put(), delete() 遍历或者循环遍历关联的链表，看看给定键是否有值。在没有修改的情况下，这种机制可能会造成性能问题，因为函数需要遍历整个链表来检查条目是否存在。想象一下，内部数组的大小是16，但是你需要存储200万个值。最理想的场景是每个链表均有125000个条目（2/16，单位：百万）。所以，每个get(),put(),delete()会导致125000次遍历操作。为了避免这种情况，HashMap有能力增加其内部数组数量，用来保持存储的链表不至过长。</p> <p>当你创建一个HashMap，你可以使用下面的构造函数指定initialCapacity（初始大小）和loadFactor（负载系数）：</p> <p>public HashMap(int initialCapacity, float loadFactor)</p> <p> </p> <p>如果你不指定上面的参数，则默认的initialCapacity=16，默认的loadFactor=0.75。initialCapacity表示了链表内部数组的大小。</p> <p>每次使用函数put(...)向Map中添加新的键值对时，函数首先检查是否需要扩充内部数组的大小。为了做到这一点，map存储了两个值： * map的尺寸：表示了HashMap中的条目数。每次添加或者移除条目时，这个值都会进行更新 * 阈值：阈值等于内部数组大小乘以负载系数，数值在每次内部数组重新分配大小之后刷新。</p> <p>在添加新条目之前，put(...)会检查如果数组大小大于阈值，则会创建一个具有两倍大小的新数组。因为新数组大小已经改变，所以索引函数（按位与操作hash(key) AND (sizeOfArrya-1)）改变了。因此，调整数组大小为之前的2倍意味着可以存储更多的桶（链表），接着重新把现有已存在的条目分配到桶中（这些桶有旧值也有新被创建的值）。</p> <p>扩容操作的目标在于减少链表的大小，因此来保持get(),put()和delete()函数较低的时间花费。扩容后，所有key具有相同哈希值得条目会放置在相同的桶中，但是两个具有不同哈希值的键的条目即使之前在相同的桶中，现在也不会被放置在相同的桶中了。</p> <p><img src="https://simg.open-open.com/show/80a47f9fc70c35af03a64e3a322e3c68.jpg"></p> <p>上图展现了内部数组调整大小前后的情况。在扩容前，为了得到条目E，map需要遍历链表中的5个元素，扩容后，相同的get()函数只需要遍历链表中的两个元素就可以得到条目E，扩容后get()比之前快了两倍多！</p> <p>注：HashMap仅提供增加内部数组的大小，不支持减少数组大小操作。</p> <h2>线程安全性</h2> <p>相信熟悉HashMap的开发者都了解，HashMap并不是线程安全的。但是为什么呢？想象一下你有一个写线程讲新值放入Map中，而另一个读线程在Map中读取数据，为什么不能正常工作呢？</p> <p>因为如果碰上自动扩容，如果线程尝试读或者写入对象，map可能会使用旧的索引，而不是找到条目应该在的新的桶。</p> <p>最坏的场景是两个线程同时向map中放置数据，然后两put()操作都同时调用了Map的扩容方法。因为两个线程在同一时间修改了链表，则Map很有可能在其内部链表之一中持续内部循环。如果你尝试在一个具有内部循环的Map中取数据，那么你得get()永远不会结束。</p> <p>HashTable是线程安全的实现，避免了上面提到的这种情况的发生。但是，因为CRUD所有操作都被synchronized修饰，则这种实现十分缓慢。比如，如果线程1调用了get(key1)，线程2调用了get(key2)，线程3调用了get(key3)，一次只能有一个线程取到其值，及时3个线程同时执行，同时找到数据。</p> <p>自从Java 5开始，存在了一个更聪明的线程安全的HashMap的实现：ConcurrentHashMap。只有桶是同步的，所以在不访问相同的桶或者扩容内部数组大小的情况下，Map支持多线程同时get(), remove()或者put()。在多线程应用中，使用这种实现显然是更好的选择</p> <h2>键的不可变性</h2> <p>为什么字符类型和整数型适合做为HashMap的键？绝大部分的原因在于它们是不可变的！如果你选择创建自己的Key类，并且不把它设为为不可变的，则在使用HashMap时，你可能会丢失数据。</p> <p>看下面的使用案例：</p> <p>1、你有一个内部值为1的键</p> <p>2、使用这个Key，向HashMap中put一个对象</p> <p>3、HashMap以用这个Key（这里值为1）生成一个哈希值</p> <p>4、Map在新创建的条目中存储了这个哈希值</p> <p>5、修改Key的内部值为2</p> <p>6、键的哈希值被修改，但是HashMap并不知情（因为旧的哈希值已经被存储起来了）</p> <p>7、你尝试使用修改后的Key去HashMap中获取对象</p> <p>8、map尝试用新的Key的哈希值去找条目在哪个链表里</p> <p>情况1：由于Key被修改，所以Map尝试在错误的桶中寻找条目，却没有找到</p> <p>情况2：修改后的Key和修改前的Key生成的桶是同一个。Map遍历链表，去找有相同Key的这个条目。但是为了找到相同的Key，Map首先比较两者的哈希值，然后调用equals()进行比较。由于修改后的Key哈希值已经和旧值不同，则Map没办法在链表中找到条目。</p> <p>这里有一个在Java中的具体例子。我在Map中放置了两个键值对，修改了第一个Key，然后尝试获取这二个值。只有第二个值成功返回，第一个值丢失在HashMap中：</p> <pre> <code class="language-java">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); } }</code></pre> <p> </p> <p>输出是"test1= null test2=test 2"。正如预想的那样，Map不能使用修改后的key去遍历得到它的值。</p> <h2>Java 8 中的改进</h2> <p>在Java8中，HashMap的内部表现形式改变了很多。事实上，Java7中的实现大约是1k行代码，而Java8中得实现大约是2k行代码。上面提到的内容除了条目的链表，其他基本上都是正确的。在Java8中，你仍然有一个数组，但是现在它存储了Node，Node就像Entry一样，存储了相同的信息，所以仍然是一个链表： 下面是Java8中部分Node的实现代码：</p> <pre> <code class="language-java">static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next;</code></pre> <p>那么到底与Java7中最大的不同在哪里呢？答案是Node现在可以继承TreeNode。一个TreeNode是一个红黑树结构，存储了足够多得信息，所以能在O(long(n))的复杂度下添加、删除和获取一个元素。</p> <p>另外值得一提，下面是TreeNode内部存储的详尽的数据列表：</p> <pre> <code class="language-java">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;</code></pre> <p> </p> <p>红黑树是自平衡二叉查找树。他们的内部机制确保了无论是添加新的节点还是移除节点，长度总能保证在log(n)。使用树的最大优势在于万一在内部表中相同索引的桶中存储了大量的数据，使用树的搜索仅需要O(long(n))的复杂度，而链表搜索的复杂度为O(n)。</p> <p>正如你看到的那样，树结构比链表使用了更多的空间，这点，我们在下一部分详细讨论。</p> <p>通过继承，内部表可以同时包含Node（链表）和TreeNode（红黑树）。Oracle决定按照下面的规则使用两个数据结构：</p> <p>1、对于内部表中给定索引位置的桶超过8个节点，则链表转换成红黑树</p> <p>2、对于内部表中给定索引位置的桶低于6个节点，则树会被转换链表</p> <p><img src="https://simg.open-open.com/show/195c998512542c3448aca2a4d9aacfca.jpg"></p> <p>上图展示了在Java8中一个HashMap内部既有树（0号桶）又有链表（1、2、3号桶）的情况。桶0是树因为它有超过8个节点。</p> <h2>内存开销</h2> <h3>Java 7中</h3> <p>使用HashMap的代价全在内存。在Java 7中，一个HashMap将键值对包在条目中。一个条目具有：</p> <p>1、一个对下一个条目的引用</p> <p>2、一个预先计算过的哈希值（整形）</p> <p>3、一个对key的引用</p> <p>4、一个对value的引用</p> <p>此外，Java7的HashMap使用内部条目数组。假设在Java7中一个HashMap包含N个元素，其内部数组的容量为CAPACITY，则额外的内存开销大约是：</p> <p>sizeOf(integer)* N + sizeOf(reference)* (3*N+C)</p> <p>这里：</p> <p>1、一个整形的大小是4个字节</p> <p>2、引用的大小要看JVM、操作系统和处理器，但是通常是4个字节</p> <p>这就意味着开销通常是 16 * N + 4 * CAPACITY个字节。</p> <p>提示：在Map扩容后，内部数组的CAPACITY等于N的下一个是2的幂的数字。</p> <p>备注：自从Java7开始，HashMap类有懒加载。也就意味着及时你分配了一个HashMap，内部条目数组在不使用put()方法放置对象时是不会被分配内存的。</p> <h3>Java 8中</h3> <p>在Java8的实现中，估算内存使用变得有点复杂，因为一个Node可以和一个条目一样存储相同的数据，也可能要加上6个引用和一个布尔值（如果节点是一个TreeNode）。</p> <p>如果所有的节点都是Node，那么Java8的HashMap的内存消耗和Java7中得HashMap应当是一样的。</p> <p>如果所有的节点都是TreeNode，那么Java8中得HashMap得内存消耗则变成了： N * sizeOf(integer) + N * sizeOf(boolean) + sizeOf(reference)* (9*N+CAPACITY ) 在大多数标准的JVM中，通畅等于44 * N + 4 * CAPACITY个字节。</p> <h2>性能问题</h2> <p>倾斜的HashMap vs 平衡的HashMap</p> <p>最好的场景中，get()和put()方法均耗费O(1)的时间复杂度。但是，如果不注意键的哈希函数，则最终你可能在执行put()和get()时十分缓慢。性能良好的put()和get()取决于数据重新分配到不同索引的内部数组中。如果键的哈希函数设计不良，则可能会产生倾斜的重新分区（无论内部数组的容量有多大），所有与最长的链表打交道的put()和get()因为要便利整个链表，所以会变得很慢。在最坏的情况下（即所有的数据被放置在同一个桶中），时间复杂度就变成了O(n)。</p> <p>下面是一个图例，第一幅图展示了一个倾斜的HashMap，第二张图展示了一个平衡的HashMap。</p> <p><img src="https://simg.open-open.com/show/3f04ca9a3ac10dd9316dfd23d5e754f8.jpg"></p> <p>在这个倾斜的HashMap中，在0号桶执行get()和put()操作花费十分昂贵。得到条目K需要6次迭代。</p> <p><img src="https://simg.open-open.com/show/195a94b4b06eac3a120d0144b795e3f7.jpg"></p> <p>在这个平衡的HashMap中，取得条目K仅需要3次迭代。两个HashMap存储的相同的数据，并且内部数组大小一样。唯一的区别在于键的哈希函数不同导致桶中条目的分布不同。</p> <p>下面是一个极端的示例代码，这段代码中，我创建了一个哈希函数，将所有的数据放置在同一个桶中，然后我向桶中添加了200万个元素。</p> <pre> <code class="language-java">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())); } }</code></pre> <p> </p> <p>在我配置为i5-2500k @ 3.6GHz的电脑上，使用Java 8u40，耗时超过了45分钟（45分钟后我停止了这个进程）。</p> <p>现在，如果使用相同的代码，只不过将哈希函数修改为下面的代码：</p> <p>@Override public int hashCode() { int key = 2097152-1; return key+2097152*i; } 则仅需要46s，简直是巨大的进步！这个哈希函数比之前的函数具有更好的分配方案，所以put()的调用更快。</p> <p>当我使用下面的哈希函数运行相同的代码：</p> <p>@Override public int hashCode() { return i; }</p> <p>仅需2s！</p> <p>我希望你能通过上面的例子意识到哈希函数的重要性。如果使用相同的例子在Java7中运行，结果会更差，因为在Java7中put()得时间复杂度是O(n)而在Java8中则是O(log(n))。</p> <p>当使用HashMap是，你需要找到一个合适的哈希函数，将你的键尽可能分配到最多的桶中。为了做到这个，你需要避免哈希碰撞。String类型的对象是键的很好选择，因为它有不错的哈希函数。整形也不错，因为它的哈希值就是他们自己本身的值。</p> <h2>调整大小的开销</h2> <p>如果你需要存储大量的数据，你应该在创建HashMap时指定初始化容量为你期待的值。</p> <p>如果你不这样做，Map会默认大小为16，负载率为0.75.那么前11个put()操作会很快，而第12个（16x0.75）会创建一个新的内部数组（关联之前的链表或者树），大小为32.那么第13到23个put()操作也会很快，但是第24个操作（32x0.75）又会花费昂贵来为内部数组的大小加倍。内部大小的调整操作会在第48、96、192...个put()操作调用时产生。当内部数组大小较小时，调整大小很快，但是当内部数组的容量不断扩大，重新调整大小的耗时会由秒级到分钟级。所以初始化期待的大小，可以避免这样昂贵的操作。</p> <p>当然这样做也有缺点，如果你设置数组的大小非常大，比如2^28，而实际上仅仅使用了2^26个桶，那么会浪费大量的内存（大约为2^30个字节）。</p> <h2>结论</h2> <p>对于简单的使用，你不需要知道HashMap的内部原理，因为你根本不会体会到O(1)、O（n）和O(log(n))操作的不同。但是了解一下常用数据结构内部机制总是更好的一件事情。另外，对于Java开发者来说，这也是一个典型的面试题。</p> <p>在大数据量的情况下，了解哈希函数的内部原理和重要性是十分重要的。</p> <p>我希望本文能帮助你对HashMap的实现有个更深的认识。</p> <p> </p> <p>来自： <a href="/misc/goto?guid=4959674619705077628" rel="nofollow">http://www.jointforce.com/jfperiodical/article/2037</a></p> <p> </p>