java源码-HashMap

开篇

这篇文章的主要是想把HashMap进行一个讲解，在上一篇java源码-HashSet当中其实已经提到过了一点点HashMap的源码实现了，这篇文章会更加详细的进行讲解，顺带会讲解一些比较奇妙的源码实现。

HashMap类图

数据结构

在jdk1.8的HashMap的数据结构当中我们看到很多定义的常量基本上和扩容相关的：

• 核心变量table变量用于保存HashMap的变量
• size用于保存HashMap中变量的值，
• modCount用于记录变更次数便于遍历的时候抛异常
  在源码当中我们用transient变量修饰table变量，那序列化怎么办？其实HashMap自行定义了序列化接口，参考《Java中HashMap关键字transient的疑惑》。

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { private static final long serialVersionUID = 362498820763181265L; // 初始容量，也就是默认会创建 16 个箱子，箱子的个数不能太多或太少。如果太少，很容易触发扩容，如果太多，遍历哈希表会比较慢。 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 // 哈希表最大容量，一般情况下只要内存够用，哈希表不会出现问题。 static final int MAXIMUM_CAPACITY = 1 << 30; // 默认的负载因子。因此初始情况下，当键值对的数量大于 16 * 0.75 = 12 时，就会触发扩容。 static final float DEFAULT_LOAD_FACTOR = 0.75f; // Java的处理方案是当链表太长时，转换成红黑树。这个值表示当某个箱子中，链表长度大于 8 时，有可能会转化成树。 static final int TREEIFY_THRESHOLD = 8; // 在哈希表扩容时，如果发现链表长度小于 6，则会由树重新退化为链表。 static final int UNTREEIFY_THRESHOLD = 6; // 在转变成树之前，还会有一次判断，只有键值对数量大于 64 才会发生转换。这是为了避免在哈希表建立初期，多个键值对恰好被放入了同一个链表中而导致不必要的转化。 static final int MIN_TREEIFY_CAPACITY = 64; // hash桶的数组 transient Node<K,V>[] table; transient Set<Map.Entry<K,V>> entrySet; // 变量的个数 transient int size; // HashMap的变更次数 transient int modCount; // HashMap的hash桶的数量 int threshold; // HashMap的负载因子 final float loadFactor; 

构造函数

HashMap的构造函数执行的操作非常简单，就是初始化两个核心变量loadFactor和threshold。不过这里有一个非常巧妙的实现tableSizeFor方法，那就是计算比initialCapacity大且最接近的的2*n的变量。
tableSizeFor方法的核心思想通过位操作 依次 将最高位为1的HashMap的后2位(包括高位的1)，后4位(包括高位的1)，后8位(包括高位的1)，后16位(包括高位的1)，最后形成类似0111111111+1=10000000的变量值就得到了2 * n变量。

public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); } /** * Returns a power of two size for the given target capacity. */ static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; } 

Node的数据结构是实实在在保存Map的key/value结构的变量，内部除了保存key、value的变量外，还有key的对应的hash值，以及指向下一个Node指针，就这些。

static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } } 

增删改查

添加变量

在HashMap内部真正执行的是putVal()方法，在putVal()的内部执行其实按照以下顺序执行的。

• 如果HashMap内部的桶数组没有初始化就创建一个桶数组
• 通过hash值找到桶下标，如果对应位置为空就直接创建一个Node节点newNode
• 通过hash值找到桶下标，如果对于位置不为空那么就直接比较key是否相等，如果相等就直接返回，如果遍历完成后都没有找到那么在链表的最后连接一个新创的节点
• 在新增节点后判断是否超过上限需要进行resize动作，resize()函数也是一个很有意思的过程，这个放到HashMap当中去分析吧
• ++modCount这个会记录值的变更然后通过比较值抛出更改异常

 public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } 

remove()方法

HashMap的remove方法内部逻辑通过对key进行hash定位到hash桶的下标，然后遍历桶下面的列表节点通过比较key是否相同进行删除。
删除后同样会--size减少size，更新 ++modCount。

 public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { Node<K,V>[] tab; Node<K,V> p; int n, index; if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { Node<K,V> node = null, e; K k; V v; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) node = p; else if ((e = p.next) != null) { if (p instanceof TreeNode) node = ((TreeNode<K,V>)p).getTreeNode(hash, key); else { do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { node = e; break; } p = e; } while ((e = e.next) != null); } } if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { if (node instanceof TreeNode) ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); else if (node == p) tab[index] = node.next; else p.next = node.next; ++modCount; --size; afterNodeRemoval(node); return node; } } return null; } 

clear()方法

HashMap的内部clear当中就是直接把HashMap的桶的值的每个下标的值为null就可以了，估计内部会进行垃圾回收？

public void clear() { Node<K,V>[] tab; modCount++; if ((tab = table) != null && size > 0) { size = 0; for (int i = 0; i < tab.length; ++i) tab[i] = null; } } 

contains()方法

