HashMap全解
1. HashCode为什么选择31作为乘数
HashCode是32位的有符号数
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
- 31 是一个奇质数，如果选择偶数会导致乘积运算时数据溢出
- (为什么不使用31,33,37)乘积运算可以使用位移提升性能，31 * i == (i<<5) - i
测试不同的乘数的碰撞检测：
2. HashMap
2.1 简单的HashMap
Map用于存放数据的数据结构，即通过key、value的形式进行读取。我们需要保证key唯一，一个比较好的方法就是使用 HashCode，但是HashCode的范围为（ - 2^31 到 2^31），我们不可能去创建这么大的数组，所以需要进行运算来保证HashCode能够映射到具体的数组上。
// 初始化一组字符串
List<String> list = new ArrayList<>();
list.add("jlkk");
list.add("lopi");
list.add("小傅哥");
list.add("e4we");
list.add("alpo");
list.add("yhjk");
list.add("plop");
// 定义要存放的数组
String[] tab = new String[8];
// 循环存放
for (String key : list) {
int idx = key.hashCode() & (tab.length - 1); // 计算索引位置
System.out.println(String.format("key值=%s Idx=%d", key, idx));
if (null == tab[idx]) {
tab[idx] = key;
continue;
}
tab[idx] = tab[idx] + "->" + key;
}
// 输出测试结果
System.out.println(JSON.toJSONString(tab));
这样能够将数据映射到指定位置中 ，但是存在一定问题
- 数组如何进行初始化，因为计算索引过程中，是tab.length -1（111之类）。数组长度要为2的幂次方。
- 数组越小碰撞越大，数组越大碰撞越小，时间和空间如何取舍
- 如何使得数据分布更加均匀
- 不断增加元素超过数组的长度时，如何扩容
- 当多个元素映射到同一个位置，如何处理
2.2 扰动函数
为了使得数据分布更加均匀， hash采用扰动函数，即
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
补：>> 有符合右移 >>>无符合右移（始终填0
使用哈希值的高半区和低半区做异或，混合原始哈希码的高位和低位，以此来加大低位区的随机性。让数据元素更加均衡的散列，减少碰撞。
2.3 初始化容量和负载因子
数组如何进行初始化，因为计算索引过程中，是tab.length -1（111之类）。数组长度要为2的幂次方。
2.3.1 找数组长度的 2的幂次方
Hash初始化， 会通过移位操作把自最高位开始1后为全一， 及11111， 后面加上1之后为2的幂次方。
public HashMap(int initialCapacity, float loadFactor) {
...
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
tatic 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;
}
2.3.2 负载因子
负载因子，指的就是数据达到数组容量的多少进行，扩容。 原因在于，在相同的位置可能有多个元素，不可能正好把数组填满。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
2.4 数组扩容
数据扩容本身是很简单，但如何把之前已经存放的元素放到新数组中是一个问题。
2.4.1 原数组元素的新索引
在jdk1.7之前是采用重新计算哈希值的方法。在jdk1.8中，可以发现。原哈希值与扩容新增出来的长度16，进行&运算，如果值等于0，则下标位置不变。如果不为0，那么新的位置则是原来位置上加16。
2.4.2 数据迁移
通过移位操作对新的二次幂新增位进行判断，如果为1则需要移动数据， 为0则保持不变。（hash是确定的， 而索引是 hash & (nums.length - 1)， 所以只需要判断新位，不用重新计算。例如， 扩充16， oldCap = 1111。
hash & oldCap == 0
2.4.3 源代码学习
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// Cap 是 capacity 的缩写，容量。如果容量不为空，则说明已经初始化。
if (oldCap > 0) {
// 如果容量达到最大1 << 30则不再扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 按旧容量和阈值的2倍计算新容量和阈值
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
// initial capacity was placed in threshold 翻译过来的意思，如下；
// 初始化时，将 threshold 的值赋值给 newCap，
// HashMap 使用 threshold 变量暂时保存 initialCapacity 参数的值
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 这一部分也是，源代码中也有相应的英文注释
// 调用无参构造方法时，数组桶数组容量为默认容量 1 << 4; aka 16
// 阈值；是默认容量与负载因子的乘积，0.75
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// newThr为0，则使用阈值公式计算容量
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"})
// 初始化数组桶，用于存放key
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 如果旧数组桶，oldCap有值，则遍历将键值映射到新数组桶中
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)
// 这里split，是红黑树拆分操作。在重新映射时操作的。
((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;
// 这里是链表，如果当前是按照链表存放的，则将链表节点按原顺序进行分组{这里有专门的文章介绍，如何不需要重新计算哈希值进行拆分《HashMap核心知识，扰动函数、负载因子、扩容链表拆分，深度学习》}
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;
}
2.5 数据插入
问题:
- 如果出现哈希值计算的下标碰撞了怎么办？
- 如果碰撞了是扩容数组还是把值存成链表结构，让一个节点有多个值存放呢？
- 如果存放的数据的链表过长，就失去了散列表的性能了，怎么办呢？
- 如果想解决链表过长，什么时候使用树结构呢，使用哪种树呢？
2.5.1 插入流程
整个数据插入流程为：
-
进行哈希扰动获取哈希值。
(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); -
判断表是否为空，或者长度是否为0， 如果是则扩容。 （为空代表未初始化， 为0代表初始化了一个长度为0的空数组）
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
-
根据哈希值计算下标，如果对应下标正好没有存放数据，则直接插入即可否则需要覆盖。
tab[i = (n - 1) & hash]) -
如果不存在下标，判断tab[i]是否为树节点，否则向链表中插入数据，是则向树中插入节点
-
通过for循环插入链表中，如果链表中插入节点的时候，链表长度大于等于8，则需要把链表转换为红黑树。
treeifyBin(tab, hash); -
最后所有元素处理完成后，判断是否超过阈值；
threshold，超过则扩容 -
treeifyBin,是一个链表转树的方法，但不是所有的链表长度为8后都会转成树，还需要判断存放key值的数组桶长度是否小于64MIN_TREEIFY_CAPACITY。如果小于则需要扩容，扩容后链表上的数据会被拆分散列的相应的桶节点上，也就把链表长度缩短了。 -
重新扩容之后，需要元素拆分，如果拆分之后树节点元素小于6个，则要转为链表
2.5.2 源代码学习
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;
// 初始化桶数组 table，table 被延迟到插入新数据时再进行初始化
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;
// 如果键的值以及节点 hash 等于链表中的第一个键值对节点时，则将 e 指向该键值对
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果桶中的引用类型为 TreeNode，则调用红黑树的插入方法
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;
}
// 条件为 true，表示当前链表包含要插入的键值对，终止遍历
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 判断要插入的键值对是否存在 HashMap 中
if (e != null) { // existing mapping for key
V oldValue = e.value;
// onlyIfAbsent 表示是否仅在 oldValue 为 null 的情况下更新键值对的值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 键值对数量超过阈值时，则进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
2.5.3 链表转红黑树
jkd1.8之前，在哈希碰撞的情况下存放多个数据是采用链表。但从链表中定位元素的时间复杂度为O(n)，链表越长性能越差。在jdk1.8中会把大于等于8个节点的数据转为自平衡的红黑树结构，红黑树的元素定位时间复杂度为O(logn)。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 这块就是我们上面提到的，不一定树化还可能只是扩容。主要桶数组容量是否小于64 MIN_TREEIFY_CAPACITY
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
// 又是单词缩写；hd = head (头部)，tl = tile (结尾)
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);
}
}
- 链表树化的条件有两点；链表长度大于等于8、桶容量大于64(保证有必要进行树化，因为红黑树的空间复杂度更高)，否则只是扩容，不会树化。
- 先进行树化 ， 再进行红黑树转化
2.5.4 红黑树转链表
利用链表转树节点时保持的连接信息
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
// 遍历TreeNode
for (Node<K,V> q = this; q != null; q = q.next) {
// TreeNode替换Node
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
// 替换方法
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
return new Node<>(p.hash, p.key, p.value, next);
}
2.6 数据查找
数据查找的过程的插入过程类似
- 计算哈希扰动
- 判断是否初始化或者为0
- 计算元素下标
- 判断当前为树还是链表节点，分别调用对应查找方法
源码如下：
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;
// 判断桶数组的是否为空和长度值
if ((tab = table) != null && (n = tab.length) > 0 &&
// 计算下标，哈希值与数组长度-1
(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) {
// TreeNode 节点直接调用红黑树的查找方法，时间复杂度O(logn)
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;
}
2.7 删除
源码如下：
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
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;
// 定位桶数组中的下标位置，index = (n - 1) & hash
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 指向该节点
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;
}
2.8 遍历
遍历是无序的，但每次使用不同方式遍历包括keys.iterator()，它们遍历的结果是固定的
2.8.1 EntrySet()遍历
for (HashMap.Entry<String, Integer> entry : map.entrySet()) {
System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}
2.8.1 keySet()遍历
for (String key : map.keySet()) {
Integer value = map.get(key);
System.out.println("Key: " + key + ", Value: " + value);
}
2.8.3 通过values遍历所有值
for (Integer value : map.values()) {
System.out.println("Value: " + value);
}
2.8.4 通过迭代器（Iterator）遍历
Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<String, Integer> entry = iterator.next();
System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}
3.红黑树
HashMap主要使用桶数组+链表+红黑树实现，为什么使用红黑树，是一个比较重要的问题。HashMap中使用红黑树、从数据库索引为B+Tree。
3.1 二叉搜索树
二叉搜索树（Binary Search Tree，简称 BST）是一种特殊的二叉树数据结构，具有以下性质：
- 每个节点的值都大于其左子树中所有节点的值。
- 每个节点的值都小于其右子树中所有节点的值。
- 左子树和右子树本身也是二叉搜索树（递归定义）。
这使得二叉搜索树的每次搜索操作都可以基于节点值进行比较，类似于二分查找，从而提供了高效的查找、插入和删除操作。二叉搜索树的数据插入过程是，插入节点与当前树节点做比对，小于在左，大于在右。
平均情况（普通二叉搜索树）：( O(log n) )
最坏情况（退化为链表时）：( O(n) )。
3.2 2-3树
2-3 树是一种自平衡的搜索树（Balanced Search Tree），它是一种特殊的 B 树（B-Tree）的简化版本。2-3 树能够保持树的平衡，从而保证查找、插入和删除操作在最坏情况下的时间复杂度都是 (O(log n))。
2-节点：包含一个数据元素和两个子节点。
3-节点：包含两个数据元素和三个子节点。
三叉与两叉的不同点在于，除了两边的节点，中间件还有一个节点。这个节点是介于两个数据元素之间的值。
特点：
- 所有叶子节点在同一深度：树是平衡的
- 动态调整：插入和删除操作可能会导致节点的分裂和合并，但树始终保持平衡。
索引查找的思路
- 小于当前节点值，左侧寻找
- 大于当前节点值，右侧寻找
- 大于左侧，小于右侧，中间寻找
- 一直到找到索引值，停止。
3.3 红黑树
红黑树具有良好的效率，它可在近似O(logN) 时间复杂度下完成插入、删除、查找等操作，因此红黑树在业界也被广泛应用，比如 Java 中的 TreeMap，JDK 1.8 中的 HashMap、C++ STL 中的 map 均是基于红黑树结构实现的。
- 根节点是黑色
- 节点是红黑或者黑色
- 所有子叶节点都是黑色（叶子是NIL节点）
- 每个红色节点必须有两个黑色子节点
- 从任一节点到每个叶子节点，经过的路径的包括相同数目的黑色节点
3.3.1 插入 （左右旋+染色）
左旋定义： 把一个向右倾斜的红节点连接(2-3树，3-叉双元素节点)，转化为左连接。是以当前某一节点为支点，让其右子节点上升替代原节点的位置，原节点成为其右子节点的左孩子。目的是让树的右子树高度降低，调整树的平衡性。
右旋定义： 把一个向左倾斜的红节点连接(2-3树，3-叉双元素节点)，转换为右连接。右旋是以某一节点为支点，将其左子节点上升替代原节点的位置，原节点变为其左子节点的右孩子。目的是让树的左子树高度降低，调整树的平衡性。
染色：是指在调整红黑树时，根据红黑树的特性，将树中的某些节点重新分配颜色，以满足红黑树的性质。
3.3.2 删除
- 红色子叶节点的删除并不会破坏树平衡，也不影响树高，所以直接删除即可
- 左右删除都需要进行旋转和染色
4 ConcurrentHashMap
4.1 ConcurrentHashMap和HashTable的区别
数据结构的不同
- ConcurrentHashMap在jdk1.7之前采用分段的数组+链表实现， JDK1.8之后采用数组+链表/红黑二叉树。
- HashTable采用数组+链表
实现线程安全的方式不一样
- 在jdk1.7中ConcurrentHashMap对整个桶数组进行分割分段使用分段锁，每一把锁只锁其中一部分。多线程访问容器里不同数据段的数据，就不会存在锁竞争。
- 在jdk1.8之后并发控制使用
synchronized和 CAS 来操作, 对桶进行加锁。 - HashTable使用
synchronized来保证线程安全，效率非常低下.
4.2 线程安全的具体实现
jdk1.7的ConcurrentHashMap的线程安全具体实现
ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。
static class Segment<K,V> extends ReentrantLock implements Serializable {
}
有一个需要注意的地方，就是Hash Map是对数组的映射，那么怎么确定一个数组是在哪个Segment的HashEntry呢。这里实际上Segment就是可以看作一个桶固定为16的hashMap。整体可以看作两层hash。
而在jdk1.8中，使用更加细粒度的锁，采用synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，就不会影响其他 Node 的读写，效率大幅提升。
源代码如下
public V put(K key, V value) {
return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh; K fk; V fv;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// 如果桶为空，通过 CAS 操作直接插入，无需加锁
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
// // 桶正在扩容，帮助扩容代码
tab = helpTransfer(tab, f);
//检查是否需要覆盖已有值
else if (onlyIfAbsent // check first node without acquiring lock
&& fh == hash
&& ((fk = f.key) == key || (fk != null && key.equals(fk)))
&& (fv = f.val) != null)
return fv;
else {
V oldVal = null;
// 对当前节点进行加锁
synchronized (f) {
// 再次确认桶未被其他线程修改
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key, value);
break;
}
}
}
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
//再次检查是否需要覆盖已有值
if (!onlyIfAbsent)
p.val = value;
}
}
else if (f instanceof ReservationNode)
throw new IllegalStateException("Recursive update");
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
// CAS判断函数
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
return U.compareAndSetObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
return (Node<K,V>)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE);
}
整体逻辑和HashMap的插入差不多， 就是在找到当前发生Hash冲突索引的首部节点的时候，对其进行加锁。
4.3 能否存NULL
- key和value都不能为null， 因为无法判断是
- key存在，value为null
- key不存在
- 避免在并发更新时产生错误行为
map.putIfAbsent(key, value) // 如果 key 尚未存在，则插入 (key, value)
那为什么HashMap能够允许null？因为开发者可以明确控制 put() 和 get() 操作，因为没有并发访问问题。并且二义性问题可以调用 containsKey(key) 方法可以进一步确认是哪一种情况。
如果在ConcurrentHashMap中使用null，则
public static final Object NULL = new Object();
4.4 复合操作原子性
虽然ConcurrentHashMap存在put等的安全操作，但是如果使用复合操作任存在问题，要么加锁要么，使用自带的复合操作。
以putIfAbsent举例， 是直接调用另一个函数putVal
public V putIfAbsent(K key, V value) {
return putVal(key, value, true);
}
参考
chatgpt
jdk1.8源码