【Java并发】聊聊不安全的HashMap以及ConcurrentHashMap

在实际的开发中，hashmap是比较常用的数据结构，如果所开发的系统并发量不高，那么没有问题，但是一旦系统的并发量增加一倍，那么就可能出现不可控的系统问题，所以在平时的开发中，我们除了需要考虑正常的情况，还需要考虑异常情况，高并发的场景，这样写的代码才具备稳定性。否则就是随时就是定时炸弹。只是目前没有触发而已。

hashmap为什么不安全

造成线程不安全的原因在于竞态读写共享资源，对于hashmap来说其实就是table数组以及数组中链表。
get：读操作 put：写操作，以及扩容和树化等。

1.读操作与读操作、写操作、扩容、树化之间是否线程安全
读和读之间显然不会有线程安全问题，读是从table中获取对应下标遍历链表，而写直接写在最后，也不存在。

读和扩容之间存在线程安全问题，扩容的基本流程是会创建一个新的table数组，然后将当前table引用指向新的数组，然后在将旧的table数组遍历迁移到新的数组中。所以在这个过程中，可能导致读操作获取不到原来旧数组中的某些值，从而导致出现数据丢失。

读操作与树化不存在线程安全问题，原因在于 链表的节点和树化的节点是不同的，需要创建新的树节点，而之前是不需要修改链表节点。在树化完全执行完毕之后，才会更新对应的引用。是一个写时复制操作。

2.写操作与写操作，扩容、树化之间是否线程安全
写与写操作是存在线程安全的，因为同时对链表进行尾部插入，如果同时有两个线程操作，那么就会出现丢失数据的情况。
同样写与扩容来说，一边写和扩容，并行操作。写与树化操作，因为是对链表操作，而在树化结束之后，没来得记更新，所以就会出现写操作无效。
3.扩容与扩容、树化操作之间是否安全
扩容与扩容 在同时操作不同的数据肯定会丢失数据。
4.树化与树化之间是否线程安全

ConcurrentHashMap

如上所示，hashmap是线程不安全的，所以在实际的开发中，我们会更多的使用concurrentHashMap。hashtable和Synchroinzed的原理其实是通过对全局的操作进行加一把锁，整体的并发粒度比较粗。

    public synchronized int size() {return count;}

而ConcurrentHashMap采用了分段锁的思想，按照table的粒度进行划分，如果是8个那么默认就是8个锁，这样对于数据的操作可以提升并发性能。

get实现原理

public V get(Object key) {Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;// key 所在的 hash 位置int h = spread(key.hashCode());if ((tab = table) != null && (n = tab.length) > 0 &&(e = tabAt(tab, (n - 1) & h)) != null) {// 如果指定位置元素存在，头结点hash值相同if ((eh = e.hash) == h) {if ((ek = e.key) == key || (ek != null && key.equals(ek)))// key hash 值相等，key值相同，直接返回元素 valuereturn e.val;}else if (eh < 0)// 头结点hash值小于0，说明正在扩容或者是红黑树，find查找return (p = e.find(h, key)) != null ? p.val : null;while ((e = e.next) != null) {// 是链表，遍历查找if (e.hash == h &&((ek = e.key) == key || (ek != null && key.equals(ek))))return e.val;}}return null;
}

总结下其实就是如下几种步骤，
1.根据hash值计算位置，
2.找到指定位置，如果是头节点直接返回。
3.如果头节点hash值小于0，说明正在扩容或者是红黑树，查找
4.如果是链表，直接遍历链表。

put实现原理

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) {// key 和 value 不能为空if (key == null || value == null) throw new NullPointerException();int hash = spread(key.hashCode());int binCount = 0;for (Node<K,V>[] tab = table;;) {// f = 目标位置元素Node<K,V> f; int n, i, fh;// fh 后面存放目标位置的元素 hash 值if (tab == null || (n = tab.length) == 0)// 数组桶为空，初始化数组桶（自旋+CAS)tab = initTable();else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {// 桶内为空，CAS 放入，不加锁，成功了就直接 break 跳出if (casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null)))break;  // no lock when adding to empty bin}else if ((fh = f.hash) == MOVED)tab = helpTransfer(tab, f);else {V oldVal = null;// 使用 synchronized 加锁加入节点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, 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) {if (binCount >= TREEIFY_THRESHOLD)treeifyBin(tab, i);if (oldVal != null)return oldVal;break;}}}addCount(1L, binCount);return null;
}

写操作的过程 其实是分两种情况，如果table[i] 为空，则使用cas方式将数据写入对应的节点，如果table[i]不为空 ，通过syn的方式枷锁实现。

树化操作，写入和扩容的同时会丢失数据，所以需要使用syn枷锁

扩容
ConcurrentHashMap使用的是分段锁，也就是一个table[i] 一个锁，那么在实际扩容的时候是怎么样的。
实际上也是通过扩容操作也是分段加锁执行的。整体就是写时复制、复制替代搬移

1.操作的时候，会对每个数组进行枷锁处理，复制、然后解锁，并且是多个线程同时处理。比如A线程复制1-3，B线程复制4-6。所以整体的流程就是已经完成复制的（已复制未加锁）、在复制中加锁、未复制未加锁。
2.因此在复制的过程中，对于已经复制的链表应该使用新的table数组，而在复制和没有复制的应该使用旧的table数组。
ForwardingNode 节点就是标记是否已复制未加锁，所以在已经复制的节点，会使用 ForwardingNode的nextTable指向新的数组。

static final class ForwardingNode<K, V> extends Node<K, V> {final Node<K, V>[] nextTable;ForwardingNode(Node<K, V>[] tab) {super(MOVED, null, null, null);this.nextTable = tab;}}

3.在实际的扩容中，多个线程可以同时进行对数组进行扩容，通过tranferIndex，初始值为tab.length，通过CAS进行竞争获取。

4.最终谁来执行将table引用指向新数组，通过sizeCtl来判断，谁执行到最后 等于0 的时候，就负责处理。

小结

本篇主要介绍了 hashmap不安全的原因，在扩容、树化、put操作之间。以及介绍了ConcurrentHashMap 在8中的版本get、put的核心流程。主要介绍了扩容的机制/