这篇文章打算详细理一下HashMap的源码，可能会比较长，基于JDK1.8
HashMap数据结构
HashMap的数据结构一句话就是 数组+链表+红黑树
首先HashMap是一个数组，俗称Hash桶，每个桶有可能是一个链表，也有可能是一棵红黑树（当链表长度达到8就会转换成红黑树），如下图所示（图片来自网络）
https://img2018.cnblogs.com/blog/757939/201911/757939-20191124173143661-254130649.jpg
table就是一个Hash桶，当一个键值对要put，通过hash算法和高位运算及取模运算来定位该键值对的存储位置。有时两个key会定位到相同的一个Hash桶，就发生了Hash碰撞，当hash算法计算结果越分散均匀，Hash碰撞的概率就越小，Map存储效率就越高。
当发生Hash碰撞，HashMap采用了链地址法，就是数组加链表的结合，每一个Hash桶都是一个链表，如果发生冲突，则将数据接在链表下面。Java8增加了红黑树来存储数据，在极端情况下，大量数据非常凑巧的放在同一个Hash桶下，这时对索引就会产生很大的负担，所以当链表长度达到8时，就会将链表转换成红黑树，提高查询性能。
上图每一个矩形都是一个存放数据的节点Node，本质是键值对，有两种，如果是链表，则是Node类，如果是红黑树，则是TreeNode类，TreeNode继承了Node类（Node和TreeNode都是HashMap的静态内部类）。Node类的源码字段定义如下
/**
* 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> {
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;
}
// 省略其他方法...
}
这里的 hash 值是HashMap对key自身的hashCode值进行重新计算的新的Hash值，计算方式如下，key自身的hashCode值的高16位与低16位进行异或操作，即对key进行高位计算（让高16位也参与计算，为了计算出更加分散的hash值）
/**
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
红黑树的TreeNode类字段定义源码如下：
/**
* Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
* extends Node) so can be used as extension of either regular or
* linked node.
*/
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
// 省略大量TreeNode的方法
}
parent、left、right ，表示红黑树当前节点的父节点，左孩子节点，右孩子节点。boolean red，表示当前节点是否为红色。在变成红黑树之前，这个hash桶是一个链表，从HashMap.Node可以看出Node节点只维护了下一个节点的引用，也就是next 。在变成红黑树的时候，这里多了个prev，维护当前节点还是链表中的Node节点时的上一个节点，用来恢复成链表时使用，所以实际上TreeNode是一个红黑树节点，也是一个双向链表的节点。其次 TreeNode 是HashMap的静态内部类，包内可见，不可被继承，并且继承至 LinkedHashMap.Entry 。而LinkedHashMap.Entry这个类又是继承 HashMap.Node 这个内部类。
这里的设计不明白的是，为什么不直接继承 HashMap.Node ,而是要继承 LinkedHashMap.Entry
/**
* HashMap.Node subclass for normal LinkedHashMap entries.
*/
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
可以看到 LinkedHashMap.Entry也是继承HashMap.Node，多了两个 before 和 after 字段，这是为了维护 LinkedHashMap 的双向链表的功能。说明 HashMap.TreeNode 就拥有双向链表的能力，可是TreeNode增加了一个prev属性来存储前一个节点，加上从Node继承过来的next属性，说明即使不继承LinkedHashMap.Entry也拥有双向链表的能力，从其他方法也能看出来，使用的也是 pre 和 next 这两个属性，而不是 before 和 after 这两个属性，即从LinkedHashMap.Entry继承过来的两个属性是完全没有用到的。所以不明白这样继承的意义何在，相当于TreeNode多了两个用不到的引用。目前网上还没有找到合理的解释，stackoverflow有一个提问就是关于该问题，不过Answer不太理解
why in Java8 the TreeNode subclass in HashMap extends LinkedHashMap.Entry instead of directly extending HashMap's Node subclass?
HashMap属性
一个类的属性成员很重要，以下就来解释一波HashMap属性成员
- HashMap的默认的初始容量是16，也就是数组的长度，并从注释可以看出容量大小必须是2的幂次方
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
- HashMap的最大容量，为2的30次幂减1
/**
* 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;
- 默认的负载因子，为0.75，当HashMap中的元素个数达到了这个阈值（容量大小 * 负载因子），则会进行扩容
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
- 一个桶存储的数据格式从链表转换成红黑树的阈值为8，即在一个桶中链表长度达到8，就会转换成红黑树
/**
* 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;
- 一个桶存储的数据格式从红黑树还原成链表的阈值为6，即在一个桶中，一棵红黑树存储的数据量小于等于6时，这个桶就会从红黑树还原成链表。
/**
* 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;
- 一个桶从链表转换成红黑树时，容量的最小值为64，即当一个桶中的链表长度达到8了，可是这时容量（数组长度）没有达到64，此时不会转换成树，而是进行扩容。且这个值不能小于 4 * TREEIFY_THRESHOLD
/**
* 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;
- 实际存储元素的数组桶，大小必须为2的幂次倍
/**
* 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;
- HashMap元素的个数
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
- HashMap的修改次数，如对元素的增删改，这个值在使用迭代器时会用到，实现快速失败策略。
/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient int modCount;
- 对数组桶进行扩容时的阈值(=容量*负载因子)，当HashMap中的size(元素个数)达到这个值时，就会进行扩容
/**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;
- 负载因子，当元素个数和容量的比例超过这个比例，就会进行扩容，默认为0.75，负载因子越大，HashMap的填充程度就越高，也就是能容纳更多的元素，但是索引效率就会降低，空间复杂度也会降低；负载因子越小，容纳更少的元素，越容易扩容，所以会对空间造成浪费，但是索引效率高，而默认值0.75是对空间和时间的一个平衡值，一般不进行修改，直接使用默认值
/**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;
HashMap之构造方法
共有四种构造方法
- 无参，只做了一件事情，将负载因子赋值为默认的值
/**
* 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
}
- 传入容量值（即数组长度），指定默认的负载因子，调用另一个构造方法
/**
* 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);
}
- 传入容量值和负载因子，进行验证并将负载因子进行赋值，然后将容量大小值暂时赋给threshold（阈值），这里的threshold并不是真正的阈值，在第一次resize时，会重新计算threshold的值，注意：第一次put的时候是一定会resize的，因为数组table在第一次put时才会被初始化
/**
* 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;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
上面的 this.threshold = tableSizeFor(initialCapacity) 方法是计算出比initialCapacity大，且最小的2的幂次数，如传入的容量值为22，这里会自动计算成32，因为HashMap的容量大小必须为2的幂次数，源码如下
/**
* 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;
}
- 传入一个Map，将该Map中的key, value都put到当前的HashMap中
/**
* Constructs a new <tt>HashMap</tt> with the same mappings as the
* specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
* default load factor (0.75) and an initial capacity sufficient to
* hold the mappings in the specified <tt>Map</tt>.
*
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException if the specified map is null
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
/**
* Implements Map.putAll and Map constructor
*
* @param m the map
* @param evict false when initially constructing this map, else
* true (relayed to method afterNodeInsertion).
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
根据传入Map的size，计算当前HashMap的容量，遍历Map将Key一个个put到当前HashMap中。
HashMap的put操作
put 方法实际调用的是putVal 方法，跟随源码一步步解释：
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
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;
}
- 参数解释：
- hash： 对key的hashCode值重新计算的hash值
- key： key值
- value： value值
- onlyIfAbsent： 如果是true，则HashMap中已经存在这个key，并且这个key对应的value不为空时，就不会进行put的覆盖操作。
- evict： 用于LinkedHashMap中的尾部操作，这里没有实际意义。
- 如果table（Hash桶数组）为空，进行扩容，实际上当我们构造一个HashMap对象时，table是没有初始化的，真正初始化扩容是在第一次put的时候
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
- 当要插入的key所对应Hash桶为空，则直接新建一个Node放在这个桶里面。(n - 1) & hash这个操作实际上是hash算法的第三步，取模操作，判断应该存放在哪一个桶下面
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
- 当要插入的key与计算出的对应的Hash桶的第一个节点相等，则直接进行赋值，p在这里指向对应Hash桶的第一个节点的引用，e变量是最终要插入的节点引用
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
- 如果对应的Hash桶的第一个节点为TreeNode（红黑树节点类），表示这个Hash桶是一棵红黑树，则以红黑树的方法进行添加节点，红黑树的操作这里不展开
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
- 对链表进行遍历，如果下一个节点为空，表示到链表结尾了，则直接新建一个节点接到链表最后面，然后去判断链表长度是否达到阈值（8），达到则转换成红黑树，操作就算完成了。否则不为空则判断是否跟当前要插入的节点相同，如果相同表示这个节点已经存在了，直接停止循环，后面会对这个节点进行覆盖操作
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;
}
}
- 针对已经存在key的情况做处理，e如果有值，则表示找到了一个跟要插入的key相同的节点，如果原本节点的值为空，或者onlyIfAbsent为false则进行覆盖操作，并返回原本的值。
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
- 增加HashMap修改次数，判断总节点个数是否达到阈值（threshold），达到进行扩容操作
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
afterNodeInsertion(evict); 和 afterNodeAccess(e); 是空函数，它存在主要是为了LinkedHashMap的一些后续处理工作。
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
流程图如下：
image.png
HashMap之remove
先看下HashMap的remove方法
/**
* Removes the mapping for the specified key from this map if present.
*
* @param key key whose mapping is to be removed from the map
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
removeNode 方法根据 key 匹配，如果匹配成功，则删除，返回删除的value值。否则返回null。而实际上，如果返回null也可以表示为匹配成功，只不过匹配的是 key 为 null value也为null 的Node节点（HashMap允许key和value为null的，key为null的hash值是0，所以是放在第一个Hash桶中）。
其实删除的过程也包含了查找的过程，先找出来，然后删除，如下是removeNode方法：
/**
* Implements Map.remove and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to match if matchValue, else ignored
* @param matchValue if true only remove if value is equal
* @param movable if false do not move other nodes while removing
* @return the node, or null if none
*/
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;
}
参数解析：
- hash ：key的hash值
- key ：节点的key
- value : 节点的value值
- matchValue : 为true时，需被删除的节点的Value值与给定的value一致，才删除
- movable : 删除节点之后是否移动（在删除红黑树节点时使用）
- 先做判空处理：保证数组桶不为空，也元素个数大于0，且待删除的节点所在的hash桶也不为空（(n - 1) & hash 取模计算数组桶下标）
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
- 判断首节点是否是待删除节点，node节点就是需要删除的节点引用
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
- 如果是红黑树节点，调用红黑树的方式找出这个节点
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); // 提供给LinkedHashMap的后续操作
return node;
}
总的流程就是 根据key找出节点 -> 然后删除节点。找出节点时先常规性的判空操作，顺便根据hash值定位出Hash桶。先判断首节点的key是否匹配，匹配则直接删除，然后再遍历Hash桶中的其他节点。如果这个Hash桶中的节点是TreeNode，则以红黑树的方式去查找节点，这个方式实际是调用了find方法。如果是普通的Node节点（单向链表），则遍历链表匹配节点。找出节点之后，就删除了它，如果是红黑树则使用红黑树的方式删除节点。afterNodeRemoval方法是空的方法，在HashMap中没有意义，在LinkedHashMap中有具体的实现。
HashMap之扩容resize
HashMap的扩容resize方法是HashMap非常重要的一个方法，当Key的数量达到阈值的时候，为了保持查询效率，HashMap会进行扩容，将原本的Hash桶数量变为原本的两倍，并将原本的Key重新计算放在新的Hash桶中。我们先看一下源码，在一步步解析。
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
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;
}
- 首先看一下这三个条件处理。
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表示有容量，该map已经存在key了，已经不是第一次扩容了。容量和阈值都变为原来的两倍，如果超过最大值，就取最大值。
- 接下来两个条件都表示是第一次扩容，第二个 else if 条件表示在调用构造方法创建实例时，传了参数。在构造方法篇，我们讲到，如果传了参数，则会把传进来的initialCapacity（容量）值暂时存放在threshold（阈值）变量中，实际上值表示的是容量，所以threshold是有值的。这里的操作就是直接把threshold值赋给newCap（新的容量）
- 第三个条件则表示第一次扩容，且创建HashMap时是没有传参数的，在构造方法篇中讲到，无参的构造方法只做了一件事情，将负载因子赋值为默认的值，所以threshold（阈值）是没有值的，所以这里就将容量和阈值都设置成默认的值
- 重新计算threshold（阈值）
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
- 由于数组是不可变的，扩容时就需要新建一个新的数组，大小为新的容量newCap。接下来的操作就是遍历将旧数组里面的数据移到新的数组中
有数据的Hash桶总共三种情况
- 第一种：如果Hash桶中只有一个key，则直接赋值到新的Hash桶中
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
其中的 e.hash & (newCap - 1) 为取模操作，重新计算的数组下标，进行存放
- 第二种：如果Hash桶中是一课红黑树，则使用红黑树的操作方法
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
split方法如下：
/**
* Splits nodes in a tree bin into lower and upper tree bins,
* or untreeifies if now too small. Called only from resize;
* see above discussion about split bits and indices.
*
* @param map the map
* @param tab the table for recording bin heads
* @param index the index of the table being split
* @param bit the bit of hash to split on
*/
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);
}
}
}
逻辑如下，在HashMap的数据结构中有讲到TreeNode的数据结构，我们知道TreeNode是一个红黑树的节点，也是一个双向链表的节点，所以这里就算按顺序遍历这个双向链表，将这个链表拆分成两个链表，一个低链表，一个高链表，起始点就是调用这个方法的TreeNode节点，也就是方法中的this，从resize方法知道，这个节点就是这个Hash桶的首节点，也就是红黑树中的根节点。
接下来判断低链表是否有值，并且判断低链表是否少于UNTREEIFY_THRESHOLD值（红黑树转链表的阈值，值为6），是的话就执行红黑树转成普通链表的方法 tab[index] = loHead.untreeify(map) ，否则的话，就是不需要将红黑树转成普通链表，直接将首节点赋予这个Hash桶，然后这时候判断高链表是否有值，如果有值，说明原来的双向链表被拆分了，那么这个时候低链表的红黑树性质被破坏了，就需要重新进行构建红黑树的操作 loHead.treeify(tab) 。同理高链表也进行同样的操作。
上面讲的可能有点乱，实际上就是如果一个Hash桶原本是一棵红黑树（也是双向链表），那么在扩容的时候可能会把这个棵树的节点分为两部分，一部分留在原来的Hash桶中，一部分移到往后移动 oldCap 的位置。然后再判断两部分的节点个数，如果少于6个，就执行 untreeify 方法，最后对两部分的节点进行重新构建红黑树的操作 treeify （下面单独讲）方法。
untreeify 方法如下：
/**
* Returns a list of non-TreeNodes replacing those linked from
* this node.
*/
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
for (Node<K,V> q = this; q != null; q = q.next) {
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
这个方法是红黑树转普通链表的方法，逻辑就是遍历这个Hash桶的节点，将TreeNode全部转为Node即可，最后返回首节点。（虽然这个Hash桶是一棵红黑树，但也是双向链表，所以操作的时候直接按双向链表的性质操作即可）。
replacementNode方法如下：
// For conversion from TreeNodes to plain nodes
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
return new Node<>(p.hash, p.key, p.value, next);
}
- 第三种：如果Hash桶中存放的是多个key的链表形式，则使用以下方式。
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;
}
}
这里重点讲解链表形式下的数据转移：
将原本的链表拆分成两条链表 e.hash & oldCap 这个结果为 0 的节点放在低的链表中，为 1 的放在高的链表中，在新的数组中，低链表依然放在原本的位置，高链表放在 往后移 oldCap 个位置的地方。
最重要的一个操作为 ( e.hash & oldCap )， 因为cap（数组长度）是2的幂次数，所以cap的二进制只有一位最高位是1，例如16（10000），这一步的操作就是查看节点的hash值与oldCap为1的那一位相同的位置是1还是0，如果是0则移到新数组中相同的下标位置，如果为1则往后移动此次增加的数组长度的位置，，，这个过程也就是 rehash 的过程
举个栗子：
- 旧数组长度为16
- 有两个key的计算出来的hash分别为5和21，所以他们两个都存放在数组下标为5的Hash桶中，形成一个链表
- 现在要进行扩容，新数组长度为32，然后遍历这个链表，进行 (e.hash & oldCap) 操作，5（00101），旧数组长度16（10000），16的二进制为1的位数是右数第五位，而5的二进制右数第五位是0，所以5移动到新的数组中下标为5的Hash桶中。
- 另一个是21（10101），和16（10000）进行 & 的结果是1，也就是21的二进制右数第五位是1，所以21在移动到新的数组中是放在下标为（5+16）的Hash桶中
不好理解的话就理解，(e.hash & oldCap) 的结果如果是0，则下标位置不变，如果是1则下标位置增加oldCap个位置。
这里的代码设计，是基于数组长度cap一定是2的幂次数才成立，这也是HashMap将数组长度（容量）设计成2的幂次数的原因之一
这里的解析是看了源码和网上的博客之后自己的总结，不对的地方欢迎探讨。
HashMap的链表转红黑树 treeify
在HashMap的putVal方法中，有这么一段：
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;
}
遍历Hash桶中的元素当链表长度大于等于 TREEIFY_THRESHOLD 时，就会进行链表转红黑树的动作，至于判断条件为什么是 binCount >= TREEIFY_THRESHOLD - 1，是因为 binCount没包含前两个元素，后面有注释 -1 for 1st（-1 表示 第一个）。
再来看下 treeifyBin(tab, hash) 方法：
/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
*/
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; // 定义首、尾节点
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);
}
}
首先判断数组长度是否达到了 MIN_TREEIFY_CAPACITY（64），如果没有的话，就进行扩容，而不是结构转换。即当数组长度没有达到64的话，没必要进行结构转换，而是进行扩容，将元素拆分到不同的Hash桶中
将hash值取模，得到数组下标，然后遍历这个Hash桶中的链表，将每个节点都转换成树节点（TreeNode），如下是 replacementTreeNode 方法
// For treeifyBin
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
到目前为止，也只是把Node节点转换成TreeNode节点，并把单向链表变成双向链表，
hd.treeify(tab) 方法才是将链表转成红黑树的方法：
/**
* Forms tree of the nodes linked from this node.
* @return root of tree
*/
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
这是个红黑树的构建过程，按照查找二叉树的性质，进行插入，然后再进行插入后的平衡操作。具体不详细讲，请搜索红黑树，虽然有点差异，但总体思路一致。
我们这里看几点，一个是对 dir 的判断
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
dir 是 x（待插入节点）和 p（当前节点）的比较结果，如果是 -1 表示 x 比较小，放在 p 的左侧。否则 x 比较大，放在 p 的右侧。不可能为0（即相等）。
首先根据 key 的 hash 值的大小来判断，但是 hash 值有可能会相等（即使是 equals 不相等的情况），如果相等，就要根据其他方式进行比较，如果 key 实现了comparable接口，并且当前树节点和链表节点是相同Class的实例，那么通过comparable的方式再比较两者。如果还是相等，最后再通过tieBreakOrder比较一次。先看下 kc = comparableClassFor(k) 方法：
/**
* Returns x's Class if it is of the form "class C implements
* Comparable<C>", else null.
*/
static Class<?> comparableClassFor(Object x) {
if (x instanceof Comparable) {
Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
if ((c = x.getClass()) == String.class) // bypass checks
return c;
if ((ts = c.getGenericInterfaces()) != null) {
for (int i = 0; i < ts.length; ++i) {
if (((t = ts[i]) instanceof ParameterizedType) &&
((p = (ParameterizedType)t).getRawType() ==
Comparable.class) &&
(as = p.getActualTypeArguments()) != null &&
as.length == 1 && as[0] == c) // type arg is c
return c;
}
}
}
return null;
}
comparableClassFor 方法就是判断传进来的对象是否实现了 Comparable 接口，如果实现了，就返回这个对象的 Class 类对象，否则返回null。
再看 dir = compareComparables(kc, k, pk) 方法：
/**
* Returns k.compareTo(x) if x matches kc (k's screened comparable
* class), else 0.
*/
@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
static int compareComparables(Class<?> kc, Object k, Object x) {
return (x == null || x.getClass() != kc ? 0 :
((Comparable)k).compareTo(x));
}
调用这个方法就说明了这个 key 是实现了 Comparable 接口的，然后调用 compareTo 获得比较结果。
如果比较结果是0，说明又是相等，那么这时候就使用终极绝招，调用 dir = tieBreakOrder(k, pk) 方法。
/**
* Tie-breaking utility for ordering insertions when equal
* hashCodes and non-comparable. We don't require a total
* order, just a consistent insertion rule to maintain
* equivalence across rebalancings. Tie-breaking further than
* necessary simplifies testing a bit.
*/
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
当 key 的 hash 值无法比较时，并且没有实现 Comparable 接口，这是就调用 System.identityHashCode(a) 方法 比较大小，且返回值不可能为0。
System.identityHashCode 方法是根据内存地址计算出来的一个数值，默认情况下跟Object的hashCode方法的结果一致，但是hashCode方法是可以重写的，而这个方法不会被重写，计算出来的结果一定是跟内存地址相关的。所以用这个计算出来的结果进行比较，几乎是不可能会出现相等的情况。
计算出 dir 之后，用查找二叉树的方式插入，插入之后需要进行平衡操作:
root = balanceInsertion(root, x);
平衡操作不详细讲，请查阅红黑树
把所有的链表节点都遍历完之后，最终构造出来的树可能经历多次平衡操作，根节点目前到底是链表的哪一个节点是不确定的，所以我们需要把红黑树的根节点作为Hash桶的第一个节点。
moveRootToFront(tab, root);
/**
* Ensures that the given root is the first node of its bin.
*/
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
if (root != first) {
Node<K,V> rn;
tab[index] = root;
TreeNode<K,V> rp = root.prev;
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
assert checkInvariants(root);
}
}
TreeNode既是一个红黑树结构，也是一个双链表结构，这个方法里做的事情，就是保证树的根节点一定也要成为链表的首节点。
我们看到在代码的最后一段：
assert checkInvariants(root);
/**
* Recursive invariant check
*/
static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
tb = t.prev, tn = (TreeNode<K,V>)t.next;
if (tb != null && tb.next != t)
return false;
if (tn != null && tn.prev != t)
return false;
if (tp != null && t != tp.left && t != tp.right)
return false;
if (tl != null && (tl.parent != t || tl.hash > t.hash))
return false;
if (tr != null && (tr.parent != t || tr.hash < t.hash))
return false;
if (t.red && tl != null && tl.red && tr != null && tr.red)
return false;
if (tl != null && !checkInvariants(tl))
return false;
if (tr != null && !checkInvariants(tr))
return false;
return true;
}
这一步是防御性编程，用递归的方式校验每一个TreeNode节点是否满足红黑树和双向链表的特性。如果这个方法校验不通过：可能是因为用户编程失误，破坏了结构（例如：并发场景下）；也可能是TreeNode的实现有问题（这个是理论上的以防万一）
至此，链表转红黑树的整个过程就已经结束了。我们可以看出，链表转红黑树的条件还是比较苛刻的，Hash 桶数组长度不能少于64个，否则节点达到阈值会先考虑扩容，扩容的时候就会重新拆分节点到新的 Hash 桶中，而且，只有在 hashCode 的实现很糟糕，极端的情况下，才会导致一个Hash桶有超过8个节点。
JDK1.8 虽然引入了红黑树，但实际情况中还是会很少用到的，但是红黑树是一个非常经典优秀的数据结构，所以学习一下还是非常有必要的
HashMap的hash算法
HashMap是用Hash表来存储数据的，存放数据之前第一步要做的就是定位Hash桶，一个好的hash算法可以减少Hash碰撞，使数据更加分散均匀地存储在Hash桶中，Map的存储效率就会越高。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
在调用真正的putVal方法之前，调用了hash(key)方法对key进行hash计算。
HashMap的hash算法分为三步，1、获取key自身的hashCode值；2、高位运算；3、取模运算。
前两步在hash方法中，而第三步在putVal中才会计算
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
i = (n - 1) & hash
- key.hashCode()：获取key自身的hashCode值
- (h = key.hashCode()) ^ (h >>> 16)：将获取的hashCode值进行高位运算，让高16位也参与运算，计算出更加分散的hash值，具体是将hashCode值向右移16位，再与自身进行异或。
- 计算出来的新的hash值对容量（也就是Hash桶数组长度）取模，最终定位某一个Hash桶，第三步在putVal方法中。因为n一定为2的幂次数，所以 (n - 1) & hash 实际上就是hash对n的取模，而这样子的操作比 hash%n 快很多，这也是为什么HashMap要将数组长度设为2的幂次数的原因之一。
计算流程如下：
https://images2018.cnblogs.com/blog/1331009/201802/1331009-20180226152430594-1656669455.png
HashMap为何将容量设计为2的幂次数？
我们知道HashMap的容量大小，也就是Hash桶的数量一定要是2的幂次数，这是一种非常规的设计。为了能减少冲突的概率，一般会选择素数，像Hashtable初始化桶的数量就是11
那这么设计的目的是什么呢？ 主要是为了在取模和扩容时做优化
在HashMap构造方法中，如果传入的参数不为2的幂次数，HashMap会将其转换为向上取最小的2的幂次数，如传入的大小为20，则HashMap会转换为32，最终创建了一个Hash桶长度为32的实例。利用了tableSizeFor这个方法
/**
* 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;
}
上面的位运算可以理解为，将cap的尾部几位全部置1，最后在加1，就可以计算出比cap大的最小幂次数了。
上面讲到，设计为2的幂次数主要为了在取模和扩容时做优化：
- 在取模时，对于新计算出来的hash值，对Hash桶长度n取模，可以 hash & (n - 1) ,这种操作比 hash % n 速度快很多，而这种方式的优化只有在 n 为2的幂次数的时候才有效。上面的HashMap的hash算法有讲到
- 在扩容时，由于Hash桶是2的幂次数，在扩容之后，Hash桶的长度变为原来的两倍，那么所有的key要么在原来的位置，要么在增加2的幂次数的位置，只要将原本的hash值往前看一位，如果是0，就在原位置，如果是1，就是往后增加2的幂次数的位置。上面的扩容resize中有讲到
还有其他的，有空再梳理
以上只是简单梳理了源码的流程，更多的细节以及设计的思路还等待探索...
参考：
https://www.cnblogs.com/kangkaii/p/8473793.html
https://www.zhihu.com/question/20733617
等等...
网友评论