Java8 HashMap 源码分析
JDK 1.6 1.7 HashMap 采用的是 数组+链表的形式， 每个桶对应不同的 hash 值，根据 key 计算得到的 hash,将键值对存放到对于的位置。
hashMap 的键值都可以为 null ,每个桶又是链表的形式存放的。
但是当一个桶中链表的元素变多，通过 key 值依次查找的效率会变低，因此 HashMap 采用的是 桶+链表/红黑树的方式实现。当链表长度超过 8 时，将链表转换为红黑树，大大减少查找时间。
HashMap 结构
底层实现
Hash 表的结果是数组（桶）+单链表+红黑树。不同的 key 计算出的 hash 值可能相同，会造成 hash 冲突， hashmap 是不允许相同的 key, 当链表过长是，会造成访问速度降低，性能下降问题，黑客可以抓住这个特点进行攻击，让服务器处于繁忙状态， 引入红黑树，可以提高访问效率。
/** * The table, initialized on first use, and resized as * necessary. When allocated, length is always a power of two. * (We also tolerate length zero in some operations to allow * bootstrapping mechanics that are currently not needed.) */ transient Node<K,V>[] table; /** * Holds cached entrySet(). Note that AbstractMap fields are used * for keySet() and values(). */ transient Set<Map.Entry<K,V>> entrySet; /** * The number of key-value mappings contained in this map. */ transient int size;
HashMap 中的几个参数：
/** * The default initial capacity - MUST be a power of two. 默认初始化数组容量16 */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** 最大的容量键值对个数是 2的 30次方 * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */ static final int MAXIMUM_CAPACITY = 1 << 30; /** 加载因子，当 hash 表中数码超过当前容量与加载因子的乘积时，扩容。 * The load factor used when none specified in constructor. */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * The bin count threshold for using a tree rather than list for a * bin. Bins are converted to trees when adding an element to a * bin with at least this many nodes. The value must be greater * than 2 and should be at least 8 to mesh with assumptions in * tree removal about conversion back to plain bins upon * shrinkage. 桶的树化的一个阀值，当桶中元素个数超过这个值时，将链表转换成红黑树。 */ static final int TREEIFY_THRESHOLD = 8; /** 一个桶的链表还原阀值，当桶中元素个数小于这个值是，红黑树欢迎成链表。 * The bin count threshold for untreeifying a (split) bin during a * resize operation. Should be less than TREEIFY_THRESHOLD, and at * most 6 to mesh with shrinkage detection under removal. */ static final int UNTREEIFY_THRESHOLD = 6; /** * The smallest table capacity for which bins may be treeified. * (Otherwise the table is resized if too many nodes in a bin.) * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts * between resizing and treeification thresholds. 哈希表的最小化树形化容量，只有当数组容量大于这个阀值时，表中的桶才能树形化，否则，当桶中元素太多时，不是转换成红黑树，而是扩容，因为容量不够大。 */ static final int MIN_TREEIFY_CAPACITY = 64; 门限，进行 rehash 的限制，数组扩容的限制（capacity*loadFactor） // DEFAULT_INITIAL_CAPACITY.) int threshold; /** * The load factor for the hash table. * * @serial */ final float loadFactor;
- HashMap默认的容量（键值对个数）是16,。默认的加载因子是0.75，加载因子loadFactor是影响hashMap进行扩容的指标之一，还有一个影响因素是容量，也就是table数组的大小（桶的个数）。threshold是进行扩容的门限值，为capacity*loadFactor 。
- 数组元素个数 大于 MIN_TREEIFY_CAPACITY 时，可以树化，当一个桶中元素个数大于8时（添加元素时判断），会将链表转成红黑树；当树的节点个数小于6时（删除节点时判断），会转成链表。
- MIN_TREEIFY_CAPACITY变量：最小树形化的值。意思是：桶的的个数（表的容量）没有达到这个值（64）时，即使桶中元素个数大于8时，也不会转成红黑树，而是直接扩容（resize()），扩大桶的个数，桶个数两倍。只有当桶的个数大于等于该值时，才会树形化。
size 标识当前存储键值的个数，存一个+1 ，减一个-1 ，而 capacity 容量，也是表示存储键值对的容量，（不是桶数组的个数），当 size >capacity*0.75 那么就扩容，指的是键值对数量的比较。
构造函数
构造函数只是对 初始化容量 和 加载因子进行赋值， 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; // 找到大于等于 initialCapacity的第一个整数的幂， 例如 14 返回 16 this.threshold = tableSizeFor(initialCapacity); } /** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and the default load factor (0.75). * * @param initialCapacity the initial capacity. * @throws IllegalArgumentException if the initial capacity is negative. */ public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** * Constructs an empty <tt>HashMap</tt> with the default initial capacity * (16) and the default load factor (0.75). */ public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }
HashMap 是如何 get 值的
- 计算 Key 对应的 hash 值
- 根据 hash 值找到对应桶的第一个节点
- 判断第一个节点是不是要找的值，比较 hash 和key
- 第一个值不是就分红黑树和链表继续遍历
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; }
根据 key 和 hash 值找到对应的节点
- 根据 hash 值找到对应的桶的第一个节点，如果第一个节点 hash 值与 key 都对应相等，那么返回第一个，找桶的算法是 (n-1)&hash。n 是桶的个数
- 如果第一个数不是，那么就分树和链表继续查找。
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; }
- 查询步骤
- 计算 key 的 hash 值
- 根据 hash 值找到桶对应的第一个节点 hash&(n-1)
- 判断第一个节点是不是要找的节点，主要比较 hash 和 key 值
- 第一个节点不是，就分红黑树和链表继续遍历。
HashMap 是怎么 Put 的？
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }
- put 步骤
- 根据 key 计算 hash 值
- 判断是否第一次加入元素（table 是否为空），如果是则调用 resize函数初始化。
- 根据 hash 找到桶的第一个元素，如果第一个元素为空，那么直接插入新节点。
- 根据第一个元素不为空，则判断结果是不是红黑树，如果是红黑树，则调用红黑树的方法
- 如果不是红黑树，一次遍历链表，如果链表有传入的 key 相同的key ,那么用新的 value 替换掉原来的value ,并返回。
- 如果没有相同的 key ,则插入链表，如果新链表是否超过门限，超过，则转换成红黑树。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; /** 构造函数中没有对table 进行初始化，第一次 put 时，会进行 判断是否为空，为空，需要初始化，table 初始化容量为 16. resize() 是扩容函数，table 为空时，扩容的默认容量为16 ，table 不为空时，扩容两倍。 **/ if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 根据 hash 值，找到对应桶位置的第一个元素,如果改元素为空，直接插入 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; // 如果第一个元素不为空，该元素key与传入key相同，那么记录下来 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) { // 如果最后一个，且 key 都不相同，则将新节点插入到链表后 if ((e = p.next) == null) { // 如果新加入节点，链表大小超过阀值8，转换成红黑树 p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; }// 如果有相同的key ,跳出循环 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } /** 如果有相同 的key，那么将新的Value 替换旧的 value,并返回原来的value **/ 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; }
put 过程总结
- 根据 key 计算 hash 值
- 判断是不是第一次插入，如果是第一次插入，需要初始化，如果 threadhold = 0，初始化为16，如果threshold 不为0 (可能是初始化构造函数传入)，将容量初始化为 threadlod
- 根据 hash 值找到 (n-1)&hash 对应桶的第一个元素，如果第一个元素为空，那么直接插入新节点。
- 如果第一个元素不为空，判断是不是红黑树，如果是，调用红黑树的插入方法。
- 如果不是红黑树，遍历链表，如果链表中有和 key 相同的值，用新的value 替换 就 的value ，并返回旧的 value.
- 如果没有相同 的key ，那么就插入到链表最后，盘点链表的大小是否超过门限，如果是，转换成红黑树。
- 盘点新 size 是不是大于 threshold ,那么扩容。
resize
初始化 hash 表Node 数组大小为 16，如果 Node数组的元素达到 threadhold 重新调整 hashMap 数组大小，变成原来两倍。扩容时将数组的大小扩大为原来两倍，判断是否扩容时根据键值对的个数 size > threshold.
如何扩容
- 表中只有一个键值对，针对新表就是桶的位置，并插入键值对。
- 表中阶段是键值对时，
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) { // 如果原来的容量比默认容量大，且它的2倍没有超过最大的容量，用新容量为两倍，新扩容门限也是原来两倍 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 }// 如果原来的门限大于0，新容量为原来门限 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; }
扩容步骤
- 第一步：确定扩容后的容量
table 不为空时：
- 如果原来的容量 > 16 ,扩容两倍
- 如果 0 < 容量 <16 ,扩容两倍
table 为空时：
- 如果threshold > 0 ，这个就是构造函数传入的参数，初始化容量设置成 threshold
- 如果 threshold = 0 ,没传入初始化的值，初始化默认容量为16
- 第二步：扩容两倍步骤
- 新建一个散列数组，容量为旧表的2倍，接着把旧表的键值对迁移到新表（重新计算hash，放入新表）
- 桶只有一个键值对时，针对新表计算新的桶位置，并插入键值对。
- 桶中节点是红黑树节点，split 这个 bin
- 桶中节点包含多个键值对组成的链表，采用拉链算法，把链表键值对分成2串，根据 e.hash & oldCap 判断，一串放到 newTab[j] = loHead; 还有一串放到新表的元索引位置 j+原表长度oldCap 位置。
/** * 返回大于cap-1的第一个2的幂次。如cap=10，返回2^4=16 * 如果cap本身就是2的幂次，就返回cap */ 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; }
