Java HashSet和HashMap源码剖析
yibadao112
8年前
<h2>总体介绍</h2> <p>之所以把<em>HashSet</em>和<em>HashMap</em>放在一起讲解，是因为二者在Java里有着相同的实现，前者仅仅是对后者做了一层包装，也就是说<strong><em>HashSet</em>里面有一个<em>HashMap</em>（适配器模式）</strong>。因此本文将重点分析<em>HashMap</em>。</p> <p><em>HashMap</em>实现了<em>Map</em>接口，允许放入<code>null</code>元素，除该类未实现同步外，其余跟<code>Hashtable</code>大致相同，跟<em>TreeMap</em>不同，该容器不保证元素顺序，根据需要该容器可能会对元素重新哈希，元素的顺序也会被重新打散，因此不同时间迭代同一个<em>HashMap</em>的顺序可能会不同。<br> 根据对冲突的处理方式不同，哈希表有两种实现方式，一种开放地址方式（Open addressing），另一种是冲突链表方式（Separate chaining with linked lists）。<strong>Java <em>HashMap</em>采用的是冲突链表方式</strong>。<br> <img alt="Java HashSet和HashMap源码剖析" src="https://simg.open-open.com/show/c9616b75b2840001cc00a67a46a5d5cf.png" width="1200" height="1069"></p> <p>从上图容易看出，如果选择合适的哈希函数，<code>put()</code>和<code>get()</code>方法可以在常数时间内完成。但在对<em>HashMap</em>进行迭代时，需要遍历整个table以及后面跟的冲突链表。因此对于迭代比较频繁的场景，不宜将<em>HashMap</em>的初始大小设的过大。</p> <p>有两个参数可以影响<em>HashMap</em>的性能：初始容量（inital capacity）和负载系数（load factor）。初始容量指定了初始<code>table</code>的大小，负载系数用来指定自动扩容的临界值。当<code>entry</code>的数量超过<code>capacity*load_factor</code>时，容器将自动扩容并重新哈希。对于插入元素较多的场景，将初始容量设大可以减少重新哈希的次数。</p> <h2>方法剖析</h2> <h3>get()</h3> <p><code>get(Object key)</code>方法根据指定的<code>key</code>值返回对应的<code>value</code>，该方法调用了<code>getEntry(Object key)</code>得到相应的<code>entry</code>，然后返回<code>entry.getValue()</code>。因此<code>getEntry()</code>是算法的核心。<br> 算法思想是首先通过<code>hash()</code>函数得到对应<code>bucket</code>的下标，然后依次遍历冲突链表，通过<code>key.equals(k)</code>方法来判断是否是要找的那个<code>entry</code>。<br> <img alt="Java HashSet和HashMap源码剖析" src="https://simg.open-open.com/show/376d99960adbe5967be550643955948a.png" width="1200" height="947"><br> 上图中<code>hash(k)&(table.length-1)</code>等价于<code>hash(k)%table.length</code>，原因是<em>HashMap</em>要求<code>table.length</code>必须是2的指数，因此<code>table.length-1</code>就是二进制低位全是1，跟<code>hash(k)</code>相与会将哈希值的高位全抹掉，剩下的就是余数了。</p> <pre> <code class="language-java">//getEntry()方法 final Entry<K,V> getEntry(Object key) { int hash = (key == null) ? 0 : hash(key); for (Entry<K,V> e = table[hash&(table.length-1)];//得到冲突链表 e != null; e = e.next) {//依次遍历冲突链表中的每个entry Object k; //依据equals()方法判断是否相等 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; }</code></pre> <h3>put()</h3> <p><code>put(K key, V value)</code>方法是将指定的<code>key, value</code>对添加到<code>map</code>里。该方法首先会对<code>map</code>做一次查找，看是否包含该元组，如果已经包含则直接返回，查找过程类似于<code>getEntry()</code>方法；如果没有找到，则会通过</p> <p><code>addEntry(int hash, K key, V value, int bucketIndex)</code>方法插入新的<code>entry</code>，插入方式为<strong>头插法</strong>。<br> <img alt="Java HashSet和HashMap源码剖析" src="https://simg.open-open.com/show/cca17f8630779523d73004928887f201.png" width="1200" height="1002"></p> <pre> <code class="language-java">//addEntry() void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length);//自动扩容，并重新哈希 hash = (null != key) ? hash(key) : 0; bucketIndex = hash & (table.length-1);//hash%table.length } //在冲突链表头部插入新的entry Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<>(hash, key, value, e); size++; }</code></pre> <h3>remove()</h3> <p><code>remove(Object key)</code>的作用是删除<code>key</code>值对应的<code>entry</code>，该方法的具体逻辑是在<code>removeEntryForKey(Object key)</code>里实现的。<code>removeEntryForKey()</code>方法会首先找到<code>key</code>值对应的<code>entry</code>，然后删除该<code>entry</code>（修改链表的相应指针）。查找过程跟<code>getEntry()</code>过程类似。<br> <img alt="Java HashSet和HashMap源码剖析" src="https://simg.open-open.com/show/fdfff611a122b5428908b9cc8f4b93e7.png" width="1300" height="1033"></p> <pre> <code class="language-java">//removeEntryForKey() final Entry<K,V> removeEntryForKey(Object key) { int hash = (key == null) ? 0 : hash(key); int i = indexFor(hash, table.length);//hash&(table.length-1) Entry<K,V> prev = table[i];//得到冲突链表 Entry<K,V> e = prev; while (e != null) {//遍历冲突链表 Entry<K,V> next = e.next; Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {//找到要删除的entry modCount++; size--; if (prev == e) table[i] = next;//删除的是冲突链表的第一个entry else prev.next = next; return e; } prev = e; e = next; } return e; }</code></pre> <h2>HashSet</h2> <p>前面已经说过<em>HashSet</em>是对<em>HashMap</em>的简单包装，对<em>HashSet</em>的函数调用都会转换成合适的<em>HashMap</em>方法，因此<em>HashSet</em>的实现非常简单，只有不到300行代码。这里不再赘述。</p> <pre> <code class="language-java">//HashSet是对HashMap的简单包装 public class HashSet<E> { private transient HashMap<E,Object> map;//HashSet里面有一个HashMap // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); public HashSet() { map = new HashMap<>(); } public boolean add(E e) {//简单的方法转换 return map.put(e, PRESENT)==null; } }</code></pre> <p>来源：https://github.com/CarpenterLee/JCFInternals/blob/master/markdown/6-HashSet%20and%20HashMap.md</p>