HashMap的containsKey方法来判断key是否存在，而containsKey内部通过根据key的hash值，通过计算的hash值找到table的槽位，如果第一个元素的key就是查询的key就直接返回，否则就依次遍历冲突链逐个进行比较解决。
这里需要说明的就是hash方法内部其实就是对key取了个hashcode()的值。

 public boolean containsKey(Object key) { return getNode(hash(key), key) != null; } final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; } 

resize()方法

HashMap的resize()方法是整个HashMap当中最值得仔细分析的逻辑，在jdk1.7和jdk1.8两个版本当中实现非常不一样，在jdk1.7当中会造成死循环，而在jdk1.8当中已经不会造成死循环了，这点完全可以用来考考那种号称看了jdk1.8源码的童鞋，为什么会造成死循环请继续往下看。HashMap的扩展过程如下：

• HashMap的resize以2倍的速率进行扩展(newCap = oldCap << 1)
• 遍历oldTab的所有变量重新rehash到newTab当中，rehash过程设计非常巧妙
• rehash过程针对每个hash桶进行，针对每个hash桶里面的变量，我们按照原来的顺序生成loHead和loTail，或按照原来的顺序生成hiHead或hiTail，然后整体挂到newTab当中
• 我个人认为在jdk1.8当中这种按照原来的顺序生成的过程保证了不会形成死循环。

final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; } 

迭代器Iterator

在HashMap的数据结构当中，有三类迭代器分别是KeySet、Values、EntrySet。通过源码看了以后就会发现这三者的实现其实基本上是一致的，核心的关键点在于 HashIterator 的设计。其他的差别就是从Node节点的取数对象不一致，有的取的是key，有的取的是value，有的取的是整个Node对象。
在调用map.keySet()或者map.values()或者map.entrySet()方法时，我们都会创建KeySet对象，Values对象，EntrySet对象，但是这些不是重点，重点是这些对象提供一个iterator方法。
在KeySet对象的返回的是KeyIterator对象，在Values对象返回的是ValueIterator对象，在EntrySet对象返回的是EntryIterator对象。
在KeyIterator、ValueIterator、EntryIterator初始化过程中，她们会首先初始化共有的基类HashIterator，在HashIterator的构造函数当中，会把当前map的table对象放入到迭代器当中，所有的操作就在这个HashIterator的内部执行的。
HashIterator的nextNode()方法内部，按照二维的方向进行遍历，先遍历一个hash桶下所有的Node，遍历完以后继续遍历下一个hash桶的所有Node，直至遍历完成。

 public Set<K> keySet() { Set<K> ks = keySet; if (ks == null) { ks = new KeySet(); keySet = ks; } return ks; } final class KeySet extends AbstractSet<K> { public final int size() { return size; } public final void clear() { HashMap.this.clear(); } public final Iterator<K> iterator() { return new KeyIterator(); } public final boolean contains(Object o) { return containsKey(o); } public final boolean remove(Object key) { return removeNode(hash(key), key, null, false, true) != null; } public final Spliterator<K> spliterator() { return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0); } public final void forEach(Consumer<? super K> action) { Node<K,V>[] tab; if (action == null) throw new NullPointerException(); if (size > 0 && (tab = table) != null) { int mc = modCount; for (int i = 0; i < tab.length; ++i) { for (Node<K,V> e = tab[i]; e != null; e = e.next) action.accept(e.key); } if (modCount != mc) throw new ConcurrentModificationException(); } } } final class KeyIterator extends HashIterator implements Iterator<K> { public final K next() { return nextNode().key; } } 

 public Collection<V> values() { Collection<V> vs = values; if (vs == null) { vs = new Values(); values = vs; } return vs; } final class Values extends AbstractCollection<V> { public final int size() { return size; } public final void clear() { HashMap.this.clear(); } public final Iterator<V> iterator() { return new ValueIterator(); } public final boolean contains(Object o) { return containsValue(o); } public final Spliterator<V> spliterator() { return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0); } public final void forEach(Consumer<? super V> action) { Node<K,V>[] tab; if (action == null) throw new NullPointerException(); if (size > 0 && (tab = table) != null) { int mc = modCount; for (int i = 0; i < tab.length; ++i) { for (Node<K,V> e = tab[i]; e != null; e = e.next) action.accept(e.value); } if (modCount != mc) throw new ConcurrentModificationException(); } } } final class ValueIterator extends HashIterator implements Iterator<V> { public final V next() { return nextNode().value; } } 

