HashMap源码分析，基于jdk1.8，附源码注释
HashMap源码详解
jdk1.8中HashMap是基于数组+链表+红黑树完成的 。
1.当我们执行 创建 HashMap 实例时
只是初始化的一些参数，并没有进行数组的创建；
初始化的参数：
(1) 、当使用HashMap 空构造器时，只是初始化了 “负载系数”，默认值为 0.75f
源码：
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
(2) 、当使用HashMap（int 容量） 一个参数构造器时，初始化了 “负载系数”（默认值为 0.75f），和容量，并且调用联合各参数的构造器
源码：
public HashMap(int initialCapacity) {
// 容量 负载系数 DEFAULT_LOAD_FACTOR是默认值0.75f
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
(3) 、当使用HashMap（int 容量，float 负载系数） 两个参数构造器时，会将负载系数存入变量loadFactor中，将容量先存入threshold（后续操作它会用于存储临界容量），方法tableSizeFor后续会单独说明，很简单很高大上。
源码：
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)//MAXIMUM_CAPACITY是数组的最大容量为1<<30
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
**
2.在向HashMap中put数据时，首先会先把计算key的hash值，然后调用putVal实现键值对的增加**
源码：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
（1）、计算hash方法hash(Object key)
首先判断key如果是null则key值为0（HashMap是允许存一个key为null的键值对）；
其次当key不是null时，它会计算出key的哈希值，并将hash值 与 其哈希值进行逻辑左移16位 进行异或运算；
为什么需要这么运算呢？
一般我们HashMap存储的值并不会太多，列如存储200个键值对那么计算出数组容量为256（后面会说到怎么算），255转换为2进制为 11111111（前面用0补齐）；当我们用hash 与 255（(n - 1) & hash）计算下标时只有后八位参与到运算，如下计算：
01100100 10000011 00010011 01111001 --1686311801
00000000 00000000 00000000 11111111 --255
00000000 00000000 00000000 01111001 --进行&运算结果 121
从上可看出 不管前面 32 位是什么 只要与255进行&运算都不影响结果，只是后面8位决定最后值，
所以为了使hash更多的位参加运算，使用了（h ) ^ (h >>> 16） 这样就是首先将算出hash值进行一次^运算：例如
01100100 10000011 00010011 01111001 --1686311801
00000000 00000000 01100100 10000011 --25731（高16位 (h >>> 16））
01100100 10000011 01110111 11111010 ---（h ) ^ (h >>> 16）结果 （1686337530）
在于255进行&运算显而易见 后8位参与计算的数据收到了于是数据 9~16位影响
00000000 00000000 00000000 11111010 --进行&运算结果 250
源码：
```java
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
（2）、真正的放入键值对方法putVal
1）.首先通过判断table（Node数组）是否为null，若为null说明数组容器未进行初始化，需要调用 resize()方法进行初始化数组容器（数组扩容也是调用此方法）。
2).其次当数组容器已经初始化完成,通过 (n - 1) & hash 计算出 此key对应的数组下标，判断此处下标处是否存在数据，若不存在怎直接newNode() 放入此处；
若存在（发生了hash碰撞）则进行后续处理：
#如果数组此处下标的链表第一个Node的key与我们要存储键值对的key相同，那么直接将值替换（暂时这么理解，实际是会先存储此Node，后面判断相同的key是不是需要替换再进行实际操作。）
#如果数组此处下标的链表第一个Node的key与我们要存储键值对的key不同，判断是不是红黑树，是树则进行树添加操作，这里不做说明，太复杂，后续文章分析。
#如果数组此处下标的链表第一个Node的key与我们要存储键值对的key不同，也不是红黑树；循环此链表，存在key相同则替换，不同则追加到这个链表的尾部，满足转红黑树条件就转红黑树。
具体细节看下面源码，里面有详细注释。
源码：
/**
* Implements Map.put and related methods
*实现Map.put和相关方法
* @param hash key 的hash值
* @param key 原始key
* @param value 要存储的value值
* @param onlyIfAbsent 如果true 不覆盖相同key的value值，保留老的oldValue
* @param evict 如果为false，则表处于创建模式.
* @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;
/*
*第一次加入数据 table一定是null，走此条件
*/
if ((tab = table) == null || (n = tab.length) == 0)
//resize()主要用于对数组的初始化和扩容，此处看做初始化一个数组，一般默认长度16
n = (tab = resize()).length;
/*
*通过 与（&）运算将算出此hash应放在数组什么位置
*1.与 运算 是 两个操作数中位都为1，结果才为1，否则结果为0（都为2进制的数）
*2.（n-1） 是因为实际数组长度下标的关系所得，列如数组长度是16，那么下标为0~15。
*3.(n - 1) & hash 的到结果一定不会 大于（n-1）【假设长度为16 （15的二进制为 00001111）因为是与运算所以 除去后四位其他位一定是0】
*4.p = tab[i = (n - 1) & hash] 如果是null 说明数组下标为“i” 的位置没存过数据（此位置未发生过hash碰撞），
* 可直接存放。否则将 tab[i] 存在的数据赋给 p。作后续处理进入 else
*/
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
/*
*发生hash碰撞处理
*发生hash碰撞有三种情况，
* 第一种是hash值相同【p.hash == hash】并且key相同，这种视为key相同；-直接将p（此node节点）赋给e
* 第二种是hash相同，key不同，这种视为不同（先不考虑这种，视为一般不会发生，hashcode算法问题引起的）；
* 第三种是hash不同
*/
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);
/*
*第二种是hash相同，key不同，这种视为不同（先不考虑这种，视为一般不会发生，hashcode算法问题引起的）；
*第三种是hash不同
*/
else {
/**
*进行链表的循环
*1.如果存在hash和key都相同说明 ，是相同的 key，那么将这个链表里的这个node赋值给e，后续根据条件是替换value或者不替换
*2.如果循环到尾部还是没有相同的key（hash和key都相同），那么将创建一个新的node并且放在链表尾部，
* 如果满足转红黑树条件之一的条件（binCount >= TREEIFY_THRESHOLD - 1）则调用转红黑树方法（不一定会转，需要满足另一个条件）
*/
for (int binCount = 0; ; ++binCount) {
/*
*如果 (e = p.next) == null 说明p（数组中i位置的node链表中的node）没有下一个几点，也就是到链表的尾部了
*走到此处说明没有相同的key 不需要做类似替换value操作，跳出for循环
*/
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//链表转红黑树的条件之一若满足则调用转红黑树方法尝试转化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//存在hash和key都相同说明 ，是相同的 key，那么将这个链表里的这个node赋值给e
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
/*e (node)这个Node不为null，就是有相同的key，需要进行后续处理
*如果 老的值oldValue等于null或者 onlyIfAbsent等于false，只要满足其中一个条件就进行替换，反之则不替换，此putVal方法结束
*
*e (node)这个Node为null则不仅如此if 继续执行后续方法
*/
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//增加、覆盖、删除都会增加，可以理解为对HashMap数据操作的次数。
++modCount;
//如果 size（存储键值对个数）大于使用负载系数计算出的临界值则进行扩容运算
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
3、数组扩容方法和初始化数组方法resize()
每次扩容是原容量的2倍（满足数组长度为2的n此幂）
首先先说明几个参数
//存放旧数组（扩容前）
Node<K,V>[] oldTab = table;
//存放旧数组长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//存放旧数组扩容阈值
int oldThr = threshold;
//存放新数组长度和扩容阈值
int newCap, newThr = 0;
(1) 先判断扩容前数组（后面称呼为旧数组）
1) 如果等于null则让newCap等于初始长度（默认16），
newThr 使用数组长度默认值和加载系数进行计算出阈值（DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY）
2) 如果不等于null，判断oldCap >0说明数组创建过，然后此条件中如果oldCap大于等于数组最大规定长度则不进行扩容，直接结束扩容方法；反之oldCap小于数组最大规定长度则计算出新数组长度（满足新数组长度小于最大长度，大于最小长度）和阈值。（扩容见代码使用的是位运算）
(2) oldThr > 0使用非空构造器指定了HashMap容量（一般是初始化用得到）。
(3) 接下来使用newCap创建新的node数组
(4) 将旧数组数据“复制”到新数组中，这个“复制”过成相较于jdk1.7比较好的地方是不需要根据hash值全部重新计算每个键（key）在新数组的位置，**而是根据hash值二进制与旧数组容量值-1的二进制做&运算（(e.hash & oldCap)）若结果为零形成一个链表，不为零（1）形成一个链表，然后把为零的链表放在新数组中与旧数组索引相同位置，不为零的链表放在新数组中位置为旧数组的位置+旧数组的容量。
源码：
/**
* 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;
//oldCap大于0说明此HashMap创建过数据（曾经put过数据）
if (oldCap > 0) {
//老的数组（oldCap）长度大于等于所规定的最大长度则不进行扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
/*得到扩容后所需的数组长度 满足<=MAXIMUM_CAPACITY && 扩容前的数组长度>=初始的数组长度（一般默认长度16）
*则继续进行扩容运算
*/
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//计算出 下一个要调整大小的大小值（容量*负载系数）即 阈值
newThr = oldThr << 1;
}
else if (oldThr > 0) // 使用非空构造器指定了HashMap容量
newCap = oldThr;
//一般是初次是罹患数组使用默认长度16 和 负载系数0.75f
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//此处只有使用构造器指定了HashMap容量才会用到
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;
//就得数组不是null（等于null一般是初次put）进行如下运算
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//j位置不存在链表或者树则直接计算出新的数组所处的位置
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;
/**一个精髓
*将hash 与 oldCap 进行 与运算，
* 例如oldCap=16 e.hash & (00010000 ) 取决于 e.hash 倒数第五位是1 还是0来得到进入哪种处理方法
*若是0 则存入 loHead和loTail,余下则通过loTail存入loHead形成链表，在将loTail指向loHead最后的node
*若是1 则存入 hiHead和hiTail,余下则通过hiTail存入hiHead形成链表，在将hiTail指向hiHead最后的node
*
*最后将loHead存入 newTab[j] ；将hiHead存入newTab[j + oldCap]
* loHead存入了新数组中与老数组相同的下标位置（命名位置1）
* hiHead存入了新数组中与（老数组相同的下标+老数组长度）的位置 （命名位置2）
* 位置1 与 位置2 的2进制中就是最高位不同 例如
* 10（00000000 00000000 00000000 00001010）
* 与
* 26（00000000 00000000 00000000 00011010）
*/
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;
}
4、 通过给定的目标容量，返回2的n次幂容量-tableSizeFor(int cap)
使用位运算计算出符合2的n次幂的标准容量。
源码：
/**
* Returns a power of two size for the given target capacity.
*通过位运算 给定的目标容量，返回2的n次幂，看代码返回的就是数组长度
*/
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;
}
具体解析：例如输入24，返回符合2的n次幂的标准容量
(1) int n = cap - 1;
n=23 二进制为
00000000 00000000 00000000 00010111
(2) n |= n >>> 1;
00000000 00000000 00000000 00010111 --23
00000000 00000000 00000000 00001011 --23逻辑右移一位（11）
00000000 00000000 00000000 00011111 --23|23逻辑右移一位（31）
(3) n|=n >>>2;
00000000 00000000 00000000 00011111 --31
00000000 00000000 00000000 00001111 --31逻辑右移一位（15）
00000000 00000000 00000000 00011111 --15|31逻辑右移一位（31）
（4）n |= n >>> 4;
00000000 00000000 00000000 00011111 --31
00000000 00000000 00000000 00001111 --31逻辑右移一位（15）
00000000 00000000 00000000 00011111 --15|31逻辑右移一位（31）
（5） n |= n >>> 8;
.
.
.
（6）n |= n >>> 16;
.
.
.
如上面的过程，都是类似计算，最后结果一定是2的n次幂，并且计算速度比较快。
5.删除数据（简单描述，附源码注释，比较简单不多说了）
（1） 根据key响应hash值找到索引
（2） 不存在数据返回null
（3） 存在数据，如果第一个node（链表中可能存在多个Node，也可能就一个Node）就是我们需要的则将你的p 赋给上面一行的node变量，那么后面将table[i] 直接指向node变量的next。排除 node变量形成不引用，最后垃圾回收会干掉他。
（4）若为红黑树则按照树删除（不作讲解）
源码：
/**
* Removes the mapping for the specified key from this map if present.
*删除HashMap元素，删除成功返回key对应的value值，否则返回null
* @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;
}
/**
* Implements Map.remove and related methods
*实现删除HashMap元素，删除成功返回key对应的value值，否则返回null
* @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;
//数组不为空 && 数组长度大于0 && 用此hash& (n - 1) 算出的数组下标值i，数组i位置存在值
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;
/*如果第一个node（链表中可能存在多个Node，也可能就一个Node）就是我们需要的则将你的p 赋给上面一行的node变量
*那么后面将table[i] 直接指向node变量的next。排除 node变量形成不引用，最后垃圾回收会干掉他
*/
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
/*链表长度大于1，继续循环查找，
* 循环查找中会将 循环过的Node引用赋给 P ，将找到的得当前所需删除的Node 引用赋给 node变量
* 然后将 p的next 与 node的next相连接。排除 node变量形成不引用，最后垃圾回收会干掉他
* 最后返回删除的 node
*/
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;
}
总结：以上就是HashMap总结，包括添加数据，扩容，删除数据。（本文章不包含红黑树部分，后续会更新）
上一篇： 【Java集合源码剖析】ArrayList源码剖析
下一篇： HashMap相关知识