Java（Android）数据结构汇总（四）-- Map（下）
16lz
2021-01-26
传送门：Java（Android）数据结构汇总 -- 总纲
简介
在java.util.concurrent包下实现Map接口的类有两个：ConcurrentHashMap和ConcurrentSkipListMap。下面分别来讲解。
一、ConcurrentHashMap
ConcurrentHashMap是一个线程安全的Map结构。相比Hashtable它有更好的写并发能力，因此官方建议用它来代替Hashtable。
ConcurrentHashMap采用了分段锁的设计（将数据分成多段），只有在同一段中才会有竞争关系（需要上锁），不同段没有竞争关系（不需要上锁），这样在很大程度上降低了阻塞的几率。相比Hashtable的全表加锁，大大提高了并发处理能力。
ConcurrentHashMap内依然和HashMap一样，采用数组+单链表+红黑树来实现的。
在1.8版本中，ConcurrentHashMap的每个数组上的元素使用一个把锁。进一步降低了多线程的冲突几率。
我们一步一步来剖析ConcurrentHashMap，先来看看它的定义：
public class ConcurrentHashMap extends AbstractMap implements ConcurrentMap, Serializable { // 内部的数组，大小为2的冥 transient volatile Node[] table; // 扩容时新建的数组 // 扩容的时候会新建一个是当前容量两倍大小的数组nextTable， // 然后将table中的元素重新分布到这个新数组中， // 最后再将table指向这个新数组，并释放nextTable引用（置为null） private transient volatile Node[] nextTable; // 当前键值对总数 private transient volatile long baseCount; // 控制标志符 // -1：表示正在初始化； // -N：表示有N-1个线程正在执行扩容操作； // 0：表示需要初始化； // >0：表示扩容的阈值（即当前容量 * 加载因子），当实际使用量超过该值时就会进行扩容操作 private transient volatile int sizeCtl; // 扩容时用，标记最新移动元素的位置，扩容时会将table中的元素从后往前一次处理并移动到新数组中， // 比如线程A处理table数组上的元素的范围是64-56，那么它会将transferIndex设置为56， // 这样下一个线程就会从56开始处理元素，因为处理范围都是相同的，所以这个线程处理的范围就是56-48， // 同时它会将transferIndex更新为48，以后后来的线程可以从48开始处理 private transient volatile int transferIndex; ...} 然后再来看几个它的内部类：
// 链表节点，每个Node存储一个键值对static class Node implements Map.Entry { final int hash; // key的hash值 final K key; // key volatile V val; // value volatile Node next; // 下一个节点 ...}// 红黑树的节点static final class TreeNode extends Node { TreeNode parent; // red-black tree links TreeNode left; TreeNode right; TreeNode prev; // needed to unlink next upon deletion boolean red;}// 用来维护红黑树，提供了红黑树的相关操作，// 当将链表转换为红黑树后，table上不直接存放TreeNode，而是存放一个对整颗红黑树进行了封装的TreeBin对象static final class TreeBin extends Node { ...}// 在扩容期间用，当table数组上某个位置呗处理后，会将其设置为ForwardingNode，表示该位置已处理static final class ForwardingNode extends Node { ...} 构造方法：
public ConcurrentHashMap() {}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;}public ConcurrentHashMap(Map<? extends K, ? extends V> m) { this.sizeCtl = DEFAULT_CAPACITY; //16 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(); // concurrencyLevel表示同时更新ConcurrentHashMap时不会产生锁竞争关系的最大线程数。 // 这个是是为了兼容老版本而保留的，这里的作用只是保证初始容量不小于这个值 if (initialCapacity < concurrencyLevel) // Use at least as many bins initialCapacity = concurrencyLevel; // as estimated threads // 同样，自定义的加载因子也会影响初始容量，以后扩容都是使用的0.75 long size = (long)(1.0 + (long)initialCapacity / loadFactor); int cap = (size >= (long)MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : tableSizeFor((int)size); this.sizeCtl = cap;}接着再来看一下它的具体操作，我们还是从put()开始：
public V put(K key, V value) { return putVal(key, value, false);}final V putVal(K key, V value, boolean onlyIfAbsent) { // 键和值都不能为null if (key == null || value == null) throw new NullPointerException(); // 计算key的hash值 int hash = spread(key.hashCode()); int binCount = 0; // 使用CAS机制进行尝试更新tab，如果失败（有其他线程在操作）则不断重试，直到成功 for (Node[] tab = table;;) { Node f; int n, i, fh; // 如果当前table还没有初始化则进行table初始化 if (tab == null || (n = tab.length) == 0) tab = initTable(); // (n - 1) & hash的作用就是将hash映射到数组上，原理在讲HashMap的时候就说过了 // i就是该hash值在数组上的索引 // tabAt就是利用CAS机制取出tab上i位置的元素，并赋值给f // // f的值有三种： // null：该位置还没有放入元素，则将当前的key-value封装成一个Node对象放在该位置； // 如果该位置的hash值为MOVED，表示正在扩容中，则进入下次循环重试； // 如果该位置的hash值为TREEBIN，表示该值是一个TreeBin对象（红黑树），则按照红黑树的方式插入新的元素； // else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // casTabAt利用CAS机制进行原子性的将新建的节点存放到tab的i位置 // 如果在存放的过程中i位置的值发生了变化（不再是null），则返回false，否则返回true // 如果发生了变化是因为有其他线程在这个时候修改了i位置的值 // 当失败了就进入下次循环重试 if (casTabAt(tab, i, null, new Node(hash, key, value, null))) break; // no lock when adding to empty bin } // 如果该节点的hash值为MOVED则表示正在扩容 else if ((fh = f.hash) == MOVED) // 帮助扩容，并返回扩容后的新tab，然后进入下次循环重试 tab = helpTransfer(tab, f); else { V oldVal = null; // 对该位置上的链表或红黑树进行加锁同步 // 这里可以看出，table上每个位置都是一把单独的锁， // 也就是只有多个线程同时操作同一个位置时才能产生竞争关系， // 而操作不同位置时不会产生竞争关系，这就是比HashTable高效的原因所在 synchronized (f) { // 验证该节点是否被其他线程修改过， // 如果没有修改（tab的i位置的值还是f）才进行相关操作，否则直接进入下次循环重试 if (tabAt(tab, i) == f) { // 如果该节点的hash值不小于0表示是一个链表（否则可能是红黑树或其他） if (fh >= 0) { binCount = 1; // 执行链表操作，将新的节点插入到链表中 for (Node e = f;; ++binCount) { K ek; // 判断如果有相同key，则替换旧值 if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node pred = e; // 如果当前已经是链表的最后一个节点，则将新的节点插入到这个链接的结尾 if ((e = e.next) == null) { pred.next = new Node(hash, key, value, null); break; } } } // 如果当前是一颗红黑树，则进行红黑树的插入操作 else if (f instanceof TreeBin) { Node p; binCount = 2; // TreeBin对象在管理这颗红黑树 // 将要插入的值使用putTreeVal方法插入到红黑树中，返回值p表示和该key相同的节点 // 如果p为null表示没有和当前key相同的节点，则本次是新增了一个节点， // 否则表示有和当前key相同的节点，则直接返回该节点 if ((p = ((TreeBin)f).putTreeVal(hash, key, value)) != null) { // 获取该节点上的旧值，并将旧值替换为新的值 oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } else if (f instanceof ReservationNode) throw new IllegalStateException("Recursive update"); } } // binCount不为0表示本次添加成功 if (binCount != 0) { // 当是链表的时候，binCount表示链表上的节点数量 // 如果链表的节点数量达到了链表转红黑树的阈值时，则将链表转换为红黑树 if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); // 如果有旧值，则返回旧值 // 注意此处没有更新baseCount（下面的addCount用来更新baseCount）， // 因为有旧值，说明是替换而不是新增那么键值对的数量（baseCount）没有发生变化 if (oldVal != null) return oldVal; break; } } } // 更新baseCount（baseCount是当前键值对的数量） addCount(1L, binCount); return null;}// 数组初始化方法private final Node[] initTable() { Node[] tab; int sc; // 这里也是采用CAS机制，如果操作失败就不断重试，直到成功 while ((tab = table) == null || tab.length == 0) { // 如果sizeCtl小于0表示有其他线程正在进行初始化操作或扩容操作 if ((sc = sizeCtl) < 0) // yield的作用是让出自己的CPU执行时间，并且让自己和其他线程再来一起竞争这段CPU执行时间。 // 这样就会在保证自己不会阻塞挂起的同时，尽量让其他线程先执行（等待他们初始化或扩容结束） Thread.yield(); // lost initialization race; just spin // 以CAS机制原子性的修改sizeCtl的值为-1。 // 这样保证同一时刻只会有一个线程修改成功，如果有其他线程则会执行上面的Thread.yield() else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { try { // 再次验证是否需要初始化 if ((tab = table) == null || tab.length == 0) { // 构造方法里如果初始化了sizeCtl，则sc大于0，否则sc就是默认值0 // 如果初始化了sizeCtl则容量就用初始化值，否则用默认值 int n = (sc > 0) ? sc : DEFAULT_CAPACITY; @SuppressWarnings("unchecked") Node[] nt = (Node[])new Node<?,?>[n]; table = tab = nt; // 因为加载因子是0.75，所以这里将sc设置为当前容量的3/4（ n - (n >>> 2)等价于 n*3/4） sc = n - (n >>> 2); } } finally { // 将sc的值重新赋值给sizeCtl，表示以后当使用量超过当前容量的3/4就进行扩容 sizeCtl = sc; } break; } } return tab;}// 链表转红黑树private final void treeifyBin(Node[] tab, int index) { Node b; int n; if (tab != null) { // 如果tab长度不足MIN_TREEIFY_CAPACITY（64），则对table进行扩容，而不将链表转换为红黑树 if ((n = tab.length) < MIN_TREEIFY_CAPACITY) tryPresize(n << 1); // 验证该位置的存储的元素不为空，且不处于扩容过程中时才进行转换， // 否则就放弃本次转换，而是等到下次put新元素的时候再进行转换 else if ((b = tabAt(tab, index)) != null && b.hash >= 0) { // 先锁住该链表 synchronized (b) { // 再次判断是否被修改了 if (tabAt(tab, index) == b) { TreeNode hd = null, tl = null; // 将链表的Node类型的节点转换成TreeNode，然后用TreeNode创建一个TreeBin for (Node e = b; e != null; e = e.next) { TreeNode p = new TreeNode(e.hash, e.key, e.val, null, null); if ((p.prev = tl) == null) hd = p; else tl.next = p; tl = p; } // 将这个新建的TreeBin对象放到table的i位置 setTabAt(tab, index, new TreeBin(hd)); } } } }}// 扩容检查，满足条件才进行扩容private final void tryPresize(int size) { // 保证扩大的容量是2的冥 int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : tableSizeFor(size + (size >>> 1) + 1); int sc; // 判断控制标志符sizeCtl，只有当sizeCtl不小于0的时候才进行扩容（小于0表示当前正在进行初始化或扩容） while ((sc = sizeCtl) >= 0) { Node[] tab = table; int n; // 如果当前table为空，表示还没有初始化，则进行初始化操作 if (tab == null || (n = tab.length) == 0) { n = (sc > c) ? sc : c; // 只有成功将sizeCtl设置为-1（-1表示正在进行初始化）才进行初始化操作 if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { try { // 检查table是否被修改过，如果在这期间有其他线程修改了table则放弃本次的初始化操作 if (table == tab) { // 创建table @SuppressWarnings("unchecked") Node[] nt = (Node[])new Node<?,?>[n]; table = nt; // 设置sc的值为n的3/4（n - (n >>> 2)等价于 n * 3/4） sc = n - (n >>> 2); } } finally { // 将sizeCtl的值设置为当前容量的3/4，表示当容量的使用量超过3/4时就进行扩容 sizeCtl = sc; } } } // 如果需要扩容的容量小于当前table的容量，说明已经有其他线程完成了扩容操作，则直接退出， // 或者当前已经达到了最大容量，也放弃本次扩容 else if (c <= sc || n >= MAXIMUM_CAPACITY) break; // 再次检查，当table没有被改变时才进行扩容，否则进入下次循环重试 else if (tab == table) { int rs = resizeStamp(n); if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)) transfer(tab, null); } }}// 扩容private final void transfer(Node[] tab, Node[] nextTab) { int n = tab.length, stride; // 因为可能同时存在多个线程进行扩容操作，所以这里对tab上的元素进行了分段， // 每个线程处理一段数据（stride表示每段的长度），处理完了再处理下一段。 // 例如：tab长度为64，stride为8，有A、B、C三个线程，那么： // 线程A处理tab上0-7这八个位置的数据； // 线程B处理8-15这八个位置的数据； // 线程c处理16-23这八个位置的数据； // 如果此时线程B处理完了，则接着继续处理24-31这八个位置的数据； // 依次类推...（下面处理实际是从后面往前面处理的） // 这里stride的值是依据当前CPU数量来设定的，以保证达到一个最优处理范围 if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE) stride = MIN_TRANSFER_STRIDE; // subdivide range // 扩容的时候会将table中的元素放到新建的两倍容量数组nextTab上， // 移动完了再将table重新指向nextTab，从而实现扩容。 // 如果nextTab为null，表示当前线程是处理本次扩容的第一个线程，则新建nextTab数组，大小为table的两倍 if (nextTab == null) { // initiating try { // 构造一个大小是当前容量两倍的nextTable对象 @SuppressWarnings("unchecked") Node[] nt = (Node[])new Node<?,?>[n << 1]; nextTab = nt; } catch (Throwable ex) { // try to cope with OOME sizeCtl = Integer.MAX_VALUE; return; } nextTable = nextTab; // transferIndex表示当前处理的位置，这里直接赋值n也说明了是从后往前处理 // 注意这里直接赋值的是n，所以transferIndex表示的是长度，而不是数组的下标 transferIndex = n; } // 下面就开始移动table中的元素到nextTable中 // 新数组（nextTab）的长度 int nextn = nextTab.length; // 创建一个特殊的元素，躺table中某位置的元素被成功处理后，就将该位置的值设置为fwd，表示这个位置的元素已经被处理 ForwardingNode fwd = new ForwardingNode(nextTab); // advance为true表示该位置的元素需要处理，否则表示该位置的元素不需要处理 boolean advance = true; // 是否所有线程都完成了扩容操作 boolean finishing = false; // to ensure sweep before committing nextTab // i表示当前处理的位置，bound表示处理的最小位置 // 比如需要处理table上索引为64-32这个区间的数据（从后往前处理）， // 那么开始时i等于63（i是数组索引，需要减1），且i逐渐减小到32（bound） for (int i = 0, bound = 0;;) { Node f; int fh; // while的作用就是确定bound的值和找出这个区间里需要处理的位置（i） while (advance) { int nextIndex, nextBound; // i是上一次处理的位置，--i表示当前需要处理的位置 // 如果--i还不小于bound，说明这个位置还是由该线程来处理，则将advance设置为fale跳出while循环， // 如果finishing为true表示所有线程都已经处理完扩容操作了，也将advance设置为true跳出while循环 if (--i >= bound || finishing) advance = false; // transferIndex表示当前最新一个线程的处理位置 // 比如线程A处理的范围是64-32，那么transferIndex就是32， // 下一个线程就该从32位置开始处理 // 注意这里的范围取值（transferIndex）是1到table.lenght，而不是数组下标0到table.lenght-1 // 所以这里当transferIndex==0时就没有可处理的元素的 else if ((nextIndex = transferIndex) <= 0) { // 将i赋值为-1，表示已经处理完了 i = -1; advance = false; } // 设置处理范围 // 原子性的修改transferIndex的值为nextIndex - stride（或0）， // 即将transferIndex修改为当前处理范围的最小值，以便下一个线程好从这个位置开始往前处理 else if (U.compareAndSwapInt(this, TRANSFERINDEX, nextIndex, nextBound = (nextIndex > stride ? nextIndex - stride : 0))) { // bound为本次处理范围的最小值 bound = nextBound; // 将i设置为开始处理的位置，因为nextIndex不是数组下标，所以要减1 i = nextIndex - 1; // 将advance设置为false，表示当前i位置的元素需要处理，同时用于跳出while循环 advance = false; } } // 检查是否全部处理完成 if (i < 0 || i >= n || i + n >= nextn) { int sc; // 如果finishing为true，表示所有线程都已经处理完扩容操作了， // 则释放nextTable引用，并将table指向新建的nextTab对象 if (finishing) { nextTable = null; table = nextTab; // 重新设置扩容的阈值，因为新的容量是2*n，所以新的阈值应该是2*n*0.75，也就是1.5n // (n << 1) - (n >>> 1) // = (n * 2) - (n / 2) // = 1.5 * n return; } // 如果finishing不为true，表示只是当前线程处理完了扩容操作，则将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 } } // 下面都是处理元素的过程 // 如果i位置的元素为null（这个位置没有插入过元素）， // 则将该位置设置为fwd对象，表示该位置处理完成 else if ((f = tabAt(tab, i)) == null) // 将advance设置true，进入while循环处理下一个位置（--i） advance = casTabAt(tab, i, null, fwd); // 如果当前位置的元素的hash值是MOVED（也就是该元素是fwd）， // 表示该元素已经处理过了，则直接将advance设置true，下次循环好处理下一个位置 else if ((fh = f.hash) == MOVED) advance = true; // already processed else { // 防止在扩容的时候有put在操作该位置，所以需要加锁 synchronized (f) { // 加锁完成后再次判断该位置是否有变化，没有才进行元素移动 if (tabAt(tab, i) == f) { Node ln, hn; // 该位置的hash值不小于0说明该位置是一个链表 if (fh >= 0) { // 因为该链表下所有节点的hash值和当前数组长度取模的值是一样的， // 那么在长度翻倍的新数组里，取模的结果，只会有两个值， // 比如有一组数对8取模的结果都是5，那么他们对16取模的结果只会是5或13（5+8） //所以当前链表中的节点分配到新数组上后，也只会在两个位置：i或i+n // 这里的逻辑将是将当前链表分成两个链表， // 然后将这两个链表直接放到新数组的i和i+n两个位置上 int runBit = fh & n; Node lastRun = f; for (Node 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 (Node 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 Node(ph, pk, pv, ln); else hn = new Node(ph, pk, pv, hn); } setTabAt(nextTab, i, ln); setTabAt(nextTab, i + n, hn); setTabAt(tab, i, fwd); advance = true; } // 该位置的元素是红黑树 // 按照上面的逻辑，将红黑树才分为两个链表，分别放到新数组的i和i+n位置上 else if (f instanceof TreeBin) { TreeBin t = (TreeBin)f; TreeNode lo = null, loTail = null; TreeNode hi = null, hiTail = null; int lc = 0, hc = 0; for (Node e = t.first; e != null; e = e.next) { int h = e.hash; TreeNode p = new TreeNode (h, e.key, e.val, null, null); if ((h & n) == 0) { if ((p.prev = loTail) == null) lo = p; else loTail.next = p; loTail = p; ++lc; } else { if ((p.prev = hiTail) == null) hi = p; else hiTail.next = p; hiTail = p; ++hc; } } ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) : (hc != 0) ? new TreeBin(lo) : t; hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) : (lc != 0) ? new TreeBin(hi) : t; setTabAt(nextTab, i, ln); setTabAt(nextTab, i + n, hn); setTabAt(tab, i, fwd); advance = true; } } } } }} 可见，ConcurrentHashMap引入了分段锁和CAS机制，使得它比HashTable更加的高效。
二、ConcurrentSkipListMap
从功能上来说，ConcurrentSkipListMap是TreeMap的一个线程安全版本。主要功能同样是对键值对进行排序，它使用跳表来对内部的有序链表进行了优化，提高了操作速度。
跳表：使用“空间换时间”思想，每个节点除了指向后一个节点的next指针外，还存在其他指向后面其他节点的指针，在查找的时候我们就不用像普通链表那样挨着一个一个往后查找，而是可以跳跃式的往后查找。为了实现这种结构，跳表分为多级，结构如下： skipList_1.png
上图就是一张跳表的基本结构，其特点有：
1，由多层构成（比如这里有三层），level是通过一定的概率随机产生；
2，每一层都是一个有序链表；
3，最底层（Level 1）链表包含所有元素，也是我们的基础链表；
4，第i层的元素必然包含在第i-1层中；
5，每个链表的节点有包含两个指针，一个和普通链表一样指向下一个节点，另一个指向下层链表的相同节点；可以看出，第一层是我们的基础链表，包含所有元素。从第二层开始，每层的元素都是前一层元素的子集（比如第二层的元素是第一层元素的子集）。每个节点除了指向下一个节点的指针外还有一个指向前一层相同节点的指针。
跳表的操作都是从最上层开始，比如我们在上面的跳表中插入一个元素45，插入过程为：
- 在level3中判断：45比第一个节点（10）大，但是比第二个节点（66）小，那么从前一个节点位置降层，也就是到level2的10这个节点上；
- 在level2中判断：45比下一个节点（35）大，继续比较下一个节点（66），发现比66小，那么从前一个节点（35）位置降层，也就是到level1的35这个节点上；
- 在level1中判断：45比下一个节点（50）小，那么就将45插入到35和50之间。结果如下： skipList_2.png
跳表的性能和红黑树及AVL数性能相当，但是比它们简单。
我们明白了跳表的原理后，ConcurrentSkipListMap就比较简单了。还是以put为入口来看看源码：
public V put(K key, V value) { // 注意这里，value是不能为null的 if (value == null) throw new NullPointerException(); return doPut(key, value, false);}private V doPut(K key, V value, boolean onlyIfAbsent) { Node z; // added node // 再注意这里，key也是不能为null的 // 也就是说ConcurrentSkipListMap的key和value都不能为null if (key == null) throw new NullPointerException(); Comparator<? super K> cmp = comparator; outer: for (;;) { // 查找当前key应该插入的前节点或应该替换的节点 for (Node b = findPredecessor(key, cmp), n = b.next;;) { // 如果n不为null表示查找到的位置在链表中间 if (n != null) { Object v; int c; Node f = n.next; // 检查b的下一个节点还是否是n，如果不是则说明有其他线程修改了该节点，则重试 if (n != b.next) // inconsistent read break; // 如果该节点的value值为null，则将该节点删除 if ((v = n.value) == null) { // n is deleted n.helpDelete(b, f); break; } // 如果b的value为null，说明b已经被删除了，则重试 if (b.value == null || v == n) // b is deleted break; // 如果key比n节点的key大，则继续比较n的下一个节点 if ((c = cpr(cmp, key, n.key)) > 0) { b = n; n = f; continue; } // 如果key和n节点的key相等，则替换n节点中的value值 if (c == 0) { if (onlyIfAbsent || n.casValue(v, value)) { @SuppressWarnings("unchecked") V vv = (V)v; return vv; } break; // restart if lost race to replace value } // else c < 0; fall through } // 执行到这里有两种情况： // 一是b是链表的最后一个节点（b.next == null）； // 二是key比b节点的key值大，但是比b.next节点的key值小； // 这两种情况下，将新的key-value插入到b节点后面 z = new Node(key, value, n); if (!b.casNext(n, z)) break; // restart if lost race to append to b break outer; } } // 下面是重构跳表的层级关系 // ThreadLocalRandom是Random的一个线程安全版本，也是用来生成随机数 int rnd = ThreadLocalRandom.nextSecondarySeed(); // 将0x80000001转换成32位的二进制时是：1000...0001，最高位和最低位是1， // 最高位是1表示是一个负数，最低位是1表示是一个奇数， // 这里(rnd & 0x80000001) == 0表示最高位和最低位都不能是1，也就是说这个随机数必须是一个正偶数， // 当随机数是一个正偶数的时候就进行重新构建跳表层级关系。 if ((rnd & 0x80000001) == 0) { // test highest and lowest bits int level = 1, max; // 第一步：用新增的这个节点生成指定层数的链表（这个是从上往下的链表）。 // 判断从右到左有多少个连续的1，将连续1的数量加上基础层作为跳表的层数 while (((rnd >>>= 1) & 1) != 0) ++level; Index idx = null; HeadIndex h = head; // 第二步：创建层级基础框架（每层（基础层除外）只包含头节点） if (level <= (max = h.level)) { // 如果新的层数不大于当前层数 // // 创建链表，用来添加跳表结构中 for (int i = 1; i <= level; ++i) idx = new Index(z, idx, null); } else { // try to grow by one level // 如果新的层数大于当前层数，则新的层数在当前层数上增加一层， // 此时实际上只新增了一层 level = max + 1; // hold in array and later pick the one to use // 创建一个idxs数组用来保存每层要新增的节点,idxs [0]没有使用 @SuppressWarnings("unchecked")Index[] idxs = (Index[])new Index<?,?>[level+1]; // 创建层级基础框架（每层（基础层除外）只包含头节点 for (int i = 1; i <= level; ++i) idxs[i] = idx = new Index(z, idx, null); // 创建新层头结点HeadIndex for (;;) { h = head; int oldLevel = h.level; // 如果层级关系被其他线程修改过，则放弃 if (level <= oldLevel) // lost race to add level break; HeadIndex newh = h; Node oldbase = h.node; // 为新增的层创建HeadIndex对象用来作为头节点，同时将这个新增的层和以前的的层关联， // HeadIndex的第二个参数down指向的是以前的head， // 因为只新增了一层，所以这里只会进行一次循环 // 完成后newh表示最高层的head节点 for (int j = oldLevel+1; j <= level; ++j) newh = new HeadIndex(oldbase, newh, idxs[j], j); // 将newh和head交换 if (casHead(h, newh)) { h = newh; idx = idxs[level = oldLevel]; break; } } } // 将新增的节点添加到各层中 // find insertion points and splice in splice: for (int insertionLevel = level;;) { int j = h.level; for (Index q = h, r = q.right, t = idx;;) { // 如果已经到了最底层则退出循环 if (q == null || t == null) break splice; // 在该层链表上查找可以插入key的位置 if (r != null) { Node n = r.node; // compare before deletion check avoids needing recheck int c = cpr(cmp, key, n.key); if (n.value == null) { if (!q.unlink(r)) break; r = q.right; continue; } if (c > 0) { q = r; r = r.right; continue; } } if (j == insertionLevel) { if (!q.link(r, t)) break; // restart if (t.node.value == null) { findNode(key); break splice; } if (--insertionLevel == 0) break splice; } if (--j >= insertionLevel && j < level) t = t.down; q = q.down; r = q.right; } } } return null;}private Node findPredecessor(Object key, Comparator<? super K> cmp) { if (key == null) throw new NullPointerException(); // don't postpone errors for (;;) { // 查找的逻辑就是：从最顶层最左边（该层链表表头）开始往右往下查找： // 如果key比当前节点的key大，则往右查找； // 如果key不大于当前节点，则从前一个节点往下查找； // // head是最顶层级的头节点 for (Index q = head, r = q.right, d;;) { // 如果该节点（q）的右侧还有节点（r） if (r != null) { // 每个节点的数据都是放在一个Node对象里面的 Node n = r.node; K k = n.key; // 如果该节点的value为null，则将该节点从该层中移除，并继续查找该层下一个节点 if (n.value == null) { if (!q.unlink(r)) // 如果移除失败则进入下次循环重试 break; // restart r = q.right; // reread r continue; } // 比较key，如果要插入的key比当前的key值大，则继续向右查找下一个节点 if (cpr(cmp, key, k) > 0) { q = r; r = r.right; continue; } } // 降到下一层，如果没有下一层了则返回当前层的这个最后的节点 // 降到下一层有两种情况： // 一是本层查找完了（上面的r等于null表示当前p已经是本层的最后一个节点了）； // 二是找到了不小于当前key的节点（r），则从前一个节点（q）降级到下一层； if ((d = q.down) == null) return q.node; // 指向下一层的下一个节点 q = d; r = d.right; } }} 当成功将一个节点插入到基础层上后，再用一个随机值来判断要不要将该节点添加到其他层上以及要不要增加层。
while (((rnd >>>= 1) & 1) != 0) ++level;这里最终的level值旧是要将该节点添加到的层数，比如3就表示将新的节点添加到前3层（包括基础层），如果这个值比当前层数大，则会新增一层。
举个例子来说明。比如下图，我们成功将45这个节点添加到了基础层上（添加的过程很简单，前面在介绍跳表的时候已经讲过添加步骤了）： skipList_3.png如果这个时候rnd & 0x80000001) == 0条件成立，我们就需要将45这个节点添加到其他层去。这个时候level计算出的值有两种情况，如果大于4（当前层数）比如7，或则不大于4，比如3。
先来说不大于当前层数的处理。因为当前level值是3，所以只会将45这个节点添加到前3层，因此会先创建一个从上往下的链表，又因为基础层不需要再添加了，所以链表节点只有两个：
skipList_4.png
上面过程对应的代码为：
if (level <= (max = h.level)) { for (int i = 1; i <= level; ++i) idx = new Index(z, idx, null);} 对应的代码为：
// 创建要添加到层的节点for (int i = 1; i <= level; ++i) idxs[i] = idx = new Index(z, idx, null); // 创建新层的头节点，因为每次只会新增一层，所以这里的for循环实际上只会执行一次for (int j = oldLevel+1; j <= level; ++j) newh = new HeadIndex(oldbase, newh, idxs[j], j); ConcurrentSkipListMap的基本操作主要就这些。
总结
ConcurrentHashMap是HashMap的多线程实现，比Hashtable性能更好。ConcurrentSkipListMap则是TreeMap的多线程实现。
更多相关文章
- Android输出log的包装
- android瀑布流，完美解决滑动过程中item位置错乱，下拉刷新顶部空白，
- Android自定义控件实战——滚动选择器PickerView
- android popupwindow 模拟新浪、腾讯title弹框效果
- Android(安卓)N进入分屏代码分析二
- Android获取当前位置,location为空
- Error parsing XML: junk after document element
- 获取高德key
- android xml解析之pull解析