get到一个大佬的博客：hashmap源码分析

---

---

HashMap简介

HashMap是使用拉链法（数组+链表）的方式实现的，并且某个链表长度过长时，会将该链表转换成红黑树提高性能。

而HashMap的内部数组长度初始为16，如果需要扩展数组，那么规定是2的次方。例如16会扩充到32–>64–>128–>256–>512…
这样扩充有两个原因：

• 选择足够大的数组，让键值对更平均的分布在各个索引位，尽量减少链表长度。

• 当使用除留余数法时，能使用位运算代替取模运算，很大程度上提高效率（据说是5~8倍）。N % M 等价于N & (M - 1)，M为2的次方。

源码分析

类属性

    /*** The default initial capacity - MUST be a power of two.*///默认初始化长度，16static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16/*** 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;/*** The load factor used when none specified in constructor.*///默认负载因子，用作扩容，hashtable也是这个默认值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.*///树形化阈值，当链表节点个大于等于TREEIFY_THRESHOLD - 1时,会将该链表换成红黑树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.*///最小树形化的容量，即：当内部数组长度小于64时，不会将链表转化成红黑树，而是优先扩充数组。static final int MIN_TREEIFY_CAPACITY = 64;

内部类

这里的内部类是HashMap的结点对象，即最小存储单位。

    /*** Basic hash bin node, used for most entries.  (See below for* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)*/static class Node<K,V> implements Map.Entry<K,V> {//hash是经过hash()方法处理过的hashCode，为了使hashCode分布更加随机,要与Hashtable的key.hashCode()区分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;}}

注意：

TreeNode是Node是子类，继承关系如下：Node是单向链表节点，Entry是双向链表节点，TreeNode是红黑树节点。

java.util.HashMap<K, V>.Node<K, V>java.util.LinkedMap<K, V>.Entry<K, V>java.util.HashMap<K, V>.TreeNOde<K, V>

构造函数

    /*** Constructs an empty <tt>HashMap</tt> with the specified initial* capacity and load factor.** @param  initialCapacity the initial capacity* @param  loadFactor      the load factor* @throws IllegalArgumentException if the initial capacity is negative*         or the load factor is nonpositive*/public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;// NaN：Not a Number。例如给-1开方就会得到NaN。if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;// 这个方法可以将任意一个整数转换成2的次方。// 例如输入10，则会返回16。// 另外，有人可能疑惑，不是说threshold是 数组容量 * loadFactor得到的吗？// 是的，在第一次put操作，扩充数组时，会将这个threshold作为数组容量，然后再重新计算这个值。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}

hash()

Hashtable使用的是key.hashCode()，HashMap则进行了优化。

    static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

hash方法的作用是将hashCode进一步的混淆，增加其“随机度”，试图减少插入hash map时的hash冲突，换句更专业的话来说就是提高离散性能。而这个方法知乎上有人回答时称为“扰动函数”。原理是用hashCode的高16位与低16位进行异或运算。

put()

里面的索引算法 (n - 1) & hash ，这个表达式就是hash值的取模运算，上面已经说过当除数数为2的次方时，可以用与运算提高性能。

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}// onlyIfAbsent：当存入键值对时，如果该key已存在，是否覆盖它的value。false为覆盖，true为不覆盖。
//               参考putIfAbsent()方法。
// evict：用于子类LinkedHashMap。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {// tab：内部数组// p：hash对应的索引位中的首节点// n：内部数组的长度// i：hash对应的索引位HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;// 首次put时，内部数组为空，扩充数组。if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 计算数组索引，获取该索引位置的首节点，如果为null，添加一个新的节点if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {   HashMap.Node<K,V> e; K k;// 如果首节点的key和要存入的key相同，那么直接覆盖value的值。if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// 如果首节点是红黑树的，将键值对插添加到红黑树else if (p instanceof HashMap.TreeNode)e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 此时首节点为链表，如果链表中存在该键值对，直接覆盖value。// 如果不存在，则在末端插入键值对。然后判断链表是否大于等于7，尝试转换成红黑树。// 注意此处使用“尝试”，因为在treeifyBin方法中还会判断当前数组容量是否到达64，// 否则会放弃次此转换，优先扩充数组容量。else {// 走到这里，hash碰撞了。检查链表中是否包含key，或将键值对添加到链表末尾for (int binCount = 0; ; ++binCount) {// p.next == null，到达链表末尾，添加新节点，如果长度足够，转换成树结构。if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}// 检查链表中是否已经包含keyif (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}// 覆盖value的方法。if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount; // fail-fast机制// 如果元素个数大于阈值，扩充数组。if (++size > threshold)resize();afterNodeInsertion(evict);return null;
}

