盐城网站优化,企业高端wordpress主题,包头网络,用国外服务器做网站在实际的开发中#xff0c;hashmap是比较常用的数据结构#xff0c;如果所开发的系统并发量不高#xff0c;那么没有问题#xff0c;但是一旦系统的并发量增加一倍#xff0c;那么就可能出现不可控的系统问题#xff0c;所以在平时的开发中#xff0c;我们除了需要考虑正…在实际的开发中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) {NodeK,V[] tab; NodeK,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 (NodeK,V[] tab table;;) {// f 目标位置元素NodeK,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 NodeK,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 (NodeK,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;}NodeK,V pred e;if ((e e.next) null) {pred.next new NodeK,V(hash, key,value, null);break;}}}else if (f instanceof TreeBin) {// 红黑树NodeK,V p;binCount 2;if ((p ((TreeBinK,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-3B线程复制4-6。所以整体的流程就是已经完成复制的已复制未加锁、在复制中加锁、未复制未加锁。 2.因此在复制的过程中对于已经复制的链表应该使用新的table数组而在复制和没有复制的应该使用旧的table数组。 ForwardingNode 节点就是标记是否已复制未加锁所以在已经复制的节点会使用 ForwardingNode的nextTable指向新的数组。
static final class ForwardingNodeK, V extends NodeK, V {final NodeK, V[] nextTable;ForwardingNode(NodeK, 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的核心流程。主要介绍了扩容的机制/
