三灶网站建设,做原油看哪个网站,辽阳做网站,内容营销包括ConcurrentHashMap
引入 HashMap 的弊端 多线程下是不安全的#xff0c;是有死循环的
JDK1.7 的时候会使用头插法将新的节点增加到头部#xff0c;那么就会造成链表翻转成为了闭环#xff0c;就是所谓的死循环。
JDK1.8之后使用的是尾插法#xff0c;因此不会造成环形链…ConcurrentHashMap
引入 HashMap 的弊端 多线程下是不安全的是有死循环的
JDK1.7 的时候会使用头插法将新的节点增加到头部那么就会造成链表翻转成为了闭环就是所谓的死循环。
JDK1.8之后使用的是尾插法因此不会造成环形链表从而不会形成死循环但是多线程情况下仍然会造成数据的覆盖导致线程不安全。 使用hashtable 为什么效率不行 hashtable 使用的是 synchronized 来保证线程安全每次只能有一个线程访问 hashtable 的同步方法其他线程访问的时候就会进入阻塞或者轮询的状态。这里的synchronized 锁的是一个大的数组就是说锁的是一个对象整体所以性能比较差。 这个 类的很多方法和代码都是和HashMap 类似的但是 为什么不直接继承HashMap ? 原因是ConcurrentHashMap的内部源码中锁都是在方法内部加的而非是方法上加的如果用继承实现一般只能在方法声明上加锁而无法在方法内部中加锁 ConcurrentHashMap 使用的是分段式锁把一个大的数组分为多个小的数组每个数组都用于一把锁允许多个修改操作的并发执行。put 数据的时候会根据 hash 来确定具体存放在哪个 segment 中segment 内部同步的机制是基于Lock 操作的每个 segment 都会分配一把锁当线程占用锁访问其中一段数据的时候其他段的数据也能被其他线程访问。
然而分段锁在不同版本也是有具体实现的区别的
版本对比
1.7中
HashEntry数组 Segment数组 Unsafe 「大量方法运用」 ReentrantLock
每个segment 数组中存放的元素是HashEntry数组 链表的结果
每个segment 数组都是继承于可重入锁ReentrantLock所以就会带有锁的功能当线程执行put的时候只锁住对应的那个 segment 对象对其他的 Segment 的 get 、put 互不干扰这样子就提升了效率做到了线程安全。
ConcurrentHashMap 是如何解决hashmap在put 的时候扩容引起的安全问题
ConcurrentHashMap 在put的时候进行了两次hash 计算定位数据的存储位置尽可能的减少hash冲突的可能性根据计算出来的hash 值会以 Unsafe 调用的方式直接获取对应的 Segment最后将数据添加到容器中是由segment 对象的put 方法完成由于segment 对象本身就是一把锁新增数据的时候相应的segment 对象是被锁住的其他线程并不能操作这个segment对象扩容只是针对 segment 对象中的 HashEntry 数组进行扩容扩容的时候也是因为segment 对象是一把锁所以在 rehash 的时候其他线程无法对 segment 的hash 表进行操作从而解决了hashmap 在put 操作引起的闭环问题
从而保证了数据的安全性
1.8中
synchronizedCASNode红黑树synchronizedCAS保证安全性
放弃了HashEntry 的结构采用了和 HashMap结构相似的Node数组 链表的结构使用synchronized替代了ReentrantLock synchronized替代了ReentrantLock synchronized 是在 Java 语法层面的同步足够清晰也足够简单,并且锁的释放不需要程序员手动操作就可触发执行。在粗粒度加锁中 ReentrantLock 可能通过 Condition 来控制各个低粒度的边界更加的灵活而在低粒度中Condition的优势就没有了所以使用内置的 synchronized 其效果并不比ReentrantLock差。
成员变量 最大的 table 容量private static final int MAXIMUM_CAPACITY 1 30;默认的 table 容量private static final int DEFAULT_CAPACITY 16;支持的最大的map 的大小 static final int MAX_ARRAY_SIZE Integer.MAX_VALUE - 8;并发更新的线程数量private static final int DEFAULT_CONCURRENCY_LEVEL 16;负载因子private static final float LOAD_FACTOR 0.75f;树化的链表长度的阈值static final int TREEIFY_THRESHOLD 8;取消树化的链表长度的阈值static final int UNTREEIFY_THRESHOLD 6;树化的数组长度临界值static final int MIN_TREEIFY_CAPACITY 64;扩容期间 并发转移节点 (transfer()方法执行的) 的最小节点数默认的线程迁移数据范围private static final int MIN_TRANSFER_STRIDE 16;生成标记的位数。对于 32 位数组必须至少为 6private static int RESIZE_STAMP_BITS 16;可以帮助调整大小的最大线程数。必须适合 32 - RESIZE_STAMP_BITS 位。private static final int MAX_RESIZERS (1 (32 - RESIZE_STAMP_BITS)) - 1;sizeCtl 中记录大小标记的位移位private static final int RESIZE_STAMP_SHIFT 32 - RESIZE_STAMP_BITS;记录节点的状态static final int MOVED -1; // hash for forwarding nodes 移动static final int TREEBIN -2; // hash for roots of trees 树static final int RESERVED -3; // hash for transient reservations 转化状态static final int HASH_BITS 0x7fffffff; // usable bits of normal node hash CPU核心数static final int NCPU Runtime.getRuntime().availableProcessors();/** For serialization compatibility. */private static final ObjectStreamField[] serialPersistentFields {new ObjectStreamField(segments, Segment[].class),new ObjectStreamField(segmentMask, Integer.TYPE),new ObjectStreamField(segmentShift, Integer.TYPE)};存储数据的 table 数组transient volatile NodeK,V[] table;扩容之后的 新的table 数组private transient volatile NodeK,V[] nextTable;统计节点的个数和 CounterCell[] counterCells 结合用于计算concurrentHashMap的sizeprivate transient volatile long baseCount;可以进行控制数组 初始化和扩容初始化之后赋值为扩容的阈值当初始化大小被指定了的时候这会将这个大小保存在sizeCt1中大小为数组的0.75当为负值时表正在被初始化或调整大小 初始化数组的时候为 -1 活动的扩容的线程数为-(1n) n:表示活动的扩容线程当table为null时保留创建时使用的初始表大小默认为0。当为正值时:记录下一次需要扩容的大小。为3/4数组最大长度扩容的阈值 private transient volatile int sizeCtl;/***transient 关键字表示该字段不会被序列化即在对象被序列化为字节流时该字段的值不会被包含在字节流中。volatile 关键字表示该字段是可见的即对该字段的读取和写入操作都是原子的并且对该字段的写入操作会立即刷新到主内存中而不会被缓存。这样可以确保多个线程之间对 transferIndex 的操作是同步的避免了数据不一致性和竞态条件的问题。*/调整大小resizing过程中确定下一个要拆分的表索引加一的字段。private transient volatile int transferIndex;用于计算concurrentHashMap的size时需要加cas锁的标记private transient volatile int cellsBusy;用于计算concurrentHashMap的size 默认长度是2private transient volatile CounterCell[] counterCells;
构造器
构造器public ConcurrentHashMap() {}// 有参构造器最后的长度为 传入长度 *3/2 1 的最接近的 2 的幂次方含参构造器public ConcurrentHashMap(int initialCapacity) {if (initialCapacity 0)throw new IllegalArgumentException();int cap ((initialCapacity (MAXIMUM_CAPACITY 1)) ?MAXIMUM_CAPACITY :tableSizeFor(initialCapacity (initialCapacity 1) 1)); this.sizeCtl cap;}/*** 置为 c 的最小 2 次幂*/private static final int tableSizeFor(int c) {int n c - 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;}public ConcurrentHashMap(Map? extends K, ? extends V m) {this.sizeCtl DEFAULT_CAPACITY;putAll(m);}public ConcurrentHashMap(int initialCapacity, float loadFactor) {this(initialCapacity, loadFactor, 1);}public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {if (!(loadFactor 0.0f) || initialCapacity 0 || concurrencyLevel 0)throw new IllegalArgumentException();if (initialCapacity concurrencyLevel) // Use at least as many binsinitialCapacity concurrencyLevel; // as estimated threadslong size (long)(1.0 (long)initialCapacity / loadFactor);int cap (size (long)MAXIMUM_CAPACITY) ?MAXIMUM_CAPACITY : tableSizeFor((int)size);this.sizeCtl cap;}HashMap 只能使用在单线程下所以不会有二义性的问题并且会有 containsKey()判断元素是不是存在的所以key可以是null 但是 ConcurrentHashMap 会有二义性的问题所以value不可以是null但是源码中将 key null 也进行了判断所以key也不可以是null if (key null || value null) throw new NullPointerException(); put public V put(K key, V value) {return putVal(key, value, false);
}putVal hash值: 1、大于等于0 表示节点下面是一个链表 2、如果是-1表明节点正在迁移 3、都不是那么节点后面是一个红黑树 sizeCtl的值 1、sizeCtl 0 表正在被初始化或调整大小 1.1、 -1表示数组正在 初始化数组 1.2、-(1n)表示扩容的线程数量 n:表示活动的扩容线程 2、默认值是 0 当tablenull时保留创建时使用的初始表大小。 3、sizeCtl 0 时: 表示记录下一次需要扩容的阈值 3/4*n(n:数组长度) /** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {键和值都不能为空 否则抛出空指针异常if (key null || value null) throw new NullPointerException();计算key的hash值两次 hash 计算int hash spread(key.hashCode());/*第一次 hashCode key为Object 重写的hashcode方法第二次 static final int spread(int h) {return (h ^ (h 16)) HASH_BITS); // static final int HASH_BITS 0x7fffffff; }*/int binCount 0;for (NodeK,V[] tab table;;) {NodeK,V f; int n, i, fh;初始化数组if (tab null || (n tab.length) 0)tab initTable();找到当前值应该存放的位置的值是不是 null else if ((f tabAt(tab, i (n - 1) hash)) null) {/*获取给定索引位置上的数组元素static final K,V NodeK,V tabAt(NodeK,V[] tab, int i) {((long)i ASHIFT) ABASE是用于计算给定索引位置上的元素在数组中的偏移量。ASHIFT和ABASE是常量用于优化计算偏移量的操作。return (NodeK,V)U.getObjectVolatile(tab, ((long)i ASHIFT) ABASE);}*/如果计算出的数组位置的node为null 直接用cas进行替换即可// 在指定位置的节点数组中执行 CAS 操作将期望值替换为新值。if (casTabAt(tab, i, null, new NodeK,V(hash, key, value, null)))/*tab 是一个节点数组i 是数组中的索引位置c 是期望的节点值v 是新的节点值static final K,V boolean casTabAt(NodeK,V[] tab, int i, NodeK,V c, NodeK,V v) {// compareAndSwapObject 比较指定内存位置的值是否等于期望值 c如果相等则将该位置的值替换为新值 v并返回操作结果。将索引 i 左移 ASHIFT 位并加上 ABASE计算出需要进行 CAS 操作的内存位置return U.compareAndSwapObject(tab, ((long)i ASHIFT) ABASE, c, v);}*/break; // no lock when adding to empty bin}判断当前节点是不是正在迁移else if ((fh f.hash) MOVED) 是就 进行协助 迁移tab helpTransfer(tab, f);不在迁移状态else {V oldVal null;// 对当前节点进行加锁synchronized (f) {// 进行一次验证防止当前值被其他线程进行变动值发生了变化if (tabAt(tab, i) f) {//未发生变动fh f的hash 值 0 此时表示为链表状态if (fh 0) {
链表 // 设置bitCount 为 1binCount 1; // 遍历链表for (NodeK,V e f;; binCount) {K ek;// 判断 key 是不是一样的if (e.hash hash ((ek e.key) key || (ek ! null key.equals(ek)))) {oldVal e.val;if (!onlyIfAbsent) // onlyIfAbsent 表示是不是要进行覆盖要是fasle 进行覆盖e.val value;break; // 否则退出循环}NodeK,V pred e;
// 要是e 的 下一个是 null表示遍历到链表尾部 就创建新的节点并插入随后退出循环 e e.next 并将 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;
树 // 设置bitCount 为 2 // 也就是存在key相同的并且然后根据红黑树的规则添加到树中if ((p ((TreeBinK,V)f).putTreeVal(hash, key,value)) ! null) {oldVal p.val;if (!onlyIfAbsent) // 允许被覆盖就覆盖旧的值 onlyIfAbsent false 就 更新此节点的值p.val value; }}}}
是树或者是链表if (binCount ! 0) { 要是超过 树化阈值8 就进行树化并返回旧值if (binCount TREEIFY_THRESHOLD)treeifyBin(tab, i);if (oldVal ! null)return oldVal;break;}}}addCount(1L, binCount); //进行增加元素个数并判断要不要扩容 return null;
}initTable 作用是在初始化哈希表时确保只有一个线程进行初始化操作并创建一个初始的节点数组。 private final NodeK,V[] initTable() {NodeK,V[] tab; int sc;while ((tab table) null || tab.length 0) {0 表示有其他线程正在进行初始化 此时当前线程 礼让等待if ((sc sizeCtl) 0)Thread.yield(); 0 把么就 cas 的方式 将 sc置为 -1else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { cas 成功的话表示当前线程拥有hash表的操作权限try {判空进行初始化if ((tab table) null || tab.length 0) { 确定新的数组长度n如果sc sizeCtl大于0则为sizeCtl否则为默认容量DEFAULT_CAPACITYint n (sc 0) ? sc : DEFAULT_CAPACITY; // 16SuppressWarnings(unchecked)初始化 Node 数组NodeK,V[] nt (NodeK,V[])new Node?,?[n]; table tab nt;计算新的sizeCtl值 sc n * 3/4 sc n - (n 2); // 设置 sc n * 3/4 }} finally {赋值 扩容的阈值sizeCtl sc; }break;}}返回tab数组return tab;}helpTransfer 帮助进行数组转移通过判断条件和执行相应的操作来实现数组的扩容和数据的迁移。 final NodeK,V[] helpTransfer(NodeK,V[] tab, NodeK,V f) {NodeK,V[] nextTab; int sc;//传入的表格数组tab不为空 传入的节点f是一个转发节点ForwardingNode 转发节点的下一个数组nextTab也不为空// 判断是否需要进行扩容和数据迁移。if (tab ! null (f instanceof ForwardingNode) (nextTab ((ForwardingNodeK,V)f).nextTable) ! null) {// 根据当前哈希表的长度计算出一个扩容标记rsint rs resizeStamp(tab.length) RESIZE_STAMP_SHIFT;//nextTab等于nextTable table等于tab sizeCtl 0。tab ! null判断变量 tab 是否不为 null即检查当前的哈希表是否已经存在。(f instanceof ForwardingNode)判断变量 f 是否是 ForwardingNode 类型的实例。ForwardingNode 是用于表示正在进行扩容操作的特殊节点。强制将 f 转换为 ForwardingNode 类型并判断其 nextTable 是否不为 null。nextTable 表示扩容后的新哈希表 while (nextTab nextTable table tab (sc sizeCtl) 0) {// 中断循环。 sc等于rs MAX_RESIZERS、sc等于rs 1、transferIndex小于等于0。// 进行数据迁移的准备工作并执行数据迁移操作sc rs 1 表示当前线程是扩容操作的发起者。sc rs MAX_RESIZERS 已经达到了最大的扩容线程数当前线程不能参与扩容操作。transferIndex 0 表示当前扩容操作已经迁移完成或者还未开始迁移当前线程应该退出循环。if (sc rs MAX_RESIZERS || sc rs 1 || transferIndex 0)break;// cas 增加sizeCtl的值 成功 且 不满足上述的条件 进行转移 并 中断循环 if (U.compareAndSwapInt(this, SIZECTL, sc, sc 1)) {transfer(tab, nextTab);break;}}return nextTab;}//如果不需要进行扩容和数据迁移则返回原始的哈希表table。return table;
}transfer 用于并发扩容哈希表的迁移操作确保在多线程环境下能够正确地将旧的哈希表中的元素迁移到新的扩容后的哈希表中。 // 在扩容时将元素从旧的数组转移到新的数组中。
private final void transfer(NodeK,V[] tab, NodeK,V[] nextTab) {int n tab.length, stride;// 根据当前数组的长度和处理器核心数计算出每个线程需要处理的元素数量。 //根据cpu数量计算一个线程迁移的范围 默认是16;也就是说一个容量为32的旧数组 第一个线程第一次迁移的范围应该是16-31// stride表示每个线程处理的元素数量。如果线程数大于1则将哈希表长度的1/8除以线程数否则设为哈希表长度。if ((stride (NCPU 1) ? (n 3) / NCPU : n) MIN_TRANSFER_STRIDE)stride MIN_TRANSFER_STRIDE; // subdivide range//如果nextTab为空表示扩容刚开始。需要初始化一个新的哈希表。if (nextTab null) { // initiatingtry {SuppressWarnings(unchecked)//创建一个新的数组并将其赋值给nextTab。 容量是原来的两倍NodeK,V[] nt (NodeK,V[])new Node?,?[n 1];nextTab nt;} catch (Throwable ex) { // try to cope with OOMEsizeCtl Integer.MAX_VALUE;return;}nextTable nextTab;//transferIndex表示数据迁移的开始索引 默认是从原数组的末尾开始迁移transferIndex n;}//获取新哈希表的长度并创建一个ForwardingNode节点表示已迁移的节点。advance和finishing用于控制迁移的进程。int nextn nextTab.length;ForwardingNodeK,V fwd new ForwardingNodeK,V(nextTab);//当 advance 为 true 时表示继续进行数据迁移。当 advance 为 false 时表示停止数据迁移。boolean advance true; boolean finishing false; // to ensure sweep before committing nextTab//循环遍历旧哈希表的每个元素。i表示当前元素的索引bound表示当前线程需要处理的元素的上限。advance控制是否继续迁移。for (int i 0, bound 0;;) {NodeK,V f; int fh;//下面 这三个判断都是判断当前线程是否完成自己范围内要迁移的数据 如果完成了直接设置 advance false 跳出while循环while (advance) {int nextIndex, nextBound;// 这表示要么已经迭代到了边界之外要么已经完成了迭代。if (--i bound || finishing)advance false;//没有需要迁移的节点即没有进行数据迁移的工作。else if ((nextIndex transferIndex) 0) {i -1;advance false;}// 成功更新了迁移索引并更新了边界和迭代变量。else if (U.compareAndSwapInt(this, TRANSFERINDEX, nextIndex,nextBound (nextIndex stride ?nextIndex - stride : 0))) {bound nextBound;i nextIndex - 1;advance false;}}//如果i超出了索引范围表示迁移完成。if (i 0 || i n || i n nextn) {int sc;//如果finishing为true表示迁移已经完成更新哈希表的相关变量并返回。如果已经扩容完成 将新数组赋值给table if (finishing) {nextTable null;table nextTab;sizeCtl (n 1) - (n 1);return;}//否则cas 的 将sizeCtl减1表示迁移进入完成阶段。if (U.compareAndSwapInt(this, SIZECTL, sc sizeCtl, sc - 1)) {// 表示已经迁移完成if ((sc - 2) ! resizeStamp(n) RESIZE_STAMP_SHIFT)return;finishing advance true;i n; // recheck before commit}}//如果是空的节点 直接cas替换为fwd节点 如果节点是fwd 也就是MOVE类型的节点 证明节点上有线程正在迁移else if ((f tabAt(tab, i)) null)advance casTabAt(tab, i, null, fwd);//表示该位置已经处理过直接继续遍历下一个位置。else if ((fh f.hash) MOVED)advance true; // already processed//如果元素的哈希值大于等于0表示是普通节点需要进行处理else {synchronized (f) { // 同步锁保证只有一个线程可以处理该节点// 根据节点的哈希值和新数组的长度确定该节点在新数组中的位置。if (tabAt(tab, i) f) {NodeK,V ln, hn;if (fh 0) {int runBit fh n;NodeK,V lastRun f;// 将该节点拆分为两个链表低位链表和高位链表并将它们放入新数组的对应位置。for (NodeK,V p f.next; p ! null; p p.next) {int b p.hash n;if (b ! runBit) {runBit b;lastRun p;}}if (runBit 0) {ln lastRun;hn null;}else {hn lastRun;ln null;}for (NodeK,V p f; p ! lastRun; p p.next) {int ph p.hash; K pk p.key; V pv p.val;if ((ph n) 0)// 构建低位链表ln new NodeK,V(ph, pk, pv, ln);else//构建高位链表hn new NodeK,V(ph, pk, pv, hn);}//将低位链表放在新数组的原下标位置setTabAt(nextTab, i, ln);//将高位链表放在新数组下标为 原下标位置 原容量大小的位置setTabAt(nextTab, i n, hn);//将旧数组的位置设置为fwd节点 表示该节点已经迁移数据setTabAt(tab, i, fwd);advance true;}// 如果是树节点则将树节点转换为链表节点并将链表节点放入新哈希表的对应位置。else if (f instanceof TreeBin) {// 同样进行数据的高低位链表计算TreeBinK,V t (TreeBinK,V)f;TreeNodeK,V lo null, loTail null;TreeNodeK,V hi null, hiTail null;int lc 0, hc 0;// 循环遍历了原数组中的每个元素并根据其哈希值的特征将元素分别放入新数组的对应位置for (NodeK,V e t.first; e ! null; e e.next) {int h e.hash;TreeNodeK,V p new TreeNodeK,V(h, e.key, e.val, null, null);// 如果哈希值在某一位上为0则将元素放入低位链表(lo)中如果哈希值在某一位上为1则将元素放入高位链表(hi)中。if ((h n) 0) {if ((p.prev loTail) null)lo p;elseloTail.next p;loTail p;lc;}else {if ((p.prev hiTail) null)hi p;elsehiTail.next p;hiTail p;hc;}}// 如果迁移后的高低位链表长度小于6UNTREEIFY_THRESHOLD 那么会把原来的数结构变成链表结构// 根据计数的阈值条件决定是否将链表转换为树结构 或者 树结构转换为链表结构 ln (lc UNTREEIFY_THRESHOLD) ? untreeify(lo) :(hc ! 0) ? new TreeBinK,V(lo) : t;hn (hc UNTREEIFY_THRESHOLD) ? untreeify(hi) :(lc ! 0) ? new TreeBinK,V(hi) : t;// 将低位链表放在新数组的原下标位置setTabAt(nextTab, i, ln);// 将高位链表放在新数组下标为 原下标位置 原容量大小的位置setTabAt(nextTab, i n, hn);//将旧数组的位置设置为fwd节点 表示该节点已经迁移数据setTabAt(tab, i, fwd);advance true;}}}}}
}treeifyBin //用于将哈希表中的一个索引位置的链表转换为红黑树
private final void treeifyBin(NodeK,V[] tab, int index) {NodeK,V b; int n, sc;if (tab ! null) {if ((n tab.length) MIN_TREEIFY_CAPACITY) // 64tryPresize(n 1); // 尝试扩容// 如果哈希表在指定索引位置上的节点存在并且节点的哈希值大于等于0else if ((b tabAt(tab, index)) ! null b.hash 0) {synchronized (b) { // 加锁树化 使用了同步锁来保证线程安全。if (tabAt(tab, index) b) {//红黑树节点的左右子节点初始化为 null。TreeNodeK,V hd null, tl null;// 遍历原链表上的每个节点将每个节点转换为红黑树节点并构建红黑树结构。for (NodeK,V e b; e ! null; e e.next) {//对当前节点 进行 树化创建树节点// 首先创建一个新的红黑树节点 p并将链表节点的关键字和值复制到红黑树节点中。TreeNodeK,V p new TreeNodeK,V(e.hash, e.key, e.val,null, null);// 创建的树的前一个节点 null p就是头结点 //将红黑树节点的 prev 指针指向当前红黑树的最后一个节点 tl。if ((p.prev tl) null)//如果 tl 为 null说明链表为空将头节点 hd 设置为当前红黑树节点 p。hd p;else// 否则的话就加到 尾节点上// 否则将当前红黑树节点 p 设置为 tl 节点的下一个节点。tl.next p;// 为节点是 p 将当前红黑树节点 p 设置为最后一个节点 tl完成节点的串联。tl p;}//TreeBin 类中进行 左旋 右旋 等树化操作// 将转换后的红黑树替换原链表在指定索引位置上的节点// 调用setTabAt 方法将转换后的红黑树节点数组更新到指定的位置 index。setTabAt(tab, index, new TreeBinK,V(hd));}}}}}tryPresize 数组长度 64 的时候就进行扩容 // 用于动态调整哈希表的大小以适应不同的负载情况private final void tryPresize(int size) {
// 首先判断给定的大小是否超过了最大容量的一半如果是则将容量设置为最大容量否则调用tableSizeFor方法计算出新的容量大小。int c (size (MAXIMUM_CAPACITY 1)) ? MAXIMUM_CAPACITY :tableSizeFor(size (size 1) 1); //找到不小于期望大小的最小的 2 的幂次方值int sc;
// sizeCtl大于等于0while ((sc sizeCtl) 0) {NodeK,V[] tab table; int n;// 首先判断当前哈希表是否为空或者长度为0if (tab null || (n tab.length) 0) {// 如果是则将容量设置为sc和c中的较大值n (sc c) ? sc : c;// 尝试使用原子操作将sizeCtl的值从sc修改为-1。if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {try {if (table tab) {SuppressWarnings(unchecked)NodeK,V[] nt (NodeK,V[])new Node?,?[n];table nt;sc n - (n 2);}} finally {sizeCtl sc;}}}扩容的目标大小c大于sizeCtl并且当前table数组与tab相等else if (c sc || n MAXIMUM_CAPACITY)break;// 如果哈希表不为空且长度不为0并且c大于sc并且当前长度没有达到最大容量else if (tab table) {// 计算出一个调整大小的戳记rsint rs resizeStamp(n);// 如果sc小于0if (sc 0) {NodeK,V[] nt;//则进行扩容操作//首先判断sc是否与戳记rs相等以及其他一些条件是否满足如果满足则进行扩容操作。// sc RESIZE_STAMP_SHIFT) ! rs 如果不相等表示其他线程已经开始了新一轮的扩容操作// sc rs 1 表示当前线程是扩容操作的发起者。// sc rs MAX_RESIZERS 已经达到了最大的扩容线程数当前线程不能参与扩容操作。// (nt nextTable) null 扩容操作已经完成当前线程应该退出循环。// transferIndex 0 表示当前扩容操作已经迁移完成或者还未开始迁移当前线程应该退出循环。if ((sc RESIZE_STAMP_SHIFT) ! rs || sc rs 1 ||sc rs MAX_RESIZERS || (nt nextTable) null ||transferIndex 0)break;if (U.compareAndSwapInt(this, SIZECTL, sc, sc 1))transfer(tab, nt);}//否则进行缩小容量的操作。//使用原子操作将sc的值修改为(rs RESIZE_STAMP_SHIFT) 2并进行数据迁移操作。 表示当前线程正在进行扩容操作else if (U.compareAndSwapInt(this, SIZECTL, sc,(rs RESIZE_STAMP_SHIFT) 2))transfer(tab, null);}}
}addCount // 添加到计数中如果表太小且尚未调整大小则启动传输。如果已经调整大小则在有工作可用时帮助执行转移。转移后重新检查占用情况以查看是否需要再次调整大小因为调整大小是滞后的添加。
private final void addCount(long x, int check) { // check0 表示扩容添加否则非添加// 这里采用CounterCell数组的方式来缓解cas计算count的压力CounterCell[] as; long b, s;/*变量说明as表示 counterCells 数组用于存储计数器的单元格。U是一个用于执行原子操作的工具类。BASECOUNT表示 baseCount 字段的偏移量用于在内存中定位该字段。b表示当前的 baseCount 值。s表示计数操作后的新的 baseCount 值。CounterCell是一个用于存储计数器值的单元格。v表示单元格中的计数器值。m表示 counterCells 数组的长度减 1。uncontended表示计数操作是否存在竞争的标志。*///首先检查计数器是否使用了数组来存储计数值counterCells如果是则使用原子操作增加计数值//对baseCount进行cas操作 如果成功 那么直接返回 失败的话 就走下面的逻辑if ((as counterCells) ! null ||!U.compareAndSwapLong(this, BASECOUNT, b baseCount, s b x)) {CounterCell a; long v; int m;boolean uncontended true;
//如果增加失败或者计数器没有使用数组存储计数值或者数组中的某个单元格被占用则调用 fullAddCount 方法来处理增加计数的逻辑if (as null || (m as.length - 1) 0 ||(a as[ThreadLocalRandom.getProbe() m]) null ||!(uncontended U.compareAndSwapLong(a, CELLVALUE, v a.value, v x))) {fullAddCount(x, uncontended);/*这里return 的原因
是为了避免频繁地进行数组的扩容操作。如果每次执行CAS操作失败都立即进行扩容检查会增加额外的开销并且可能导致扩容操作频繁进行影响性能。
相反将失败的情况交给fullAddCount()方法处理可以在该方法中根据具体的情况来判断是否需要进行数组的扩容操作。这种延迟扩容的方式可以在一定程度上减少不必要的扩容操作提高性能。*/return;}// 只有一个或没有计数存在if (check 1)return;s sumCount();}//它通过 check 参数控制是否需要进行表格扩容。// 如果 check 大于等于 0if (check 0) {NodeK,V[] tab, nt; int n, sc;//则会检查 当前计数值 s 是否超过了 sizeCtl 的值并且表格 table 不为 null并且表格长度小于最大容量。while (s (long)(sc sizeCtl) (tab table) ! null (n tab.length) MAXIMUM_CAPACITY) {int rs resizeStamp(n) RESIZE_STAMP_SHIFT;if (sc 0) {//sc 是否等于 rs MAX_RESIZERS 或者 rs 1或者 nextTable 为 null或者 transferIndex 小于等于 0if (sc rs MAX_RESIZERS || sc rs 1 ||(nt nextTable) null || transferIndex 0)break;if (U.compareAndSwapInt(this, SIZECTL, sc, sc 1))// 会调用 transfer 方法来进行表格扩容。transfer(tab, nt);}else if (U.compareAndSwapInt(this, SIZECTL, sc, rs 2))transfer(tab, null);s sumCount();}}}fullAddCount 和Atomic 类源码浅析二cas 分治思想的原子累加器文章 中的 striped64中的 longAccumulate 类似 private final void fullAddCount(long x, boolean wasUncontended) {int h;// 获取当前线程的探针如果h的值为0表示当前线程的probe尚未初始化if ((h ThreadLocalRandom.getProbe()) 0) { ThreadLocalRandom.localInit(); // 通过ThreadLocalRandom.localInit()强制进行初始化// 然后再次获取h的值同时将wasUncontended的值设为true表示当前线程是未争用的。h ThreadLocalRandom.getProbe();//将 wasUncontended 的值设为 true表示当前线程是未争用的。wasUncontended true;}boolean collide false; // True if last slot nonemptyfor (;;) {CounterCell[] as; CounterCell a; int n; long v;// 第一次进入方法counterCells肯定是 null 所以不会走这个if的逻辑//判断计数器的数组counterCells是否为空以及数组的长度n是否大于0。如果满足条件进入下一步判断。if ((as counterCells) ! null (n as.length) 0) {// 当前线程所用CounterCell数组下标的值为null // 尝试获取数组中指定位置的计数器a。如果a为null表示该位置为空可以尝试创建新的计数器。if ((a as[(n - 1) h]) null) {// 没有加锁if (cellsBusy 0) { // Try to attach new CellCounterCell r new CounterCell(x); // Optimistic create//加锁if (cellsBusy 0 U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {boolean created false;try { // Recheck under lockCounterCell[] rs; int m, j;// 加锁之后再次检查指定位置是否为空 数组初始化过了 当前位置的值不是nullif ((rs counterCells) ! null (m rs.length) 0 rs[j (m - 1) h] null) {//将新的计数器 r 放置在计数器数组的指定位置 j并将 created 的值设为 true表示成功创建了新的计数器。rs[j] r;created true;}} finally {//解锁cellsBusy 0;}// 计数器增加操作完成跳出循环。if (created)break;continue; // Slot is now non-empty}}collide false;}//如果指定位置的计数器a不为空表示该位置已经有计数器存在。//会根据wasUncontended的值来判断是否已经尝试过CAS操作。//如果wasUncontended为false表示之前尝试过CAS操作失败发生了竞争会将wasUncontended设为true以便下次使用之后继续循环else if (!wasUncontended) // CAS already known to failwasUncontended true; // Continue after rehash// 尝试使用 CAS 操作将计数器 a 的值增加 x。如果 CAS 操作成功即成功将计数器的值增加了 x则跳出循环完成计数器增加操作。else if (U.compareAndSwapLong(a, CELLVALUE, v a.value, v x))break;//如果CAS操作失败代码会继续判断计数器数组是否发生变化以及数组的长度是否达到处理器数量最大值。//如果发生了变化或达到最大值表示计数器数组已经无法继续扩容将collide设为false表示不再尝试扩容else if (counterCells ! as || n NCPU)collide false; // At max size or staleelse if (!collide)collide true;//如果collide为true表示之前已经发生过碰撞即CAS操作失败并且当前没有其他线程在操作计数器数组代码会尝试获取操作计数器数组的锁。//加锁else if (cellsBusy 0 U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {try {//如果成功获取锁进行数组的扩容操作。if (counterCells as) {// Expand table unless stale// 对counterCells进行扩容 扩容为原来的2倍CounterCell[] rs new CounterCell[n 1];// 原数组as中的元素复制到新数组rs中。for (int i 0; i n; i)rs[i] as[i];// 将collide设为false表示不再尝试扩容。// 将新数组赋值给counterCells字段以扩展计数器数组的大小。counterCells rs;}} finally {cellsBusy 0;}collide false;//扩容成功 进入下一次循环continue; // Retry with expanded table}h ThreadLocalRandom.advanceProbe(h);}//首次进入方法 肯定是0 而且counterCells没有初始化 应该是null// 以cas的方式进行加锁 保证只有一个线程来进行初始化// 进行计数器数组初始化时如果当前没有其他线程在操作计数器数组并且成功获取到操作计数器数组的锁else if (cellsBusy 0 counterCells as U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {boolean init false;try { // Initialize table// 如果 counterCells 等于 as则创建一个长度为 2 的 CounterCell 数组 rs。在 rs 数组的索引位置 h 1 处创建一个新的 CounterCell 对象并将其赋值给 rs 数组。if (counterCells as) {//默认创建一个大小为2的数组 并且为当前线程CounterCell[] rs new CounterCell[2];// 将新创建的计数器CounterCell赋值给新数组rs的指定位置rs[h 1] new CounterCell(x);//初始化当前线程需要的数组下标的CounterCellcounterCells rs;init true;}} finally {cellsBusy 0;}if (init)break;}//最后如果还是没有计算成功 那么cas加到baseCount中else if (U.compareAndSwapLong(this, BASECOUNT, v baseCount, v x))break; // Fall back on using base}
}sumCount final long sumCount() {//它首先将counterCells数组赋值给asCounterCell[] as counterCells; CounterCell a;//然后将baseCount赋值给sum。long sum baseCount;//如果as不为nullif (as ! null) {//就会遍历as数组并将每个元素的value值累加到sum中for (int i 0; i as.length; i) {if ((a as[i]) ! null)sum a.value;}}// 返回计算得到的总和sumreturn sum;
}get public V get(Object key) {NodeK,V[] tab; NodeK,V e, p; int n, eh; K ek;int h spread(key.hashCode());// 数组值不是 null 并且 该元素存在if ((tab table) ! null (n tab.length) 0 (e tabAt(tab, (n - 1) h)) ! null) {// 是数组if ((eh e.hash) h) {if ((ek e.key) key || (ek ! null key.equals(ek)))return e.val;}// 表示节点 e 是一个链表或树的根节点else if (eh 0)return (p e.find(h, key)) ! null ? p.val : null;// 节点 e 是一个链表的非根节点那么通过循环遍历链表中的每个节点进行查找while ((e e.next) ! null) {//如果节点 e 的哈希值与给定哈希值 h 相等并且节点 e 的键与给定键 key 相等或者键 ek 不为 null 且与给定键 key 相等if (e.hash h ((ek e.key) key || (ek ! null key.equals(ek))))// 返回节点 e 的值 val return e.val;}}return null;
}find
Node
NodeK,V find(int h, Object k) {NodeK,V e this;//如果键值 k 不为 null则进入循环。if (k ! null) {do {K ek;//在循环中首先将节点 e 的哈希值与给定哈希值 h 进行比较然后继续执行以下操作if (e.hash h ((ek e.key) k || (ek ! null k.equals(ek))))return e;//节点后移直到return} while ((e e.next) ! null);}return null;
}ForwardingNode
// 哈希表中查找给定哈希值h和键k对应的节点。它使用了循环来避免在转发节点上出现任意深度的递归
NodeK,V find(int h, Object k) {// loop to avoid arbitrarily deep recursion on forwarding nodesouter: for (NodeK,V[] tab nextTable;;) {NodeK,V e; int n;//找不到 返回 nullif (k null || tab null || (n tab.length) 0 ||(e tabAt(tab, (n - 1) h)) null)return null;for (;;) {int eh; K ek;//匹配到key 直接返回 eif ((eh e.hash) h ((ek e.key) k || (ek ! null k.equals(ek))))return e;// 迁移 或者 是 树if (eh 0) {// 是 迁移节点 将转发节点的下一个数组赋值给变量 tab并继续外部循环跳到标签 outer 处if (e instanceof ForwardingNode) {tab ((ForwardingNodeK,V)e).nextTable;continue outer;}else// 调用树的方法找节点return e.find(h, k);}// 节点后移直到结尾都找不到 返回 nullif ((e e.next) null)return null;}}
}TreeBin
// 在红黑树中查找指定哈希值和键对应的节点
final NodeK,V find(int h, Object k) {// k 存在if (k ! null) {// 遍历节点for (NodeK,V e first; e ! null; ) {int s; K ek;//判断当前对象的 lockState 的值是否为 WAITER 或 WRITER即是否有其他线程在等待或持有写锁if (((s lockState) (WAITER|WRITER)) ! 0) {
//判断节点 e 的哈希值与给定哈希值 h 相等并且节点 e 的键与给定键 k 相等或者键 ek 不为 null 且与给定键 k 相等。if (e.hash h ((ek e.key) k || (ek ! null k.equals(ek))))// 如果满足条件则返回节点 e。return e;// e 后移e e.next;}// 要是没有 其他线程在等待或持有写锁// 使用 compareAndSwapInt 方法将当前对象的 lockState 的值增加 READER即获取读锁else if (U.compareAndSwapInt(this, LOCKSTATE, s, s READER)) {TreeNodeK,V r, p;try {//调用红黑树的 findTreeNode 方法在红黑树中查找匹配的节点并将结果赋值给变量 pp ((r root) null ? null :r.findTreeNode(h, k, null));} finally {// 通过 getAndAddInt 方法将当前对象的 lockState 的值减去 READER即释放读锁。//如果在释放读锁之前当前对象的 lockState 的值为 (READER|WAITER)并且存在等待线程 waiter则使用 unpark 方法唤醒等待线程。Thread w;if (U.getAndAddInt(this, LOCKSTATE, -READER) (READER|WAITER) (w waiter) ! null)LockSupport.unpark(w);}return p;}}}//表示在红黑树中没有找到匹配的节点返回 nullreturn null;}final TreeNodeK,V findTreeNode(int h, Object k, Class? kc) {//首先检查传入的键k是否为空如果为空则直接返回null。if (k ! null) {TreeNodeK,V p this;//如果键k不为空则从当前节点开始进行查找。使用一个循环不断根据哈希值h和键k的比较结果来决定下一步的查找方向。do {int ph, dir; K pk; TreeNodeK,V q;TreeNodeK,V pl p.left, pr p.right;// 如果当前节点的哈希值大于h则向左子节点继续查找if ((ph p.hash) h)p pl;//如果当前节点的哈希值小于h则向右子节点继续查找else if (ph h)p pr;//如果当前节点的哈希值等于h则比较键值。else if ((pk p.key) k || (pk ! null k.equals(pk)))// 如果键值相等则找到了目标节点直接返回该节点。return p;//如果左子节点为空则向右子节点继续查找。else if (pl null)p pr;// 如果右子节点为空则向左子节点继续查找。else if (pr null)p pl;//如果传入的键比较类kc不为空或者通过方法comparableClassFor(k)获取到了键的比较类kc并且通过方法compareComparables(kc, k, pk)比较键k和当前节点的键pk的大小else if ((kc ! null ||(kc comparableClassFor(k)) ! null) (dir compareComparables(kc, k, pk)) ! 0)//得到一个非零的结果dir那么根据dir的正负来决定下一步的查找方向。p (dir 0) ? pl : pr;//如果以上条件都不满足则说明需要在右子树中继续查找递归调用右子节点的findTreeNode方法else if ((q pr.findTreeNode(h, k, kc)) ! null)return q;else p pl;} while (p ! null);}// 如果循环结束时仍然没有找到目标节点则返回null。return null;}TreeNode
// 在二叉树中查找给定哈希值h和键k对应的节点
NodeK,V find(int h, Object k) {return findTreeNode(h, k, null);
}remove public V remove(Object key) {return replaceNode(key, null, null);
}replaceNode
//在哈希表中替换指定键的节点值
final V replaceNode(Object key, V value, Object cv) {int hash spread(key.hashCode());for (NodeK,V[] tab table;;) {NodeK,V f; int n, i, fh;if (tab null || (n tab.length) 0 ||(f tabAt(tab, i (n - 1) hash)) null)break;// 表示节点f是一个转发节点else if ((fh f.hash) MOVED)tab helpTransfer(tab, f);else {V oldVal null;boolean validated false;synchronized (f) {if (tabAt(tab, i) f) {//在链表中查找匹配的节点并根据验证对象cv与节点值的关系来确定是否进行替换以及如何进行替换。如果找到匹配的节点则更新节点的值为新值value或者移除该节点。最后返回被替换的旧值。if (fh 0) {validated true;for (NodeK,V e f, pred null;;) {K ek;if (e.hash hash ((ek e.key) key ||(ek ! null key.equals(ek)))) {V ev e.val;// 如果验证对象cv为null或者验证对象cv与节点的旧值ev引用相同或者验证对象cv与节点的旧值ev相等通过equals方法比较if (cv null || cv ev ||(ev ! null cv.equals(ev))) {oldVal ev;// 如果新值value不为空if (value ! null)//则更新节点e的值为新值valuee.val value;// 如果前驱节点pred不为空else if (pred ! null)// 则将前驱节点的next指向节点e的nextpred.next e.next;else// 否则将哈希桶中的第一个节点指向节点e的next。setTabAt(tab, i, e.next);}break;}pred e;if ((e e.next) null)break;}}//在树中查找匹配的节点并根据验证对象cv与节点值的关系来确定是否进行替换以及如何进行替换。如果验证通过则更新节点的值为新值value或者移除该节点。最后返回被替换的旧值。else if (f instanceof TreeBin) {// 将标志位validated设置为true表示已经验证过节点f。validated true;// 将节点f强制转换为树节点(TreeBin)类型并赋值给变量t。TreeBinK,V t (TreeBinK,V)f;//定义了两个变量r和p分别表示树节点t的根节点和要查找的节点。TreeNodeK,V r, p;//如果树节点t的根节点r不为null并且通过给定的哈希值hash和键key调用 findTreeNode方法 在树中找到了匹配的节点p if ((r t.root) ! null (p r.findTreeNode(hash, key, null)) ! null) {//获取节点p的值pv。V pv p.val;//如果验证对象cv为null或者验证对象cv与节点p的值pv引用相同或者验证对象cv与节点p的值pv相等通过equals方法比较if (cv null || cv pv ||(pv ! null cv.equals(pv))) {//将节点p的值pv赋值给变量oldVal用于最后返回被替换的旧值。oldVal pv;//如果新值value不为null将节点p的值更新为新值value。if (value ! null)p.val value;//如果新值value为null并且成功移除了节点p(通过调用树节点t的removeTreeNode方法)else if (t.removeTreeNode(p))//将树的第一个节点转为普通节点放到当前位置上setTabAt(tab, i, untreeify(t.first));}}}}}if (validated) {if (oldVal ! null) {if (value null)// 更新并发哈希表的计数器addCount(-1L, -1);return oldVal;}break;}}}return null;
}clear public void clear() {//初始化变量delta为0用于记录删除的节点数量。long delta 0L; // negative number of deletions//使用变量i遍历哈希表的每个槽位。int i 0;NodeK,V[] tab table;while (tab ! null i tab.length) {int fh;// 获取当前槽位tab[i]的节点f。NodeK,V f tabAt(tab, i);// 如果f为null则说明该槽位没有节点将i加1继续遍历下一个槽位。if (f null)i;// 如果f的哈希值为MOVED说明该节点正在进行迁移操作需要调用helpTransfer方法帮助完成迁移并重新从头开始遍历。else if ((fh f.hash) MOVED) {tab helpTransfer(tab, f);i 0; // restart}//否则使用synchronized关键字对节点f进行同步操作确保多线程环境下的安全性。else {synchronized (f) {// 检查当前槽位tab[i]是否仍然是节点f防止其他线程修改了节点。if (tabAt(tab, i) f) {//如果f是树节点(TreeBin)则获取树的首节点遍历树节点链表同样将每个节点p的delta减1并将tab[i]置为null。继续遍历下一个槽位直到遍历完整个哈希表。NodeK,V p (fh 0 ? f :(f instanceof TreeBin) ?((TreeBinK,V)f).first : null);//如果f是普通节点则遍历节点链表将每个节点p的delta减1并将tab[i]置为null表示删除节点。while (p ! null) {--delta;p p.next;}setTabAt(tab, i, null);}}}}// 如果delta不等于0调用addCount方法将delta加到计数器中if (delta ! 0L)addCount(delta, -1);
}总结
initTable的主要流程 1、要是数组正在初始化就礼让出cpu 2、否则的话就 设置数组的大小设置阈值 addCount的主要流程
阶段一计算元素个数 1、在竞争的时候 调用 fullAddCount(x, uncontended) 增加 map 集合中的元素个数之后返回 2、在没有竞争但是 计数put中就是 bitCount 1 的时候 直接返回 3、在没有竞争但是 计数 1 的时候调用 sumCount() 累加得到元素个数之后进行检查要不要扩容 阶段二检查扩容 1、数组超过阈值 并且当前节点正在执行扩容操作 1.1、无法扩容就退出循环 1.2、此时要是允许扩容那么就cas 的方式增加sizeCtl 的值cas 的目的就是避免了多个线程同时进行数据迁移操作保证只有一个线程可以成功执行扩容cas 成功那么就会进行扩容 2、要是当前节点不在进行扩容那么就cas 的方式更新sc的值cas 成功就进行扩容 3、要是两个cas的操作都失败了那么就统计 map 中的所有的元素的个数并进行下一次循环 helpTransfer主要流程 1、要是当前节点不在迁移就表示不需要进行扩容和数据迁移返回原始的数组 2、要是当前节点在迁移并且处于可以执行扩容就cas 的方式增加sizeCtl 的值cas 的目的就是避免了多个线程同时进行数据迁移操作保证只有一个线程可以成功执行扩容cas 成功那么就会进行扩容无论能否执行扩容最后都返回迁移之后的数组 treeifyBin主要流程 1、要是初始化过数组长度 64 尝试对数组扩容调用tryPresize 2、要是数组长度 64 指定位置的节点有值该节点后面是链表 3、加锁再次检查当前位置的元素没有在多线程场景下被别的线程修改那么就将所有的链表节点转为树节点然后连接起来再将所有的节点转为红黑树并设置到对应的位置上 tryPresize主要流程 1、根据传入的size参数计算出 扩容的目标大小c 只要数组不在初始化就进行扩容 2、但是数组是null,那么就和设置数组的大小设置阈值 3、要是当前节点正在执行扩容 3.1、无法扩容就退出循环 3.2、此时要是允许扩容那么就cas 的方式增加sizeCtl 的值cas 的目的就是避免了多个线程同时进行数据迁移操作保证只有一个线程可以成功执行扩容cas 成功那么就会进行扩容cas失败就继续下一次循环 4、要是当前节点不在进行扩容那么就进行扩容 fullAddCount主要流程 无限循环 1、要是处于竞争状态 1.1、当前位置值为null那么就加锁尝试在数组中插入一个新的Cells 对象 1.2、当前位置有值cas 的更新此位置的值成功就跳出循环 1.3、cas 失败要是不能扩容就不再尝试扩容 1.4、要是能继续扩容就加锁扩容扩容为两倍 2、要是不处于竞争状态但是Cells 数组没有被其他线程占用加锁初始化这个数组的位置的值 3、不处于竞争状态并且数组这个位置被占用就直接进行计算 put 主要流程总结 循环遍历数组 1、要是数组没有初始化那么就进行初始化 2、要是指定位置的没有值此时是不加锁的那么就cas 的方式插入成功退出循环失败继续下一次循环 是数组上的节点 3、要是当前节点正在迁移处于 MOVED 状态那么就 进行协助迁移 4、否则这个节点就是正常的节点那么就根据 是树还是链表执行对应的操作 是树或者链表上的节点 4.1、对树或者链表 找到就进行覆盖并返回旧值找不到就加到链表的结尾返回null 锁住头节点开始执行 4.2、要是对树或者链表 执行成功那判断是不是 阈值要是 8 那么就进行树化 5、最后增加map 中的元素个数累加的原理和 原子累加器类似最后在这个里面决定要不要扩容 transfer 的流程总结 1、要是开始扩容了那么就将数组扩大到2倍 无限循环中 2、判断是不是要继续迁移要是要迁移就更新相应的扩容边界和相关变量 3、要是 超过了索引的范围 3.1、迁移已经完成了那么就替换数组为扩容数组和更新阈值返回 3.2、要是迁移没有完成那么就cas 的方式把 sc -1 3.2.1、cas 成功的话 3.2.1.1 要是存在竞争无法扩容直接返回 3.2.1.2 要是不存在竞争更新结束进行下次循环 3.2.2、cas 失败继续下次循环 4、要是当前值为null ,cas 的将当前节点设置为转化节点进行下次循环 5、要是当前节点正在前移状态进行下次循环 6、加锁锁住这个位置的节点 那么此时就是链表或者树那么就进行迁移此时的迁移会有高低位之分高位节点放到 新数组中 原来位置 原来数组长度 的索引低位的放到新数组中原来的索引注意树的结构中要是当前树的长度 6要调用untreeify取消树化。 get 流程总结 1、指定位置的值存在hash 等且key 相等返回 2、要是hash 不等是链表的话就遍历直到找到一样的找到返回该值找不到返回 null 3、要是不是链表调用对应的节点数据类型的find 方法找到返回该值找不到返回 null remove 流程总结 循环遍历数组 1、要是 数组没有初始化或者当期位置的值为 null退出循环 2、要是当前位置的节点处于迁移状态进行协助迁移 3、锁住当前位置的节点 3.1、是链表就遍历链表 3.1.1、要是找到对应 key 的值返回旧值 3.1.1.1、新值不是null 就把这个值设置为新值 「使用的api 是 remove(Object key, Object value)」 3.1.1.2、新值是null但是当前节点前驱节点不是 null就更新链表中相关删除节点前后的指针关系「要是使用的api 是 remove(Object key)」 3.1.1.3、要是当前节点前驱节点是 null ,那么就在指定的位置设置为删除节点的后继节点结束循环 3.1.2、要是找不到对应的值就后移直到 null结束循环null 表示遍历完链表都找不到这个key ,该 key 对应的节点不存在返回 null 3.2、是树调用 树的 findTreeNode方法 在树中找到了匹配的节点p 3.2.1、要是找到节点返回旧的值 3.2.1.1、要是新值不为null就更新对应的节点的值 3.2.1.2、要是新值为null就调用树的 removeTreeNode方法 移除这个节点并将树的第一个节点转为普通节点放到当前位置上 3.2.2 、要是找不到节点返回null 4、要是新值为 null 就 更新数组中的元素个数 clear流程总结 进行循环循环条件—数组存在没有遍历结束 1、要是当前节点为 null ,后移动节点 2、要是当前节点正在迁移 进行 协助迁移 3、加锁锁住当前位置的节点要是节点是链表或者树的节点遍历所有节点对所有节点的值置为 null要是存在被清除的节点就进行原子累加的操作更新 map中所有元素总数的大小