• 检查数组是否为空，执行 resize() 扩充；

• 通过hash值计算数组索引，获取该索引位的首节点。

• 如果首节点为null，直接添加节点到该索引位。

• 如果首节点不为null，那么有3种情况

  • key和首节点的key相同，覆盖value；否则执行②或③
  • 如果首节点是红黑树节点（TreeNode），将键值对添加到红黑树。
  • 如果首节点是链表，将键值对添加到链表。添加之后会判断链表长度是否到达TREEIFY_THRESHOLD - 1这个阈值，“尝试”将链表转换成红黑树。

• 最后判断当前元素个数是否大于threshold，扩充数组。

resize()

扩容数组。

上半部分是从新计算数组的长度和阈值。下半部分是将原数组的元素拷贝到新数组中。

final HashMap.Node<K,V>[] resize() {HashMap.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;}// 否则数组容量扩充一倍。（2的N次方）else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}// 如果数组还没创建，但是已经指定了threshold（这种情况是带参构造创建的对象），threshold的值为数组长度// 在 "构造函数" 那块内容进行过说明。else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;// 这种情况是通过无参构造创建的对象else {               // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 可能是上面newThr = oldThr << 1时，最高位被移除了，变为0。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"})HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];table = newTab;// 下面代码是将原来数组的元素转移到新数组中。问题在于，数组长度发生变化。 // 那么通过hash%数组长度计算的索引也将和原来的不同。// jdk 1.7中是通过重新计算每个元素的索引，重新存入新的数组，称为rehash操作。// 这也是hashMap无序性的原因之一。而现在jdk 1.8对此做了优化，非常的巧妙。if (oldTab != null) {// 遍历原数组for (int j = 0; j < oldCap; ++j) {// 取出首节点HashMap.Node<K,V> e;if ((e = oldTab[j]) != null) {oldTab[j] = null;// 如果链表只有一个节点，那么直接重新计算索引存入新数组。if (e.next == null)newTab[e.hash & (newCap - 1)] = e;// 如果该节点是红黑树，执行split方法，和链表类似的处理。else if (e instanceof HashMap.TreeNode)((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);// 此时节点是链表else { // preserve order// loHead，loTail为原链表的节点，索引不变。HashMap.Node<K,V> loHead = null, loTail = null;// hiHeadm, hiTail为新链表节点，原索引 + 原数组长度。HashMap.Node<K,V> hiHead = null, hiTail = null;HashMap.Node<K,V> next;// 遍历链表do {next = e.next;// 新增bit为0的节点，存入原链表。if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}// 新增bit为1的节点，存入新链表。else {if (hiTail == null)hiHead = e;elsehiTail.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;
}

先计算新数组的长度和新的阈值（threshold），然后将旧数组的内容迁移到新数组中，和1.7相比不需要执行rehash操作。因为以2次幂扩展的数组可以简单通过新增的bit判断索引位。只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”

HashMap总结（面试）

HashMap是基于拉链法实现的一个散列表，内部由数组和链表实现。

• 数组的初始容量为16，而容量是以2的次方扩充的，一是为了提高性能使用足够大的数组，二是为了能使用位运算代替取模预算。

• 数组是否需要扩充是通过负载因子判断的，如果当前元素个数为数组容量的0.75时，就会扩充数组。这个0.75就是默认的负载因子，可由构造传入。我们也可以设置大于1的负载因子，这样数组就不会扩充，牺牲性能，节省内存。

• 为了解决碰撞，数组中的元素是单向链表类型。当链表长度到达一个阈值时（7或8），会将链表转换成红黑树提高性能。而当链表长度缩小到另一个阈值时（6），又会将红黑树转换回单向链表提高性能，这里是一个平衡点。

• 对于第三点补充说明，检查链表长度转换成红黑树之前，还会先检测当前数组是否到达一个阈值（64），如果没有到达这个容量，会放弃转换，先去扩充数组。所以上面也说了链表长度的阈值是7或8，因为会有一次放弃转换的操作。