2023年7月27日发(作者：)

java并发map_Java并发包——线程安全的Map相关类Java并发包——线程安全的Map相关类摘要：本⽂主要学习了Java并发包下线程安全的Map相关的类。部分内容来⾃以下博客：分类参照之前在学习集合时候的分类，可以将JUC下有关Map相关的类进⾏分类。ConcurrentHashMap：继承于AbstractMap类，相当于线程安全的HashMap，是线程安全的哈希表。JDK1.7之前使⽤分段锁机制实现，JDK1.8则使⽤数组+链表+红⿊树数据结构和CAS原⼦操作实现。ConcurrentSkipListMap：继承于AbstractMap类，相当于线程安全的TreeMap，是线程安全的有序的哈希表。通过“跳表”来实现的。ConcurrentHashMapJDK1.7的分段锁机制Hashtable之所以效率低下主要是因为其实现使⽤了synchronized关键字对put等操作进⾏加锁，⽽synchronized关键字加锁是对整个对象进⾏加锁。也就是说在进⾏put等修改Hash表的操作时，锁住了整个Hash表，从⽽使得其表现的效率低下。因此，在JDK1.5到1.7版本，Java使⽤了分段锁机制实现ConcurrentHashMap。简⽽⾔之，ConcurrentHashMap在对象中保存了⼀个Segment数组，即将整个Hash表划分为多个分段。⽽每个Segment元素，即每个分段则类似于⼀个Hashtable。在执⾏put操作时⾸先根据hash算法定位到元素属于哪个Segment，然后使⽤ReentrantLock对该Segment加锁即可。因此，ConcurrentHashMap在多线程并发编程中可是实现多线程put操作。Segment类是ConcurrentHashMap中的内部类，继承于ReentrantLock类。ConcurrentHashMap与Segment是组合关系，⼀个ConcurrentHashMap对象包含若⼲个Segment对象，ConcurrentHashMap类中存在“Segment数组”成员。HashEntry也是ConcurrentHashMap的内部类，是单向链表节点，存储着key-value键值对。Segment与HashEntry是组合关系，Segment类中存在“HashEntry数组”成员，“HashEntry数组”中的每个HashEntry就是⼀个单向链表。JDK1.8的改进在JDK1.7的版本，ConcurrentHashMap是通过分段锁机制来实现的，所以其最⼤并发度受Segment的个数限制。因此，在JDK1.8中，ConcurrentHashMap的实现原理摒弃了这种设计，⽽是选择了与HashMap类似的数组+链表+红⿊树的⽅式实现，⽽加锁则采⽤CAS原⼦更新、volatile关键字、synchronized可重⼊锁实现。JDK1.8的实现降低锁的粒度，JDK1.7版本锁的粒度是基于Segment的，包含多个HashEntry，⽽JDK1.8锁的粒度就是HashEntry(⾸节点)。JDK1.8版本的数据结构变得更加简单，使得操作也更加清晰流畅，因为已经使⽤synchronized来进⾏同步，所以不需要分段锁的概念，也就不需要Segment这种数据结构了，由于粒度的降低，实现的复杂度也增加了。JDK1.8版本的扩容操作⽀持多线程并发。在之前的版本中如果Segment正在进⾏扩容操作，其他写线程都会被阻塞，JDK1.8改为⼀个写线程触发了扩容操作，其他写线程进⾏写⼊操作时，可以帮助它来完成扩容这个耗时的操作。JDK1.8使⽤红⿊树来优化链表，基于长度很长的链表的遍历是⼀个很漫长的过程，⽽红⿊树的遍历效率是很快的，代替⼀定阈值的链表。重要属性sizeCtl：标志控制符。这个参数⾮常重要，出现在ConcurrentHashMap的各个阶段，不同的值也表⽰不同情况和不同功能：负数代表正在进⾏初始化或扩容操作。-1表⽰正在进⾏初始化操作。-N表⽰有N-1个线程正在进⾏扩容操作。其为0时，表⽰hash表还未初始化。正数表⽰下⼀次进⾏扩容的⼤⼩，类似于扩容阈值。它的值始终是当前容量的0.75倍，如果hash表的实际⼤⼩>=sizeCtl，则进⾏扩容。构造⽅法需要说明的是，在构造⽅法⾥并没有对集合进⾏初始化操作，⽽是等到了添加元素的时候才进⾏初始化，属于懒汉式的加载⽅式。⽽且loadFactor参数在JDK1.8中也不再有加载因⼦的意义，仅为了兼容以前的版本，加载因⼦由sizeCtl来替代。同样，concurrencyLevel参数在JDK1.8中也不再有多线程运⾏的并发度的意义，仅为了兼容以前的版本。1 //空参构造器。2 publicConcurrentHashMap() {3 }45 //指定初始容量的构造器。6 public ConcurrentHashMap(intinitialCapacity) {7 //参数有效性判断。8 if (initialCapacity < 0)9 throw newIllegalArgumentException();10 int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>>1)) ?11 MAXIMUM_CAPACITY :12 tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));13 //设置标志控制符。14 l =cap;15 }1617 //指定初始容量，加载因⼦的构造器。18 public ConcurrentHashMap(int initialCapacity, floatloadFactor) {19 this(initialCapacity, loadFactor, 1);20 }2122 //指定初始容量，加载因⼦，并发度的构造器。23 public ConcurrentHashMap(int initialCapacity, float loadFactor, intconcurrencyLevel) {24 //参数有效性判断。25 if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)26 throw newIllegalArgumentException();27 //⽐较初始容量和并发度的⼤⼩，取最⼤值作为初始容量。28 if (initialCapacity31 long size = (long)(1.0 + (long)initialCapacity /loadFactor);32 int cap = (size >= (long)MAXIMUM_CAPACITY) ?33 MAXIMUM_CAPACITY : tableSizeFor((int)size);34 //设置标志控制符。35 l =cap;36 }3738 //包含指定Map集合的构造器。39 public ConcurrentHashMap(Map extends K, ? extends V>m) {40 //设置标志控制符。41 l =DEFAULT_CAPACITY;42 //放置指定的集合。43 putAll(m);44 }初始化⽅法集合并不会在构造⽅法⾥进⾏初始化，⽽是在⽤到集合的时候才进⾏初始化，在初始化的同时会设置集合的阈值。初始化⽅法主要应⽤了关键属性sizeCtl，如果sizeCtl⼩于0，表⽰其他线程正在进⾏初始化，就放弃这个操作，在这也可以看出初始化只能由⼀个线程完成。如果获得了初始化权限，就⽤CAS⽅法将sizeCtl置为-1，防⽌其他线程进⼊。初始化完成后，将sizeCtl的值改为0.75倍的集合容量，作为阈值。在初始化的过程中为了保证线程安全，总共使⽤了两步操作：1)通过CAS原⼦更新⽅法将sizeCtl设置为-1，保证只有⼀个线程进⼊。2)线程获取初始化权限后内部通过 if ((tab = table) == null || == 0) ⼆次判断，保证只有在未初始化的情况下才能执⾏初始化。1 //初始化集合，使⽤CAS原⼦更新保证线程安全，使⽤volatile保证顺序和可见性。2 private final Node[] initTable() {3 Node[] tab; intsc;4 //死循环以完成初始化。5 while ((tab = table) == null || == 0) {6 //如果sizeCtl⼩于0则表⽰正在初始化，当前线程让步。7 if ((sc = sizeCtl) < 0)8 ();9 //如果需要初始化，并且使⽤CAS原⼦更新。判断SIZECTL保存的sizeCtl值是否和sc⼀致，⼀致则将sizeCtl更新为-1。10 else if (eAndSwapInt(this, SIZECTL, sc, -1)) {11 try{12 //第⼀个线程初始化之后，第⼆个线程还会进来所以需要重新判断。类似于线程同步的⼆次判断。13 if ((tab = table) == null || == 0) {14 //如果没有指定容量则使⽤默认容量16。15 int n = (sc > 0) ?sc : DEFAULT_CAPACITY;16 //初始化⼀个指定容量的节点数组。17 @SuppressWarnings("unchecked")18 Node[] nt = (Node[])new Node,?>[n];19 //将节点数组指向集合。20 table = tab =nt;21 //扩容阀值，获取容量的0.75倍的值，写法略叼更⾼端⽐直接乘⾼效。22 sc = n - (n >>> 2);23 }24 } finally{25 //将sizeCtl的值设为阈值。26 sizeCtl =sc;27 }28 break;29 }30 }31 returntab;32 }添加⽅法1)校验数据。判断传⼊⼀个key和value是否为空，如果为空就直接报错。ConcurrentHashMap是不可为空的(HashMap是可以为空的)。2)是否要初始化。判断table是否为空，如果为空就进⼊初始化阶段。3)如果数组中key指定的桶是空的，那就使⽤CAS原⼦操作把键值对插⼊到这个桶中作为头节点。4)协助扩容。如果这个要插⼊的桶中的hash值为-1，也就是MOVED状态(也就是这个节点是ForwordingNode)，那就是说明有线程正在进⾏扩容操作，那么当前线程就进⼊协助扩容阶段。5)插⼊数据到链表或者红⿊树。如果这个节点是链表节点，那么就遍历这个链表，如果有相同的key值就更新value值，如果没有发现相同的key值，就在链表的尾部插⼊该数据。如果这个节点是红⿊树节点，那就需要按照树的插⼊规则进⾏插⼊。6)转化成红⿊树。插⼊结束之后判断如果是链表节点，并且个数⼤于8，就需要把链表转化为红⿊树存储。7)添加结束之后，需要给增加已存储的数量，并判断是否需要扩容。1 //添加元素。2 publicV put(K key, V value) {3 return putVal(key, value, false);4 }56 //添加元素。7 final V putVal(K key, V value, booleanonlyIfAbsent) {8 //排除null的数据。9 if (key == null || value == null) throw newNullPointerException();10 //计算hash，并保证hash⼀定⼤于零，负数表⽰在扩容或者是树节点。11 int hash =spread(de());12 //节点个数。0表⽰未加⼊新结点，2表⽰TreeBin或链表结点数，其它值表⽰链表结点数。主要⽤于每次加⼊结点后查看是否要由链表转为红⿊树。13 int binCount = 0;14 //CAS经典写法，不成功⽆限重试。15 for (Node[] tab =table;;) {16 //声明节点、集合长度、对应的数组下标、节点的hash值。17 Node f; intn, i, fh;18 //如果没有初始化则进⾏初始化。除⾮构造时指定集合，否则默认构造不初始化，添加时检查是否初始化，属于懒汉模式初始化。19 if (tab == null || (n = ) == 0)20 //初始化集合。21 tab =initTable();22 //如果已经初始化了，并且使⽤CAS根据hash获取到的节点为null。23 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {24 //使⽤CAS⽐较该索引处是否为null防⽌其它线程已改变该值，null则插⼊。25 if (casTabAt(tab, i, null, new Node(hash, key, value, null)))26 //添加成功，跳出循环。27 break;28 }29 //如果获取到节点不为null，并且节点的hash为-1，则表⽰节点在扩容。30 else if ((fh = ) ==MOVED)31 //帮助扩容。32 tab =helpTransfer(tab, f);33 //产⽣hash碰撞，并且没有扩容操作。34 else{35 V oldVal = null;36 //锁住节点。37 synchronized(f) {38 //这⾥volatile获取⾸节点与节点对⽐判断节点还是不是⾸节点。39 if (tabAt(tab, i) ==f) {40 //判断是否是链表节点。41 if (fh >= 0) {42 //记录节点个数。43 binCount = 1;44 //循环完成添加节点到链表。45 for (Node e = f;; ++binCount) {46 K ek;47 if ( == hash && ((ek = ) == key || (ek != null &&(ek)))){48 oldVal =;49 if (!onlyIfAbsent)50 =value;51 break;52 }53 Node pred =e;54 if ((e = ) == null) { = new Node(hash, key, value, null);56 break;57 }58 }59 }60 //如果是红⿊树节点。61 else if (f instanceofTreeBin) {62 Nodep;63 binCount = 2;64 if ((p = ((TreeBin)f).putTreeVal(hash, key, value)) != null) {65oldVal =;66 if (!onlyIfAbsent)67 =value;68 }69 }70 }71 }72 //如果添加到了链表节点，需要进⼀步判断是否需要转为红⿊树。73 if (binCount != 0) {74 //如果链表上的节点数⼤于等于8。75 if (binCount >=TREEIFY_THRESHOLD)76 //尝试转为红⿊树。77 treeifyBin(tab, i);78 if (oldVal != null)79 //返回原值。80 returnoldVal;81 break;82 }83 }84 }85 //集合容量加⼀并判断是否要扩容。86 addCount(1L, binCount);87 return null;88 }修改容量并判断是否需要扩容1)尝试对baseCount和CounterCell进⾏增加的操作，这些操作基于CAS原⼦操作，同时使⽤volatile保证顺序和可见性。备⽤⽅法fullAddCount()则会死循环插⼊。2)判断是否要扩容操作，并且⽀持多个线程协助进⾏扩容。1 //修改容量并判断是否要扩容。2 private final void addCount(long x, intcheck) {3 CounterCell[] as; longb, s;4 //counterCells不为null，或者使⽤CAS对baseCount增加失败了，说明产⽣了并发，需要进⼀步处理。5 //counterCells初始为null，如果不为null，说明产⽣了并发。6 //如果counterCells仍然为null，但是在使⽤CAS对baseCount增加的时候失败，表⽰产⽣了并发。7 if ((as = counterCells) != null || !eAndSwapLong(this, BASECOUNT, b = baseCount, s = b +x)) {8 CounterCell a;long v; intm;9 boolean uncontended = true;10 //如果counterCells是null的，或者counterCells的个数⼩于0。11 //或者counterCells的每⼀个元素都是null。12 //或者⽤counterCells数组中随机位置的值进⾏累加也失败了。13 if (as == null || (m = - 1) < 0 ||14 (a = as[be() & m]) == null ||15 !(uncontended = eAndSwapLong(a, CELLVALUE, v = , v +x))) {16 //继续更新counterCells和baseCount。17 fullAddCount(x, uncontended);18 return;19 }20 //删除或清理节点时是-1，插⼊索引⾸节点0，第⼆个节点是1。21 if (check <= 1)22 return;23 //计算map元素个数。24 s =sumCount();25 }26 //如果check的值⼤于等于0，需要检查是否要扩容。删除或清理节点时是-1，此时不检查。27 if (check >= 0) {28 Node[] tab, nt; intn, sc;29 //当元素个数⼤于阈值，并且集合不为空，并且元素个数⼩于最⼤值。循环判断，防⽌多线程同时扩容跳过if判断。30 while (s >= (long)(sc = sizeCtl) && (tab = table) != null && (n = )32 int rs =resizeStamp(n);33 //sc在单线程时是⼤于等于0的，如果⼩于0说明有其他线程正在扩容。34 //如果⼩于0说明有线程执⾏了else⾥⾯的判断，导致rs左移16位并在低位+2赋值给sc。35 if (sc < 0) {36 //在第⼀次左移16位的sc，经过第⼆次右移16位之后，还和rs相同，说明已经扩容完成。37 //线程执⾏扩容，会使⽤CAS让sc⾃增，如果sc和右移并累加后的rs相等，说明已经扩容完成。38 //线程执⾏扩容，会使⽤CAS让sc⾃增，如果sc和右移并累加最⼤值后的rs相等，说明已经扩容完成。39 //如果下个节点是null，说明已经扩容完成。40 //如果transferIndex⼩于等于0，说明集合已完成扩容，⽆法再分配任务。41 if ((sc >>> RESIZE_STAMP_SHIFT) != rs ||42 sc == rs + 1 ||//此处应为 sc == (rs << RESIZE_STAMP_SHIFT) + 143 sc == rs + MAX_RESIZERS ||//此处应为 sc == (rs << RESIZE_STAMP_SHIFT) + MAX_RESIZERS44 (nt = nextTable) == null ||45 transferIndex <= 0)46 //跳出循环。47 break;48 //使⽤CAS原⼦累加sc的值。49 if (eAndSwapInt(this, SIZECTL, sc, sc + 1))50 //扩容。51 transfer(tab, nt);52 }53 //如果sizeCtl⼤于或等于0，说明第⼀次扩容，并且使⽤CAS设置sizeCtl为rs左移后的负数，并且低位+2表⽰有2-1个线程正在扩容。54 else if (eAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2))55 //进⾏扩容操作。56 transfer(tab, null);57 //计算map元素个数，baseCount和counterCells数组存的总和。58 s =sumCount();59 }60 }61 }帮助扩容⽅法1)判断集合已经完成初始化，并且节点是ForwordingNode类型(表⽰正在扩容)，并且当前节点的⼦节点不为null，如果不成⽴则不需要扩容。2)循环判断是否扩容成功，如果没有就使⽤CAS原⼦操作累加扩容的线程数，并且进⾏协助扩容。1 //帮助扩容。2 final Node[] helpTransfer(Node[] tab, Nodef) {3 Node[] nextTab; intsc;4 //如果表不为null，并且是fwd类型的节点，并且节点的⼦节点也不为null。5 if (tab != null && (f instanceof ForwardingNode) && (nextTab = ((ForwardingNode)f).nextTable) != null) {6 //得到标识符。7 int rs =resizeStamp();8 //如果nextTab没有被并发修改，并且tab也没有被并发修改，并且sizeCtl⼩于0说明还在扩容。9 while (nextTab == nextTable && table == tab && (sc = sizeCtl) < 0) {10 //在第⼀次左移16位的sc，经过第⼆次右移16位之后，还和rs相同，说明已经扩容完成。11 //线程执⾏扩容，会使⽤CAS让sc⾃增，如果sc和右移并累加后的rs相等，说明已经扩容完成。12//线程执⾏扩容，会使⽤CAS让sc⾃增，如果sc和右移并累加最⼤值后的rs相等，说明已经扩容完成。13 //如果transferIndex⼩于等于0，说明集合已完成扩容，⽆法再分配任务。14 if ((sc >>> RESIZE_STAMP_SHIFT) != rs ||15 sc == rs + 1 ||//此处应为 sc == (rs << RESIZE_STAMP_SHIFT) + 116 sc == rs + MAX_RESIZERS ||//此处应为 sc == (rs << RESIZE_STAMP_SHIFT) + MAX_RESIZERS17 transferIndex <= 0)18 //跳出循环。19 break;20 //使⽤CAS原⼦累加sc的值。21 if (eAndSwapInt(this, SIZECTL, sc, sc + 1)) {22 //扩容。23 transfer(tab, nextTab);24 break;25 }26 }27 returnnextTab;28 }29 returntable;30 }扩容⽅法1)根据CPU核⼼数平均分配给每个CPU相同⼤⼩的区间，如果不够16个，默认就是16个。2)有且只能由⼀个线程构建⼀个nextTable，这个nextTable是扩容后的数组(容量已经扩⼤)。3)外层使⽤for循环处理每个区间⾥的根节点，内层使⽤while循环让线程领取未扩容的区间。4)处理每个区间的头节点，如果头结点为空，则直接放置⼀个ForwordingNode，通知其他线程帮助扩容。5)处理每个区间的头节点，如果头结点不为空，并且hash不为-1，那么就同步头节点，开始扩容。判断头结点是链表还是红⿊树：如果是链表，则拆分为⾼低两个链表。如果是红⿊树，拆分为⾼低两个红⿊树，并判断是否需要转为链表。1 //进⾏扩容操作。2 private final void transfer(Node[] tab, Node[] nextTab) {3 int n =, stride;4 //根据cpu个数找出扩容时的最⼩分组，最⼩是16。5 if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n)8 if (nextTab == null) {9 try{10 //创建新的扩容后的节点数组。11 @SuppressWarnings("unchecked")12 Node[] nt = (Node[])new Node,?>[n << 1];13 //将新的数组赋值给nextTab。14 nextTab =nt;15 } catch(Throwable ex) {16 //扩容失败，设置sizeCtl为最⼤值。17 sizeCtl =_VALUE;18 return;19 }20 //将新的数组赋值给nextTable。21 nextTable =nextTab;22 //记录要扩容的区间最⼤值，说明是逆序迁移，从⾼位向低位迁移。23 transferIndex =n;24 }25 //设置扩容后的容量。26 int nextn =;27 //创建⼀个fwd节点，⽤于占位，fwd节点的hash默认为-1。当别的线程发现这个槽位中是fwd类型的节点，则跳过这个节点。28 ForwardingNode fwd = new ForwardingNode(nextTab);29 //如果是false，需要处理区间上的当前位置，如果是true，说明需要处理区间上的下⼀个位置。30 boolean advance = true;31 //完成状态，如果是true，就结束此⽅法。32 boolean finishing = false;33 //死循环，i表⽰最⼤下标，bound表⽰最⼩下标。34 for (int i = 0, bound = 0;;) {35 Node f; intfh;36 //循环判断是否要处理区间上的下⼀个位置，每个线程都会在这个循环⾥获取区间。37 while(advance) {38 intnextIndex, nextBound;39 //i⾃减⼀并判断是否⼤于等于bound，以及是否已经完成了扩容。40 //如果i⾃减后⼤于等于bound并且未完成扩容，说明需要处理当前i位置上的节点，跳出while循环。41 //如果i⾃减后⼩于bound并且未完成扩容，说明区间上没有节点需要处理，在while循环⾥继续判读。42 //如果已经完成扩容，跳出while循环。43 if (--i >= bound ||finishing)44 //跳出while循环。45 advance = false;46 //如果要扩容的区间最⼤值⼩于等于0，说明没有区间需要扩容了。47 else if ((nextIndex = transferIndex) <= 0) {48 //i会在下⾯的if块⾥判断，从⽽进⼊完成状态判断。49 i = -1;50 //跳出while循环。51 advance = false;52 }53 //⾸次while循环进⼊，CAS判断transferIndex和nextIndex是否⼀致，将transferIndex修改为最⼤值。54 else if (eAndSwapInt(this, TRANSFERINDEX, nextIndex,55 nextBound = (nextIndex > stride ? nextIndex - stride :0))) {56 //当前线程处理区间的最⼩下标。57 bound =nextBound;58 //初次对i赋值，当前线程处理区间的最⼤下标。59 i = nextIndex - 1;60 //跳出while循环。61 advance = false;62 }63 }64 //判读是否完成扩容。65 //如果i⼩于0，表⽰已经处理了最后⼀段空间。66 //如果i⼤于等于原容量，表⽰超过下标最⼤值。67 //如果i加上原容量⼤于等于新容量，表⽰超过下标最⼤值。68 if (i < 0 || i >= n || i + n >=nextn) {69 intsc;70 //如果完成扩容，finishing为true，表⽰最后⼀个线程完成了扩容。71 if(finishing) {72 //删除成员变量。73 nextTable = null;74 //更新集合。75 table =nextTab;76 //更新阈值。77 sizeCtl = (n << 1) - (n >>> 1);78 return;79 }80 //如果没完成扩容，当前线程完成这段区间的扩容，将sc的低16位减1。81 if (eAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {82 //如果判断是否是最后⼀个扩容线程，如果不等于，说明还有其他线程在扩容，当前线程返回。83 if ((sc - 2) != resizeStamp(n) <86 finishing = advance = true;87 //再次循环检查⼀下整张表。88 i =n;89 }90 }91 //正常处理区间，如果原数组i位置是null，就使⽤fwd占位。92 else if ((f = tabAt(tab, i)) == null)93 //如果成功写⼊fwd占位，进⼊while循环，继续处理区间的下⼀个节点。94 advance = casTabAt(tab, i, null, fwd);95 //正常处理区间，如果原数组i位置不是null，并且hash值是-1，说明别的线程已经处理过了。96 else if ((fh = ) ==MOVED)97 //进⼊while循环，继续处理区间的下⼀个节点。98 advance = true;99 //到这⾥，说明这个位置有实际值了，且不是占位符。100 else{101 //对这个节点上锁，防⽌添加元素的时候向链表插⼊数据。102 synchronized(f) {103 //判断i下标处的桶节点是否和f相同，⼆次校验。104 if (tabAt(tab, i) ==f) {105 //声明⾼位桶和低位桶。106 Nodeln, hn;107 //如果f的hash值⼤于0，表⽰是链表结构。红⿊树的hash默认是-2。108 if (fh >= 0) {109 //获取原容量最⾼位同节点hash值的与运算结果，⽤来判断将该节点放到⾼位还是低位。110 int runBit = fh &n;111 //定义尾节点，暂时取f节点，后⾯会更新。112 Node lastRun =f;113 //遍历这个节点。114 for (Node p = ; p != null; p =) {115 //获取原容量最⾼位同节点hash值的与运算结果，⽤来判断将该节点放到⾼位还是低位。116 int b = &n;117 //如果节点的hash值和⾸节点的hash值，同原容量最⾼位与运算的结果不同。118 if (b !=runBit) {119 //更新runBit，⽤于下⾯判断lastRun该赋值给ln还是hn。120 runBit =b;121 //更新lastRun，保证后⾯的节点与⾃⼰的取于值相同，避免后⾯没有必要的循环。122 lastRun =p;123 }124 }125 //如果最后更新的runBit是0，设置低位节点。126 if (runBit == 0) {127 ln =lastRun;128 hn = null;129 }130 //如果最后更新的runBit是1，设置⾼位节点。131 else{132 hn =lastRun;133 ln = null;134 }135 //再次循环，⽣成两个链表，lastRun作为停⽌条件，这样就是避免⽆谓的循环。136 for (Node p = f; p != lastRun; p =) {137 int ph = ; K pk = ; V pv =;138 //如果与运算结果是0，那么创建低位节点。139 if ((ph & n) == 0)140 ln = new Node(ph, pk, pv, ln);141 //如果与运算结果是1，那么创建⾼位节点。142 else143 hn = new Node(ph, pk, pv, hn);144 }145 //设置低位链表，放在新数组的i位置。146 setTabAt(nextTab, i, ln);147 //设置⾼位链表，放在新数组的i+n位置。148 setTabAt(nextTab, i +n, hn);149 //将旧的链表设置成fwd占位符。150 setTabAt(tab, i, fwd);151 //继续处理区间的下⼀个节点。152 advance = true;153 }154 //如果是红⿊树结构。155 else if (f instanceofTreeBin) {156 TreeBin t = (TreeBin)f;157 TreeNode lo = null, loTail = null;158 TreeNode hi = null,hiTail = null;159 int lc = 0, hc = 0;160 //遍历。161 for (Node e = ; e != null; e =) {162 int h =;163 TreeNode p = new TreeNode(h, , , null,null);164 //与运算结果为0的放在低位。165 if ((h & n) == 0) {166 if (( = loTail) == null)167 lo =p;168 else169 =p;170 loTail =p;171 ++lc;172 }173 //与运算结果为1的放在⾼位。174 else{175 if (( = hiTail) == null)176 hi =p;177 else178 =p;179 hiTail =p;180 ++hc;181 }182 }183 //如果树的节点数⼩于等于6，那么转成链表，反之，创建⼀个新的树。184 ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) : (hc != 0) ? new TreeBin(lo) : t;185 //如果树的节点数⼩于等于6，那么转成链表，反之，创建⼀个新的树。186 hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) : (lc != 0) ? new TreeBin(hi) : t;187 //设置低位树，放在新数组的i位置。188 setTabAt(nextTab, i, ln);189 //设置⾼位数，放在新数组的i+n位置。190 setTabAt(nextTab, i +n, hn);191 //将旧的树设置成fwd占位符。192 setTabAt(tab, i, fwd);193 //继续处理区间的下⼀个节点。194 advance = true;195 }196 }197 }198 }199 }200 }获取⽅法根据指定的键，返回对应的键值对，由于是读操作，所以不涉及到并发问题，步骤如下：1)判断查询的key对应数组的⾸节点是否null。2)先判断数组的⾸节点是否为寻找的对象。3)如果⾸节点不是，并且是红⿊树结构，另做处理。4)如果是链表结构，遍历整个链表查询。5)如果都不是，那就返回null值。1 //获取元素。2 publicV get(Object key) {3 Node[] tab; Node e, p; intn, eh; K ek;4 //计算hash，并保证hash⼀定⼤于零，负数表⽰在扩容或者是树节点。5 int h =spread(de());6 //如果集合不为null，并且集合长度⼤于0，并且指定位置上的元素不为null。7 if ((tab = table) != null && (n = ) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) {8 //如果hash相等。9 if ((eh = ) ==h) {10 //如果⾸节点是要找的元素。11 if ((ek = ) == key || (ek != null &&(ek)))12 ;13 }14 //如果正在扩容或者是树节点。15 else if (eh < 0)16 //尝试查找元素，找到返回元素，找不到返回null。17 return (p = (h, key)) != null ? : null;18 //如果不是⾸节点，则遍历集合查找。19 while ((e = ) != null) {20 if ( == h && ((ek = ) == key || (ek != null &&(ek))))21 ;22}23 }24 return null;25 }删除⽅法删除操作，可以看成是⽤null替代原来的节点，因此合并在这个⽅法中，由这个⽅法⼀起实现删除操作和替换操作。replaceNode()⽅法中的三个参数，key表⽰想要删除的键，value表⽰想要替换的元素，cv表⽰想要删除的key对应的值。1 //删除元素。2 publicV remove(Object key) {3 return replaceNode(key, null, null);4 }56 //删除元素7 finalV replaceNode(Object key, V value, Object cv) {8 //计算hash，并保证hash⼀定⼤于零，负数表⽰在扩容或者是树节点。9 int hash =spread(de());10 //CAS经典写法，不成功⽆限重试。11 for (Node[] tab =table;;) {12 Node f; intn, i, fh;13 //如果集合是null，或者集合长度是0，或者指定位置上的元素是null。14 if (tab == null || (n = ) == 0 || (f = tabAt(tab, i = (n - 1) & hash)) == null)15 //跳出循环。16 break;17 //如果获取到节点不为null，并且节点的hash为-1，则表⽰节点在扩容。18 else if ((fh = ) ==MOVED)19 //帮助扩容。20 tab =helpTransfer(tab, f);21 //产⽣hash碰撞，并且没有扩容操作。22 else{23 V oldVal = null;24 //是否进⼊了同步代码。25 boolean validated = false;26 //锁住节点。27 synchronized(f) {28 //这⾥volatile获取⾸节点与节点对⽐判断节点还是不是⾸节点。29 if (tabAt(tab, i) ==f) {30 //判断是否是链表节点。31 if (fh >= 0) {32 validated = true;33 //循环查找指定元素。34 for (Node e = f, pred = null;;) {35 K ek;36 //找到元素了。37 if ( == hash && ((ek = ) == key || (ek != null &&(ek)))) {38 V ev =;39 //如果cv为null，或者cv不为null时cv和指定元素上的值相同，才更新或者删除节点。40 if (cv == null || cv == ev || (ev != null &&(ev))) {41 oldVal =ev;42 //如果新值不为null，替换。43 if (value != null)44 =value;45 //如果新值是null，并且当前节点⾮⾸结点，删除。46 else if (pred != null)47 =;48 //如果新值是null，并且当前节点是⾸结点，删除。49 else50 setTabAt(tab, i, );51 }52 break;53 }54 pred =e;55 //如果遍历集合也没有找到。56 if ((e = ) == null)57 //跳出循环。58 break;59 }60 }61 //如果是红⿊树节点。62 else if (f instanceofTreeBin) {63 validated = true;64 TreeBin t = (TreeBin)f;65 TreeNoder, p;66 //找到元素了。67 if ((r = ) != null && (p = eeNode(hash, key, null)) != null) {68 V pv =;69 //如果cv为null，或者cv不为null时cv和指定元素上的值相同，才更新或者删除节点。70 if (cv == null || cv == pv || (pv != null &&(pv))) {71 oldVal =pv;72 if (value != null)73 =value;74 elseif(TreeNode(p))75 setTabAt(tab, i, untreeify());76 }77 }78 }79 }80 }81 //如果进⼊了同步代码。82 if(validated) {83 //如果更新或者删除了节点。84 if (oldVal != null) {85 //如果value为null，说明是删除操作。86 if (value == null)87 //将数组长度减⼀。88 addCount(-1L, -1);89 returnoldVal;90 }91 break;92 }93 }94 }95 return null;96 }计算集合容量ConcurrentHashMap中baseCount⽤于保存tab中元素总数，但是并不准确，因为多线程同时增删改，会导致baseCount修改失败，此时会将元素变动存储于counterCells数组内。当需要统计当前的size的时候，除了要统计baseCount之外，还需要加上counterCells中的每个桶的值。值得⼀提的是即使如此，统计出来的依旧不是当前tab中元素的准确值，在多线程环境下统计前后并不能暂停线程操作，因此⽆法保证准确性。1 //计算集合容量。2 public intsize() {3 long n =sumCount();4 return ((n < 0L) ? 0 : (n > (long)_VALUE) ? _VALUE :(int)n);5 }67 //计算集合容量，baseCount和counterCells数组存的总和。8 final longsumCount() {9 CounterCell[] as =counterCells; CounterCell a;10 long sum =baseCount;11 if (as != null) {12 for(int i = 0; i < ; ++i) {13 if ((a = as[i]) != null)14 sum +=;15 }16 }17 returnsum;18 }Hashtable、onizedMap()、ConcurrentHashMap之间的区别Hashtable是线程安全的哈希表，它是通过synchronized来保证线程安全的；即，多线程通过同⼀个“对象的同步锁”来实现并发控制。Hashtable在线程竞争激烈时，效率⽐较低(此时建议使⽤ConcurrentHashMap)。当⼀个线程访问Hashtable的同步⽅法时，其它线程如果也在访问Hashtable的同步⽅法时，可能会进⼊阻塞状态。onizedMap()使⽤了synchronized同步关键字来保证对Map的操作是线程安全的。ConcurrentHashMap是线程安全的哈希表。在JDK1.7中它是通过“锁分段”来保证线程安全的，本质上也是⼀个“可重⼊的互斥锁”(ReentrantLock)。多线程对同⼀个⽚段的访问，是互斥的；但是，对于不同⽚段的访问，却是可以同步进⾏的。在JDK1.8中是通过使⽤CAS原⼦更新、volatile关键字、synchronized可重⼊锁实现的。