- https://blog.csdn.net/v123411739/article/details/78996181/
- 分析put流程
HashMap<key,value>
装箱
key->hashCode：int->return key == null ? 0 : (h = key.hashCode()) ^ h >>> 16
1.执行hashCode位运算，计算出具体的数组index下标
public V put(K key, V value) {
return this.putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return key == null ? 0 : (h = key.hashCode()) ^ h >>> 16;
}
2.执行putValu进行值计算
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
1.校验table是否为空或者length等于0，如果是则调用resize方法进行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
2.通过hash值计算索引位置，将该索引位置的头节点赋值给p，如果p为空则直接在该索引位置新增一个节点即可
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
3.判断p节点的key和hash值是否跟传入的相等，如果相等, 则p节点即为要查找的目标节点，将p节点赋值给e节点
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
4.判断p节点是否为TreeNode, 如果是则调用红黑树的putTreeVal方法查找目标节点
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
5.走到这代表p节点为普通链表节点，则调用普通的链表方法进行查找，使用binCount统计链表的节点数
for (int binCount = 0; ; ++binCount){}
else {
走到这代表p节点为普通链表节点，则调用普通的链表方法进行查找，使用binCount统计链表的节点数
for (int binCount = 0; ; ++binCount) {
// 6.如果p的next节点为空时，则代表找不到目标节点，则新增一个节点并插入链表尾部
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 7.校验节点数是否超过8个，如果超过则调用treeifyBin方法将链表节点转为红黑树节点，
// 减一是因为循环是从p节点的下一个节点开始的
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
// 8.如果e节点存在hash值和key值都与传入的相同，则e节点即为目标节点，跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e; // 将p指向下一个节点
}
}
// 9.如果e节点不为空，则代表目标节点存在，使用传入的value覆盖该节点的value，并返回oldValue
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // 用于LinkedHashMap
return oldValue;
}
}
++modCount;
// 10.如果插入节点后节点数超过阈值，则调用resize方法进行扩容
if (++size > threshold)
resize();
执行get方法，如果是红黑树，则调用红黑树的查找目标节点方法getTreeNode
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;
// 1.对table进行校验：table不为空 && table长度大于0 &&
// table索引位置(使用table.length - 1和hash值进行位与运算)的节点不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 2.检查first节点的hash值和key是否和入参的一样，如果一样则first即为目标节点，直接返回first节点
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 3.如果first不是目标节点，并且first的next节点不为空则继续遍历
if ((e = first.next) != null) {
if (first instanceof TreeNode)
// 4.如果是红黑树节点，则调用红黑树的查找目标节点方法getTreeNode
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// 5.执行链表节点的查找，向下遍历链表, 直至找到节点的key和入参的key相等时,返回该节点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
// 6.找不到符合的返回空
return null;
}
3.DEFAULT_INITIAL_CAPACITY=16?
在线位运算
在线二进制转换
以下仅演示低4位的位运算，其实在jdk1.8的时候位把高28位的运算都加入，以此来降低hash冲突的概率
如果length默认是16，那么length-1=15，执行下面的与运算
h&length-1
15 二进制： 1111
& 0 二进制： 0000
----------------------------
1111
====================
15 二进制： 1111
& 1 二进制： 0001
----------------------------
1110
如果length默认是15，那么length-1=14，执行下面的与运算
h&length-1
14 二进制： 1110
& 0 二进制： 0000
----------------------------
1110--------------------------->1110跟下面这个值一样
====================
14 二进制： 1110
& 1 二进制： 0001
----------------------------
1110--------------------------->1110跟上面这个值一样
综上分析，如果默认值不是16，或者说不是2的幂指数，那么执行位运算之后，得出的结果可能是相同的，也就是哈希碰撞的概率变高
3.TreeNode 红黑树（高性能的平衡树）来保存冲突节点O(n)->提高到O(logn)
可以考虑下时间复杂度是怎么计算的，这里备注下
4.是否每一个节点都是红黑树？
不是，为了效率更高，并不会直接每个节点都使用红黑树，因为红黑树的初始化复杂，而且有很多的左旋右旋，本身来说，构建复杂耗时。
当节点超过8的时候，才会转成红黑树
目的就是为了让查找效率跟高效
5.HashMap线程安全问题
多线程插入、删除、扩充操作数据的时候，会有多线程安全问题，
可以参考HashTable实现策略
或者SparseArray
6.HashTable 源码分析
基本来说就是把整个HashMap加了锁，其他跟HashMap基本一致
7.ConcurrentHashMap跟HashTable、HashMap区别
锁的范围精确到对应链表，而不是整个HashMap
7.SparseArray 源码分析 跟HashMap区别
8.HashMap为什么会发生死循环
https://baijiahao.baidu.com/s?id=1675991555833901875&wfr=spider&for=pc
待总结
网友评论