HashMap源码分析
HashMap源码分析
总结
hashMap中用数组存储数据。初始值是16。每次扩容2倍。当数据>12(0.75 * 数组的长度)的时候会发起扩容。数组中存储的是Enty。默认情况下是单向链表。当链表长度>8的时候就会转型成红黑树(为了保证查询的效率，红黑树查询比单项链表高)。当红黑树链表长度<6则转成单向链表。
属性值
//负载系数
final float loadFactor;
//阈值，要调整数组大小的临界值 (capacity * loadFactor)
int threshold;
//容器包含的数据量
transient int size;
//数组，存储数据的数组，由此可见hashMap核心实现是数组
transient Node<K,V>[] table;
/*******/
//默认的数组大小 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大的容量 好几亿
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//树形化阈值
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
//最小树形化 数组长度
static final int MIN_TREEIFY_CAPACITY = 64;
构造方法
//默认的 会初始化数组长度16
public HashMap() {
//负载因子 loadFactor = 0.75
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
//会给传入的长度 进行包装
public HashMap(int initialCapacity, float loadFactor) {
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
这段代码确保了自定义长度的hashMap，会找到一个离cap最新的2的幂次方的值。（为了保证二进制低位都是1）
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;
}
put(key,value)
逻辑图
<img src="/Users/kudang0422/Library/Application Support/typora-user-images/image-20200921203400107.png" alt="image-20200921203400107" style="zoom:50%;" />
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
通过hashCode计算key的hash值，从而计算出key在数组中的位置 <span style="color:red" > 具体为啥要 右移16? => 采用了扰乱算法，保证低位数据的有效性，目的是减少hash碰撞</span>
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
putVal 核心
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
//判断内部数组是否为null 如果为null调用扩容方法
if ((tab = table) == null || (n = tab.length) == 0)
//对内部数组进行初始化 n = 16
n = (tab = resize()).length;
// tab[i = (n - 1) & hash]) = 查询key对应的hash值在数组中的下标
//判断 (n - 1) & hash key对应的数组下标是否有值
if ((p = tab[i = (n - 1) & hash]) == null)
//如果为null 赋值 newNode是一个单向链表结构
tab[i] = newNode(hash, key, value, null);
else {
//有值
Node<K,V> e; K k;
//判断 hash值对应的Node中的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 {
//循环 链表Node
for (int binCount = 0; ; ++binCount) {
//找到链表下一个是否为null
if ((e = p.next) == null) {
//如果为null直接添加在链表后面
p.next = newNode(hash, key, value, null);
//判断是否>= 8个 链表长度
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//如果是转化数组为 tree数组
treeifyBin(tab, hash);
break;
}
//如果不为null 判断当前节点key 与 传入key是否相同 一样直接跳出循环
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;
//++size 先自增然后判断 自增后的值 > 12（初始化的时候设置的 16*0.75）
if (++size > threshold)
//这里触发扩容
resize();
afterNodeInsertion(evict);
return null;
}
resize()扩容
final Node<K,V>[] resize() {
// oldTab=null
Node<K,V>[] oldTab = table;
//老的数组长度 oldCap = 0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//老的阈值 oldThr = threshold = 0 int类型默认为0
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 {
// 设置默认长度为16 设置数组长度为16
newCap = DEFAULT_INITIAL_CAPACITY;
//设置阈值 为 newThr= 16*0.75 =12
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 = 12
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//初始化数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//属性table 指向初始化的数组
table = newTab;
//这里进行扩容 进行复制
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
//当前数据Node
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
//计算新的容量下 当前node的下标
newTab[e.hash & (newCap - 1)] = e;
//如果是红黑树
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { //其实这里的作用是重新计算hash在新的数组的下标，1.7的时候是所有都重新计算，1.8的时候优化了算法。前提容量是2的幂，通过判断oldCap二进制对应的幂下标是否为0来判断是否需要重新计算。详情见下面容量为什么是2的幂。
//低位Node链表
Node<K,V> loHead = null, loTail = null;
//高位Node链表
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;
}
//位置加+old的容器
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
treeifyBin() 链表 转换成 树形结构 （先循环转成双向链表，然后在转成红黑树）
//tab 数组对象 hash为 需要插入的key的值
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index;
Node<K,V> e;
//n = 16 MIN_TREEIFY_CAPACITY = 64（初始化） 这是为了避免在哈希表建立初期，多个键值对恰好被放入了同一个链表中而导致不必要的转化。
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
//扩容
resize();
// e = Enty() 当前数组下标对应的enty index = (n - 1) & hash下面会用到
else if ((e = tab[index = (n - 1) & hash]) != null) {
//定义头节点 head 与 尾节点tail
TreeNode<K,V> hd = null,tl = null;
do {
//当前节点转化为 TreeNode
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
//初始化头节点
hd = p;
else {
//设置当前节点的 前/后节点
p.prev = tl;
tl.next = p;
}
//当前节点设置为 尾节点。实现了从单向链表 转化为 双向链表
tl = p;
//指向e的后一个节点 直到最后一个
} while ((e = e.next) != null);
//如果头节点不为null，则进行树形化
if ((tab[index] = hd) != null)
//树形化
hd.treeify(tab);
}
}
get(key,value) 获取值
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 &&
//获取hash对应的数组下标位置
(first = tab[(n - 1) & hash]) != null) {
//如果hash值相等 并且 (key相等 或者 key的值相等)
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//如果第一个不是，获取下一个node
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;
}
位运算
-
" << " 左移 各二进制全部左移若干位，高位丢弃低位补0.
例如: 6 << 2 6向左移动位.
6的二进制是 int类型在java中占用4个字节，一个字节占8位。所以 6占用了 4*32个位。而6=1x22+1x21+0x2^0
高位 ---------------------- 低位 0000 0000 0000 0000 0000 0000 0000 0110高位丢弃
--丢弃-- --00--00 0000 0000 0000 0000 0000 0000 011000 0000 0000 0000 0000 0000 0000 0110低位补0
-补充0- 00 0000 0000 0000 0000 0000 0000 0110 -00-最终结果
0000 0000 0000 0000 0000 0000 0001 10006<<2 = 1x2^4 + 1x2^3 +0x2^2 + 0x2^1 + 0x2^0 = 24
左移经常被用来* (2 ^ n)的扩容运算。 例如 6 * 2^2 = 24 6 * 2^(移动的位数)
-
">>" 右移 位数向右移动，低位丢弃高位补0
与左移相反。多数用来 / (2 ^ n)的运算。
-
& 位与 当运算符两边相同位置都是1时，结果返回1，其他情况都返回0。
例如 3&5
3
0000 0000 0000 0000 0000 0000 0000 00115
0000 0000 0000 0000 0000 0000 0000 01013&5 = 1 其中3和5的只有第一位共同为1，所以3 & 5 = 1
0000 0000 0000 0000 0000 0000 0000 0001 -
| 位或 当运算符两边相同位置都是0时，结果返回0，其他情况都返回1
例如 3 | 5 = 7 后3位都不全是0 所以返回1
```java
0000 0000 0000 0000 0000 0000 0000 0111
```
-
~ 位非 1变成0 0变成1
例如 ~3 = -4
1111 1111 1111 1111 1111 1111 1111 1100负数需要 先转码然后补码
-
^ 位异或 当运算符两边相同位置都是相同，结果返回0，不相同时返回1
例如3 ^ 5
3
0000 0000 0000 0000 0000 0000 0000 0011
5
0000 0000 0000 0000 0000 0000 0000 0101
3^5 = 6
```java
0000 0000 0000 0000 0000 0000 0000 0110
```
jdk1.8中 hash() 为什么要异或右移16位
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
最主要的目的是为了减少hash的碰撞,让数据均匀的分布在数据中
首先key的hashCode值是通过native方法算出来的int类型。int类型在java中占用4个字节总共32位。HashMap的核心是数组，通过 hash() & (16-1)* 计算出hash在数组中的位置（为什么这么计算也是有原因的）。假如就用原始的hashCode去做运算。
原始hashCode 二进制数据随机的一个
0000 0000 0000 0011 0000 0000 0000 0000
15 二进制
0000 0000 0000 0000 0000 0000 0000 1111
hash() & (15) &运算符只有都是1才展示1，其他都展示0。如果hashCode的计算值低位相同高位不断变化其实是没有任何意义的，因为&只取低4位数据，那么这些数据都会映射到同一个数组下标上。所以为了让这些低位相同高位不同的数据映射到不同的数组下标。
采用了扰动函数h = key.hashCode()) ^ (h >>> 16)。这个函数的意思是，hashCode右移16位(取32位数据的一半，也就是16位)，获取的高位数据与原数据做异或运算。
//原始code
0000 0000 0000 0011 0000 0000 0000 0000
//右移16位
0000 0000 0000 0011
//相互做 ^ 运算
0000 0000 0000 0011 0000 0000 0000 0011
通过扰动函数重新计算的结果低4位有效，再进行 &15 运算，从而降低了hash碰撞。
jdk1.8中Hashmap中数组的容量为什么是2的幂？
源码中计算key在数组中的下标 (n - 1) & hash其中n是数组的容量。
-
网上说，位运算比基本的运算快。(通过对比十亿此运算对比，位运算比基本的运算快了几毫秒。有的时候反而出现基本运算比较快的情况。)
-
取余 = (n - 1) & hash 一个2的幂的数-1 与上hash值，相当于对这个hash取余。
-
扩容的时候采用了优化算法。
Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; //1.这里 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; }这里是扩容后，当容器长度变化，对应的hashCode的下标也会变化。其实循环每一个数据，分别执行 newTab[e.hash & (newCap - 1)] = e;也是可以的。但是这样子效率比较低。1.8做了一些优化。他定义了2个链路，一个是 loHead代表的是low位=低位，这个Node链表的下标位置不需要改变。一种是hiHead代表了在新的数组中需要改变下标位置 newTab[j + oldCap] = hiHead在原有的下标位置上+oldCap。可以看到这里并没有对所有的数据轮询计算，效率明显提升了。
为什么？
e.hash & oldCap == 0
因为数组的长度是2的幂。假如数组长度为16。那么oldTable中的数据在做下标运算的时候
e.hash & (16-1) 等价于 e.hash & (15)
0000 0000 0000 0000 0000 0000 0000 1111而&运算符是比较的位数上是否都为1，如有有一个为0都是0.。而e.hash & 16
0000 0000 0000 0000 0000 0000 0001 0000 4 3210判断的是2的4次方，也就是二进制的第4位的值是0还是1。如果是0那么代表扩容一倍后，假如数组长度变为32。e.hash & (32-1)
31的二进制
0000 0000 0000 0000 0000 0000 0001 1111 4 3210一个第4位为0的hashCode &上(32-1)的第4位都是0。所以4位为0的hashCode，扩容后数组下标不会有任何变化。
而第4位=1的hashCode，&上31的二进制，第4位肯定是1，而其他的位数都不会变化。所以&后的值只是在原有的基础上加上第4位的1，而1*2^4 = 16。所以与之相对的数组下标等价于 j + oldCap。原有的数组位置+老容器长度。
- hash与上一个数，&的另一个数最好低位全是1，这样子hash值才能均匀分布在数组中。比如说数组长度为16 = 2^4。16-1 =15
15的二进制是
0000 0000 0000 0000 0000 0000 0000 1111
位与操作，当运算符两边相同位置都是1时，结果返回1，其他情况都返回0。(n - 1) & hash 2的幂-1的二进制低位都是1。位于操作能够保证数据的分布均匀。
如果是18。18并不是2的幂。18-1 = 17二进制为
0000 0000 0000 0000 0000 0000 0001 0001
17位与上任何一个数
0000 0000 0000 0000 0000 0000 0001 0001 ==17
0000 0000 0000 0000 0000 0000 0001 0000 ==16
0000 0000 0000 0000 0000 0000 0000 0001 == 1
0000 0000 0000 0000 0000 0000 0000 0000 == 0
只能是17 16 1 0 这4种，导致hash都会集中在这4个数组下标中，最终导致数据分配不均匀。
hashMap如何进行扩容的？
见源码中，resize().
hash冲突你还知道哪些解决办法？
-
链表将所有hash相同的都存在同一个链表中(hashMap)
-
再哈希法 再哈希法其实很简单，就是再使用哈希函数去散列一个输入的时候，输出是同一个位置就再次哈希，直至不发生冲突位置。 (布隆过滤器)
其他的没看过实现类，暂不列举。
0.75作为HashMap的加载因子呢？
转载一篇文章，里面有说明，因没有实操暂放在这里以后验证
https://zhuanlan.zhihu.com/p/157639240
多线程环境下可能会导致的问题
-
put后get为null
```java resize() { Node<K,V>[] oldTab = table; ... for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { //这里在线程环境下为了尽快gc，在多线程环境中一个线程A复 制 一个线程B获取，从而导致B线程获取到的数据是null oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; .... } ``` -
putd导致元素丢失
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; //这里导致问题 //当2个线程A，B对同一个hash相同的不同对象进行put操作，会导致其中一个丢失 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);