public Set<Map.Entry<K,V>> entrySet() { Set<Map.Entry<K,V>> es; return (es = entrySet) == null ? (entrySet = new EntrySet()) : es; } final class EntrySet extends AbstractSet<Map.Entry<K,V>> { public final int size() { return size; } public final void clear() { HashMap.this.clear(); } public final Iterator<Map.Entry<K,V>> iterator() { return new EntryIterator(); } public final boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry<?,?> e = (Map.Entry<?,?>) o; Object key = e.getKey(); Node<K,V> candidate = getNode(hash(key), key); return candidate != null && candidate.equals(e); } public final boolean remove(Object o) { if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>) o; Object key = e.getKey(); Object value = e.getValue(); return removeNode(hash(key), key, value, true, true) != null; } return false; } public final Spliterator<Map.Entry<K,V>> spliterator() { return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0); } public final void forEach(Consumer<? super Map.Entry<K,V>> action) { Node<K,V>[] tab; if (action == null) throw new NullPointerException(); if (size > 0 && (tab = table) != null) { int mc = modCount; for (int i = 0; i < tab.length; ++i) { for (Node<K,V> e = tab[i]; e != null; e = e.next) action.accept(e); } if (modCount != mc) throw new ConcurrentModificationException(); } } } final class EntryIterator extends HashIterator implements Iterator<Map.Entry<K,V>> { public final Map.Entry<K,V> next() { return nextNode(); } } 

abstract class HashIterator { Node<K,V> next; // next entry to return Node<K,V> current; // current entry int expectedModCount; // for fast-fail int index; // current slot HashIterator() { expectedModCount = modCount; Node<K,V>[] t = table; current = next = null; index = 0; if (t != null && size > 0) { // advance to first entry do {} while (index < t.length && (next = t[index++]) == null); } } public final boolean hasNext() { return next != null; } final Node<K,V> nextNode() { Node<K,V>[] t; Node<K,V> e = next; if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (e == null) throw new NoSuchElementException(); if ((next = (current = e).next) == null && (t = table) != null) { do {} while (index < t.length && (next = t[index++]) == null); } return e; } public final void remove() { Node<K,V> p = current; if (p == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); current = null; K key = p.key; removeNode(hash(key), key, null, false, false); expectedModCount = modCount; } } 

jdk1.7 VS jdk1.8 HashMap的对比

先说一个结论说明jdk1.7和jdk1.8版本下HashMap实现的区别：

• 在jdk1.7当中HashMap在多线程并发写的场景下会出现死循环，而jdk1.8当中已经没有死循环的问题了。
• jdk1.8当中对于挂链冲突的问题上，会采用红黑树进行优化，也就是在同一个hash桶下Node的数量超过阈值后会自动升级为红黑树，反之就降级为链表。
• 不管在jdk的哪个版本下HashMap都不是线程安全的

jdk1.7 HashMap并发写死锁问题

void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; ...... // 创建一个新的 Hash Table Entry[] newTable = new Entry[newCapacity]; // 将 Old Hash Table 上的数据迁移到 New Hash Table 上 transfer(newTable); table = newTable; threshold = (int)(newCapacity * loadFactor); } void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; //下面这段代码的意思是： // 从OldTable里摘一个元素出来，然后放到NewTable中 for (int j = 0; j < src.length; j++) { Entry<K,V> e = src[j]; if (e != null) { src[j] = null; do { Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } } 

正常Hash过程

说明：

• rehash的挂链过程采取的是重新hash然后通过倒挂链的方法挂到新的HashMap当中。
• 因为倒挂链的实现是造成死循环的本因。

并发下的 Rehash

void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; ...... // 创建一个新的 Hash Table Entry[] newTable = new Entry[newCapacity]; // 将 Old Hash Table 上的数据迁移到 New Hash Table 上 transfer(newTable); table = newTable; threshold = (int)(newCapacity * loadFactor); } void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; //下面这段代码的意思是： // 从OldTable里摘一个元素出来，然后放到NewTable中 for (int j = 0; j < src.length; j++) { Entry<K,V> e = src[j]; if (e != null) { src[j] = null; do { Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } } 

假设有两个线程

do { Entry<K,V> next = e.next; // 假设线程一执行到这里就被调度挂起了 int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); 

而线程二执行完成了。于是有下面的这个样子。

说明：

• 因为 Thread1 的 e 指向了 key(3)，而 next 指向了 key(7)，其在线程二 rehash 后，指向了线程二重组后的链表。
• 在rehash后的线程二当中e指向key(3)，next指向key(7)只是为了指示一下，实际上并没有这种情况存在
• 后续的操作是在线程二rehash后的数组上进行的，注意是在rehash后的数组上进行的

说明：

• 线程一被调度回来执行，先是执行 newTalbe[i] = e;然后是 e = next，导致了 e 指向了 key(7)。这里是因为在第一步的时候next已经指向Key(7)
• 而下一次循环的 next = e.next 导致了 next 指向了 key(3)，这里是因为线程二rehash后的HashMap采用倒链插入法所以key(7)的next指向的是key(3)

说明：

• 线程一接着工作。把 key(7) 摘下来，放到 newTable[i] 的第一个，然后把 e 和 next 往下移，这里是因为线程二工作在rehash后的HashMap当中
• 这个时候e已经是key(3)， next是null，似乎看到了死循环的形成了

说明：

• e.next = newTable[i] 导致 key(3).next 指向了 key(7)
• 此时的 key(7).next 已经指向了 key(3)， 环形链表就这样出现了

参考文章

Java中HashMap关键字transient的疑惑
JDK1.8 HashMap中tableForSize方法解析
HashMap 在高并发下引起的死循环