wen HashMap源码分析
HashMap与ArrayList一样，是我们在日常编程中经常使用的，所以选择对它进行一次源码分析。
HashMap的特性
- HashMap的存储Key是唯一的，且顺序是无序的；
- HashMap中存储的Key和Value都允许为Null；
- HashMap内部使用数组 + 链表或红黑树的方式存储Key Value形式的键值对；
- HashMap是非线程安全的；
- 不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1) ；
HashMap的源码分析
JDK1.8中的HashMap的源码，算上注释大约有2400行左右，分析HashMap与分析ArrayList和LinkedList不同，需要先从HashMap的规则进行分析：
- 如何对Key进行Hash并在Hash表中定位；
- Hash冲突时的解决方式；
- Hash表的扩容的实现；
在了解了JDK是如何对HashMap的关键点进行设计后，再来阅读代码，就会顺利很多了。
Hash算法与定位
前提：重中之重，HashMap中散列表的长度，永远是2^n！！！
简单概括的话，HashMap是通过对元素的Key进行hash算法后得到hash值，然后将hash值与数组（也就是hash表）长度进行计算，获得一个索引，这个索引就是元素在数组中的位置，接着将元素保存到该位置（暂时不考虑hash冲突）。
HashMap中的hash算法与定位，可谓是整个HashMap实现的精髓之一了，下面分析代码：
// hash算法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 定位元素
tab[i = (n - 1) & hash]
这几行代码即是HashMap的hash算法和定位方法，网上对这几行代码的讲解文章有很多，我贴出几个连接并进行简单说明和总结：
https://www.cnblogs.com/wang-meng/p/9b6c35c4b2ef7e5b398db9211733292d.html
https://blog.csdn.net/a314774167/article/details/100110216
先说hashcode算法步骤：
- 获取key的hashcode，是一个int值；
- 将hashcode进行一次无符号位置16位（等于丢弃低位，将高位移动到低位，高位补0）；
- 对hashcode与位移后的值进行异或操作；
- 最终获得的int值即使key对应的hashcode；
这段代码的重点在于步骤2和步骤3，为什么要做hashcode ^ (hashcode >>> 16)，上面连接中的文章描述的很清楚了。
============================================================================
============================================================================
将hashcode的高位16位于低位16位进行异或，可以使hashcode分散的更平均，减少hash碰撞。
在说说定位方法，定位方式其实并没有什么神秘的地方，思路就是用hashcode与数组长度取模。那为什么直接用 hashcode % length，而是用 length – 1 & hashcode进行定位呢？
这里其实是有一个性能考虑的，总所周知，在计算机计算时，位操作要比取模操作快，若一次比较可能感觉不出来，但是当数组进行扩容时，会从新的数组中的元素进行位置分配，这时如果元素数量多，那么位操作的高效率就体现出来了。
若要用位操作代替取模，其关键点与精髓就在于数组长度永远是2^n！
基于二进制的特性，以int为例，2^n – 1 的有效为永远是1。举几个形象的例子：
16的2进制=10000；15的2进制=1111；
32的2进制=100000；31的2进制=11111；
64的2进制=1000000；63的2进制=111111；
如果用length & hashcode，那么会被0给屏蔽掉，但用length – 1 & hashcode就不存在这种问题，因为有效为都是1，所以&的效果更好。
所以，要做到用位运算代替取模来提升效率，需要让数组的长度必须是2^n。
Hash冲突解决办法
当两个Key的hashCode经过计算后，依然相同，这种情况就被称为hash冲突。常用的解决hash冲突的两个办法是链表发和开发寻址法。HashMap使用链表法来解决Hash冲突。
做法是将多个冲突的元素，组成一个链表。在经过定位后，顺序查找链表找到真正要找的元素，查找链表的时间复查度为O(n)，n等于链表长度。
由于查询链表的时间复杂度为O(n)，当数组某个索引位置的链表过长时，查询效率依旧不高。所以在JDK1.8中，当链表长度打到一个阈值时，Hashmap会将链表转换为红黑树。
// 链表转换为红黑树的链表长度阈值
static final int TREEIFY_THRESHOLD = 8;
// 红黑树转换为链表的链表长度阈值
static final int UNTREEIFY_THRESHOLD = 6;
// 链表转换为红黑树的数组长度阈值
static final int MIN_TREEIFY_CAPACITY = 64;
链表转换为红黑树，或将红黑树转换为链表的阈值有以上三个。
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
当链表中的元素大于TREEIFY_THRESHOLD时候，会尝试调用treeifyBin将链表转换为红黑树。为什么说尝试呢？
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
treeifyBin方法中会判断，如果数组的长度小于MIN_TREEIFY_CAPACITY时，不进行红黑树转换，而是对数组进行一个resize。只有当长度不小于MIN_TREEIFY_CAPACITY时，才对链表做红黑树转换。
当链表中的元素小于UNTREEIFY_THRESHOLD时，将红黑树转换为链表。
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
为什么将这几个阈值设定为8，6，64，我的理解是，这些是经验值，是对时间复杂度和空间复杂度的一个平衡。
先说64，当链表长度>=8时，会尝试转换红黑树，但要求数组长度必须<64。HashMap源码注释中说道，一个红黑树的内存占用是一个链表的2倍。所以当<64这个经验阈值时，只对数组做resize，resize的同时会rehash。这是平衡时间和空间两个复杂度的设计。
再说8和6，在HashMap源码中，有一段注释是Implementation notes.
* Because TreeNodes are about twice the size of regular nodes, we
* use them only when bins contain enough nodes to warrant use
* (see TREEIFY_THRESHOLD). And when they become too small (due to
* removal or resizing) they are converted back to plain bins. In
* usages with well-distributed user hashCodes, tree bins are
* rarely used. Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million
大致意思是，在一个良好的hash算法下使用HashMap，发生链表转红黑树的概率是很小的，这个概率的依据是泊松分布。
注释中做了一些数据说明，依据公式，默认使用扩容阈值0.75时，出现hash冲突8次的概率是0.00000006，概率很小。所以这也是平衡时间和空间两个复杂度的设计。
至于将红黑树转换为链表选择了6而不是8，是为了避免频换转换带来的耗损。
Hash表的扩容
了解了hash定位和hash冲突后，会清楚HashMap内部维护了一个数组来保存数据，数组的长度是2^n，当hash冲突时通过链表法解决问题，当链表过长时会转换为红黑树。
那么当这个数组（散列表）容量不足时，如何扩容是一个关键点，下面来看看HashMap是如何对数组进行扩容的。
// 数组的默认长度
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 数组的最大长度
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的填充因子，意思是当数组中的容量达到75%时，会扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
上面是扩容的几个关键阈值，具体扩容代码如下：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
// =======================================================
// 计算相关阈值
// 记录当前数组的长度和扩容阈值，创建新数组的长度和扩容阈值
// 由于HashMap是懒加载，也就是说new HashMap()的时候数组还为创建
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 设置阈值，如果旧数组容量>0，说明已经创建过数组
// 那么尝试设置新数组长度和新扩容阈值
if (oldCap > 0) {
// 如果，旧数组容量>=(1<<30)，扩容阈值设置为Integer.MAX_VALUE
// 并返回旧数组，不进行数组扩容了
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 否则，新数组长度=旧数组长度的2倍
// 并判断，如果新数组长度 < (1<<30) 并且 旧数组长度 >= 16
// 则新的扩容阈值等于旧扩容阈值的两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 如果旧扩容阈值>0，说明new HashMap的时候设置了数组长度，但是还未初始化数组
// 那么就将设置的旧数组长度赋值给新数组长度
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 否则，说明旧数组长度=0并且旧扩容阈值=0，也就是默认的new HashMap
// 那么就用默认的比那辆来设置新数组长度和扩容阈值
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果新扩容阈值经过上面的计算后还是0
// 那么根据新的数组长度 * 填充因子，设置新的扩容阈值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 将计算好的新扩容阈值设置给threshold
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) // 重新进行hashkey计算，并写入数组
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode) // hash冲突，节点是树，则对红黑树进行操作
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // hash冲突，节点是链表，则对链表进行操作
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是懒加载，当new HashMap()时，并未真正的创建散列表，当put时会触发resize，在resize中创建散列表；
- 每次扩容的长度都是oldCap << 1，扩容阈值为填充因子 * 数组长度；
- 当数组长度为MAXIMUM_CAPACITY时，则不会对数组进行扩容，相对应的，将扩容阈值设置为threshold = Integer.MAX_VALUE；
- 扩容时会将旧的散列表数组写入到新的散列表中，写入新散列表时会做rehash操作newTab[e.hash & (newCap – 1)] = e；
常用方法
HashMap的常用方法基本上是对数组、链表和红黑树的操作，数组和链表在ArrayList与LinkedList中都有基本做法，所以就不过多记录了。
重要成员变量
// 链表对象数据结构
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;
}
}
// 红黑树数据结构
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);
}
/**
* Returns root of tree containing this node.
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
构造函数
// 默认构造函数
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 可初始化容量
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 可初始化容量和填充因子
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;
// 将传递进来的初始化容量修整为n^2
this.threshold = tableSizeFor(initialCapacity);
}
// 可从其他继承Map接口的对象初始化HashMap
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
// 将传递进来的初始化容量修整为n^2
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;
}
Get，Put，Remove方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// first = tab[(n - 1) & hash]是定位元素
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;
}
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) // 数组为null，调用resize创建数组
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) // hash不冲突，put元素
tab[i] = newNode(hash, key, value, null);
else { // hash冲突
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) // 如果put了重复元素
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) // 超过阈值，尝试链表转红黑树
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;
// 判断是否允许覆盖，并且value是否为空
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // 回调允许LinkedHashMap后置操作
return oldValue;
}
}
++modCount;
if (++size > threshold) // 添加元素后判断是否需要扩容
resize();
afterNodeInsertion(evict); // 回调以允许LinkedHashMap后置操作
return null;
}
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
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;
}
Get，Put，Remove方法都是基本上都是对数组、链表或红黑树的操作，Put时候会触发扩容，Remove时会先定位到元素，然后进行删除。
其他方法
HashMap还有很多其他方法，例如：putAll，putIfAbsent，size，isEmpty，containsKey，containsValue，clear，merge等等……
基本上都是对内部数据结构的操作，再次就不过多记录了，可以直接阅读源码。
总结
HashMap取ArrayList与LinkedList的有点，并综合了数组、链表和红黑树，提供了基于KeyValue的Hash表数据结构。
HashMap对hash算法与定位、hash冲突和hash表扩容方面的设计很巧妙，对时间复杂度和空间复杂度做到了极大的权衡。hash定位使用长度与hashcode进行计算得出位置，hash冲突使用链表法解决，扩容时会rehash。
HashMap是非常值得阅读的JDK源码，由于项目中基本都会使用，所以结合场景去阅读会非常深刻。
从实战的角度去学习hash算法，以及hash表数据结构，也接触了红黑树的概念，以及巩固了数组与链表的操作方法。
以上，是对HashMap源码分析的记录。
