注意
HashMap 是 Java 集合类中比较难搞懂的一个技术点，主要的难点是它的扩容机制，以及 JDK 1.8 之后新增的树化操作。
首先我们先来分析 JDK 1.7 中的 HashMap 。
1 初始化 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 public HashMap(int initialCapacity, float loadFactor) {//1 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; threshold = initialCapacity; init(); } public HashMap(int initialCapacity) {//2 this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap() {//3 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } public HashMap(Map<? extends K, ? extends V> m) {//4 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); inflateTable(threshold); putAllForCreate(m); }
几个构造方法类似，都是最终调用了第一个构造方法，第一个构造方法只是做了下赋值操作。如果是调用了无参构造参数，则 loadFactor 和 threshold 将分别被赋值为默认值。
如果调用第四个构造函数，除了调用第一个构造函数之外，还调用了 inflateTable 和 putAllForCreate 这两个方法，我们分别来看它们做啥。
1 2 3 4 5 6 7 8 private void inflateTable(int toSize) { // Find a power of 2 >= toSize int capacity = roundUpToPowerOf2(toSize); threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); table = new Entry[capacity]; initHashSeedAsNeeded(capacity); }
roundUpToPowerOf2方法的作用是确保返回的值是2的n次幂，该值要大于或等于传入的值，且该值是满足条件的第一个值。如：toSize==15 ，那么返回值是 16 。
之后，对 threshold 赋值，这里假定 capacity * loadFactor < MAXIMUM_CAPACITY + 1 ，所以threshold = capacity * loadFactor 。
然后，新建一个长度为 capacity 的数组。
initHashSeedAsNeeded中完成了对 hashSeed 的初始化。
讲到这里必须停一下了，因为除了很多不明用途的变量，这些变量将对之后的流程产生极大的影响，所以我先说下他们各自的概念，在之后的篇幅中大家再对照着理解就行了。
1、buckets（哈希桶）：在 HashMap 的注释里形象的用哈希桶来形容数组中的每个地址位置。
2、哈希表（散列表）：指数组本身，数组是装哈希桶的。其实就是 Hashmap 中的 table 。
3、initialCapacity（初始容量）：哈希表中哈希桶初始的数量。如果我们没有通过构造方法修改这个容量值，默认为DEFAULT_INITIAL_CAPACITY = 1<<4 即 16。
4、哈希表的容量：table.length。
5、加载因子(load factor)：加载因子是哈希表在其容量自动增加之前被允许获得的最大数量的度量。当哈希表中的条目数量超过负载因子和当前容量的乘积时，哈希表就会被重新映射（即重建内部数据结构），重新创建的散列表容量大约是之前散列表哈系统桶数量的两倍。默认加载因子（0.75）在时间和空间成本之间提供了良好的折衷。加载因子过大会导致很容易链表过长，加载因子很小又容易导致频繁的扩容。所以不要轻易试着去改变这个默认值。
6、threshold（扩容阈值）。扩容阈值 = 哈希表容量 * 加载因子。从上面加载因子的介绍可知，他是哈希表发生扩容的评判基准。
7、size（哈希表的键值对总数）= 所有哈希桶中所有链表节点数的加和。
讲完了 inflateTable ,我们再来看下 putAllForCreate 做了什么。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 private void putAllForCreate(Map<? extends K, ? extends V> m) { for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) putForCreate(e.getKey(), e.getValue()); } private void putForCreate(K key, V value) { int hash = null == key ? 0 : hash(key); int i = indexFor(hash, table.length); //看是否存在相同的key，如果有则直接将value替换并返回。 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { e.value = value; return; } } //新建 Entry ,并将其插入到该桶位置上链表的头节点。 createEntry(hash, key, value, i); } void createEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<>(hash, key, value, e); size++; }
这里思路就是遍历 m 中的 key 和 value，然后将它们一个一个添加到 table 中。细节在代码中已经注释，注意这里有一个很有意思的点，就是新添加的元素会被添加到对应链表的头结点位置。
2 put(K key, V value) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 public V put(K key, V value) { //如果数组为空，则新建数组。 if (table == EMPTY_TABLE) { inflateTable(threshold); } //如果 key 为 null，则将值存放在第 0 号桶上。 if (key == null) return putForNullKey(value); int hash = hash(key); //根据 hash 值，确定插入到桶的位置。 int i = indexFor(hash, table.length); //确定当前桶位置的链表中是否存在相同的key。 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; //扩容判断，并且添加元素。 addEntry(hash, key, value, i); return null; } private V putForNullKey(V value) { //查找第 0 号桶是否存在 key==null ，存在则替换并返回。 for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(0, null, value, 0); return null; } static int indexFor(int h, int length) { //因为 length 必定是 2 的 n 次幂，这里算出的结果范围是0～(length-1)。 return h & (length-1); } void addEntry(int hash, K key, V value, int bucketIndex) { //当 size 超过阈值时并且当前位置的值不为 null 时，执行扩容操作。 if ((size >= threshold) && (null != table[bucketIndex])) { //扩容到原来的2倍。 resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } //往链表头部插入元素。 createEntry(hash, key, value, bucketIndex); }
大体的代码逻辑已经在上面代码中注释，只剩下扩容的代码了。下面我们来看看 resize 方法内部的逻辑。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; //当哈希表的容量等于 1 << 30 时，直接返回，不进行扩容操作。 if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } //新建数组，该数组大小时原来的 2 倍。 Entry[] newTable = new Entry[newCapacity]; transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }
再来看下 transfer 方法的逻辑。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 /** * Transfers all entries from current table to newTable. */ void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) { while(null != e) { Entry<K,V> next = e.next; //rehash 为 true 时，重新 hash。 //我想这也是为了减少碰撞发生的概率吧。 if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } } }
transfer 方法的英文注释写的很清楚了，功能是元素从当前数组转移到新的数组中，之后在把新的数组赋值给当前数组。
好了，put 方法讲完了。流程是：
1、判断数组是否为空，为空则新建数组，顺便将 threshold 赋值为 capacity * loadFactor。
2、判断是 key 是否为 null，为 null 则保存到 0 号桶位置。
3、根据 hash 值寻找桶的位置。
4、查找是否具备相同的 key 值的 Entry。
5、如果 size >= threshold && null != table[bucketIndex] ，则扩容。
6、添加数据。
注意，判断 key 是否相等是根据e.hash == hash && ((k = e.key) == key || key.equals(k))判断的，这也是为什么要求作为key的类必须正确重写 equals 和 hashcode 方法。
作为 Hashmap 的 key 需要有什么前提条件？
不知道你注意到没，HashMap 在进行 put 操作时，也是会修改 modCount 的，说明 HashMap 同样是有fast-fail 机制的。实际上，Java 集合类除了 java.util.concurrent 包下的CopyOnWriteArrayList 和 ConcurrentHashMap，其它集合类都是有 fast-fail 机制，以后再遇到 modCount 时，笔者将不再赘述其作用。
到这里 put 方法的解读就到完成了。
这里不再列出 remove\get 方法的代码，原理很简单，请自行查阅。
3 遍历 HashMap 的遍历只能通过迭代器（Iterator）遍历。
1 2 3 for (Map.Entry entry : map.entrySet()) { System.out.println(entry.getKey().toString()); }
上面的写法等价于下面：
1 2 3 4 5 Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator(); while (iterator.hasNext()) { System.out.println(iterator.next()); }
这里得到的 iterator 对象，是一个 HashIterator 对象。
1 2 3 4 5 private final class EntryIterator extends HashIterator<Map.Entry<K,V>> { public Map.Entry<K,V> next() { return nextEntry(); } }
我们来看下 HashIterator 类结构。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 private abstract class HashIterator<E> implements Iterator<E> { Entry<K,V> next; // next entry to return int expectedModCount; // For fast-fail int index; // current slot Entry<K,V> current; // current entry HashIterator() { expectedModCount = modCount; if (size > 0) { // advance to first entry Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } } public final boolean hasNext() { return next != null; } final Entry<K,V> nextEntry() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); Entry<K,V> e = next; if (e == null) throw new NoSuchElementException(); if ((next = e.next) == null) { Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } current = e; return e; } public void remove() { if (current == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); Object k = current.key; current = null; HashMap.this.removeEntryForKey(k); expectedModCount = modCount; } }
HashIterator 的构造方法中存下了 modCount 的值给 expectedModCount ，之后定位到首个 entry 不为 null 的桶位置。
nextEntry 方法负责一个一个地遍历桶中的链表。
HashIterator 还提供了 remove 方法。
整个 HashIterator 类 和 ArrayList 中的 Itr 类很像。
HashMap 除了能通过 map.entrySet() 遍历 Entry ，还可以通过 map.keySet() 遍历 key 值，通过 map.values() 遍历 value 值。
好了，JDK 1.7 的 HashMap 就分析完了，其实它就是一个数组+链表的结构。对于它的扩容时机、扩容时的元素转移、链表插入方式（头插）以及几个重要的概念一定要搞清楚。HashMap 是线程不安全的，并且由于 JDK 1.7 中 HashMap 链表的插入方式是头插法，所以多线程操作还可能会导致循环链表的产生。
采用数组+链表的结构存储数据的一个弊端是可能会导致链表长度过长，即：Hash 冲突严重时，查询效率变低。于是，JDK 1.8 对 HashMap 做了重构，下面介绍JDK 1.8 HashMap 相关的内容。
JDK 1.8 中的 HashMap 最大的改变就是采用了数组+链表+红黑树的方式来组织数据。
4 put(K key, V value) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 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) //位置为 i 位置的桶不存在元素时，就将新元素赋值到 i 位置上。 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; //key 相等，则替换。 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) // 链表长度大于 8 ，则树化。 treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // key 已经存在。 V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) // size+1 大于阈值时，扩容。 resize(); afterNodeInsertion(evict); return null; }
我们来看下树化的逻辑。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; //Node 转化成 TreeNode 。 do { TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); //链表转化成红黑树。 if ((tab[index] = hd) != null) hd.treeify(tab); } }
当 tab == null 或者 (n = tab.length) < MIN_TREEIFY_CAPACITY 时，执行扩容操作。所以，HashMap 在树化时如果发现桶的数量小于 64 的话，是执行扩容操作，这样做也是为了性能可以达到最优吧。
下面让我们先来学习一下红黑树的原理吧。
一、红黑树是什么:
二、红黑树的构建规则:
变颜色：当前节点的父节点是红色，且父亲的兄弟节点也是红色，则将父亲节点和父亲的兄弟节点变成黑色，同时爷爷节点变成红色。最后，把当前节点设置到爷爷节点。
左旋：当前节点的父亲节点是红色，且父亲节点的兄弟节点是黑色且当前的节点是右子树的时候，则以当前节点的父亲节点为轴左旋。最后，把当前节点设置到当前节点的父节点。
右旋：当前节点的父亲节点是红色，且父亲节点的兄弟节点是黑色且当前的节点是左子树的时候，则以当前节点的爷爷节点为轴右旋，同时父亲节点变成黑色，爷爷节点变成红色。最后，把当前节点设置到轴节点。
参考文章>> （PS：文章中的删除操作没弄懂）参考视频>>
看完上面链接中的文章和视频，对于红黑树的理解也就差不多。至于Hashmap中关于红黑树的操作，笔者没有深入代码研究，这里难度还是很大的，以后再来复盘。
接下来，我们看下JDK 1.8 中 HashMap 是如何扩容的，它的扩容操作是在 resize 方法中进行的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 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; //上面的代码是初始化新哈希表对应的阈值（newThr）和容量（newCap）。 @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 { //该桶位置是链表结构时，复制到新数组上维持顺序。 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; }
对于桶节点是树或者链表的情况，Hashmap 转移到新数组上的策略都是将原结构拆分成两个链表，然后分别加入到新数组的对应桶上，以此来最大限度的让元素分散。对于是红黑树的情况，我们来看下 split 方法做了什么。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) { TreeNode<K,V> b = this; // Relink into lo and hi lists, preserving order TreeNode<K,V> loHead = null, loTail = null; TreeNode<K,V> hiHead = null, hiTail = null; int lc = 0, hc = 0; for (TreeNode<K,V> e = b, next; e != null; e = next) { next = (TreeNode<K,V>)e.next; e.next = null; if ((e.hash & bit) == 0) { if ((e.prev = loTail) == null) loHead = e; else loTail.next = e; loTail = e; ++lc; } else { if ((e.prev = hiTail) == null) hiHead = e; else hiTail.next = e; hiTail = e; ++hc; } } if (loHead != null) { if (lc <= UNTREEIFY_THRESHOLD) tab[index] = loHead.untreeify(map); else { tab[index] = loHead; if (hiHead != null) // (else is already treeified) loHead.treeify(tab); } } if (hiHead != null) { if (hc <= UNTREEIFY_THRESHOLD) tab[index + bit] = hiHead.untreeify(map); else { tab[index + bit] = hiHead; if (loHead != null) hiHead.treeify(tab); } } }
首先，将树结构分成两个双向链表，之后分别对他们进行树化或者链表化。如果长度<=6，就将树转变成单向链表，否则调用 treeify 树化。
除了扩容时，树可能会转化为链表外，在元素删除后，树也有可能转化为链表。具体什么情况下会转化成链表，笔者看代码没有搞懂，不过从代码中注释可以得知当树的元素足够小时就会退化成链表，这里我只粘贴出部分代码。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, boolean movable) { int n; if (tab == null || (n = tab.length) == 0) return; int index = (n - 1) & hash; TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl; TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev; if (pred == null) tab[index] = first = succ; else pred.next = succ; if (succ != null) succ.prev = pred; if (first == null) return; if (root.parent != null) root = root.root(); if (root == null || (movable && (root.right == null || (rl = root.left) == null || rl.left == null))) { tab[index] = first.untreeify(map); // too small return; } ///////省略之后的代码 }
关键代码就是 tab[index] = first.untreeify(map)这一句了，这个 too smal 到底如何量化，笔者代码没看懂，以后有精力再来复盘吧。
5 总结 一、JDK 1.7 的哈希表以数组+链表结构存储键值对，JDK 1.8 的哈希表以数组+链表+树结构存储键值对。
二、JDK 1.7 和 1.8 的哈希表扩容时都是扩大到原来的 2 倍，同时阈值也到达原来的 2 倍。当发生扩容元素转移时，JDK 1.7 会通过根据最新的 hashSeed 重新计算 hash 值来确定元素在新的数组中的位置，JDK 1.8 则是通过固定的 hash 值和原来哈希表容量发生与操作来确定元素决定新数组中的位置。两个版本的HashMap 发生元素转移后在新数组中的位置都有两种：原来位置或者原来位置+原来数组容量，从性能上考虑，1.8 版本的 Hashmap 省去了重 hash 计算，性能更高。
三、JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，JDK1.8 不会倒置。
上面第二条和第三条参考了这篇文章 ，笔者没有仔细研读完，只是结合自己的理解大概看了下思路。
四、JDK 1.8 对加载因子的作用了做了具体的说明，笔者理解的意思是如果加载因子为 0.75 ,那么链表长度达到 8 的概率是最小的，这样能够减少树化的可能，毕竟树化是有计算和内存损耗的。思路来源>>
五、JDK 1.7 Hashmap的扩容需要满足两个条件：当前数据存储的数量（即size()）大小必须大于等于阈值；当前加入的数据是否发生了hash冲突。
六、JDK 1.8 Hashmap的扩容只需满足 1 个条件：当前数据存储的数量（即size()）大小必须大于等于阈值。
七、JDK 1.8 以后哈希表的 添加、删除、查找、扩容方法都增加了一种节点为 TreeNode 的情况：
参考资料 搞懂 Java HashMap 源码