并发环境下HashMap是不安全的,容易造成并发修改异常或者死锁现象 而Collections下提供的synchionizedMap虽然因为加了synchionized而变得安全,却也因此极大的降低了性能 由于以上情况,就使得ConcurrentHashMap应运而生
如何优化Hashtable？
- 通过锁细粒度化，将整锁拆解成多个锁进行优化
将整锁拆为十六个子锁,一个线程每次只操作一个锁并不干扰其他线程操作其他锁,理论上性能提高了16倍
ConcurrentHashMap的扩容因子SizeCtl是用volatile修饰的对其他线程可见 ConcurrentHashMap可以通过computreIfAbsent()和computre()构建java本地缓存,降低程序计算量
ConcurrentHashMap:put方法的源码逻辑
1.判断Node[]数组是否初始化，没有则进行初始化操作 2.通过hash定位数组的索引坐标，是否有Node节点，如果没有则使用CAS进行添加（链表的头节点），添加失败则进入下次循环。 3.检查到内部正在扩容，就帮助它一块扩容。(主要做数据标记,辅助迁移等) 4.如果f=null(头节点不为空)，则使用synchronized锁住元素（链表/红黑二叉树的头元素） 4.1如果是Node（链表结构）则执行链表的添加操作。 4.2如果是TreeNode（树型结构）则执行树添加操作。 5.判断链表长度已经达到临界值8，当然这个8是默认值，大家也可以去做调整，当节点数超过这个值就需要把链表转换为树结构。
ConcurrentHashMap总结：比起分段锁Segment，锁拆得更细
- 首先使用无锁操作CAS插入头节点，失败则循环重试
- 若头节点已存在，则通过synronchized尝试获取头节点的同步锁，再进行操作
public V put(K key, V value) {
return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
//onlyIfAbsent的意思是在put一个KV时，如果K已经存在什么也不做则返回null
//如果不存在则put操作后返回V值
final V putVal(K key, V value, boolean onlyIfAbsent) {
//ConcurrentHashMap中是不能有空K或空V的
if (key == null || value == null) throw new NullPointerException();
//hash算法得到hash值
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
//如果table是空的，就去初始化，下一个循环就不是空的了
if (tab == null || (n = tab.length) == 0)
tab = initTable();
//如果没有取到值，即取i位的元素是空的，为什么i取值是(n-1)&hash??
//这是hash的精华所在，在这里可以先思考一下
//此时直接到KV包装成Node节点放在i位置即可
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
//MOVED，定义为-1。标记原table正在执行扩容任务，可以去帮忙(支持多线程扩容)
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
//这种情况是，在i的位置找到了一个元素，说明此元素的K与之间的某个K的hash结果是一样的
//
V oldVal = null;
synchronized (f) {//同步锁住第一个元素
if (tabAt(tab, i) == f) {//为了安全起见，再一次判断
if (fh >= 0) {//节点的hash值大于0，说明是一个链表结构
binCount = 1;//记录链表的元素个数
for (Node<K,V> e = f;; binCount) {
K ek;
//判断给定的key是否与取出的key相同，如果是则替换元素
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;//直接跳出，这是一种思想。在编程时可以减少一些if else判断
}
//否则就是不相等，那就把此元素放在链表的最后一个元素
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
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;
}
}
}
}
if (binCount != 0) {
//链表的元素大于等于8时，就把链表转换为红黑树
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
//新添加一个元素，size加1，可能会触发扩容
addCount(1L, binCount);
return null;
}CAS性能很高，但是我知道synchronized性能可不咋地，为啥jdk1.8升级之后反而多了synchronized？
synchronized之前一直都是重量级的锁，但是后来java官方是对他进行过升级的，他现在采用的是锁升级的方式去做的。 针对 synchronized 获取锁的方式，JVM 使用了锁升级的优化方式，就是先使用偏向锁优先同一线程使用,然后再次获取锁，如果失败，就升级为 CAS 轻量级锁，如果失败就会短暂自旋，防止线程被系统挂起。最后如果一直都失败就升级为重量级锁。 所以是一步步升级上去的，最初也是通过很多轻量级的方式锁定的。
ConcurrentHashMap的get操作又是怎么样子的呢？
- 根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值。
- 如果是红黑树那就按照树的方式获取值。
- 就不满足那就按照链表的方式遍历获取值。
关于ConcurrentHashMap主要注意的地方
- 1.size（）方法和mappingCount方法的异同，两者计算是否准确？ 1.1 size最大返回 int 最大值，但是这个 Map 的长度是有可能超过 int 最大值的 mappingCount 方法的返回值是 long 类型。所以不必限制最大值必须是Integer.MAX_VALUE 1.2 public long mappingCount()返回映射的数量。应该使用此方法而不是size（），因为ConcurrentHashMap可能包含的映射数多于可以表示为int的映射。返回的值是估计值; 如果有并发插入或删除，实际计数可能会有所不同。 size()返回此映射中键 - 值映射的数量。
- 2.CouncurrentHahsMap的并发扩容问题 CouncurrentHahsMap在添加元素时候会判断是否有线程在扩容,如果有,它会调用一个helpTransfer()方法,在这个方法里会重新确认一下,如果确实扩容,会添加一个sizeCtl开启一个辅助线程帮助扩容.
- 3我们这里保证了并发的写put操作是安全的,那么get操作没有加锁,他是怎么保证并发读写线程安全的呢??? 答案: get操作可以无锁是由于Node的元素val和指针next都是用volatile修饰的，在多线程环境下线程A修改结点的val或者新增节点的时候是对线程B可见的。
HashMap、Hashtable、ConccurentHashMap三者区别
参考 https://blog.csdn.net/xpsallwell/article/details/88071038 https://blog.csdn.net/qq_27037443/article/details/94441885
