* In addition to using deletion markers, the lists also use * nullness of value fields to indicate deletion, in a style * similar to typical lazy-deletion schemes. If a node's value is * null, then it is considered logically deleted and ignored even * though it is still reachable. This maintains proper control of * concurrent replace vs delete operations -- an attempted replace * must fail if a delete beat it by nulling field, and a delete * must return the last non-null value held in the field. (Note: * Null, rather than some special marker, is used for value fields * here because it just so happens to mesh with the Map API * requirement that method get returns null if there is no * mapping, which allows nodes to remain concurrently readable * even when deleted. Using any other marker value here would be * messy at best.) * n是当前要删除的节点，b是n的前驱节点，f是n的后继节点，开始删除前，(b,n,f)的指向关系如下 * Here's the sequence of events for a deletion of node n with * predecessor b and successor f, initially: * * +------+ +------+ +------+ * ... | b |------>| n |----->| f | ... * +------+ +------+ +------+ * * 1. CAS n's value field from non-null to null. * From this point on, no public operations encountering * the node consider this mapping to exist. However, other * ongoing insertions and deletions might still modify * n's next pointer. * * 1、 将删除节点n的value使用cas设成null，表示此刻起，n节点处于待删除状态，虽然其value为null，对于public相关方法如get等，在执行遇到此类型节点时不会将该节点视为有效节点（也即会被跳过处理），但是如果对于正在执行的插入和删除操作的方法来说，可能也可以去更改“此待删除节点n”的后继节点。 * 2. CAS n's next pointer to point to a new marker node. * From this point on, no other nodes can be appended to n. * which avoids deletion errors in CAS-based linked lists. * * +------+ +------+ +------+ +------+ * ... | b |------>| n |----->|marker|------>| f | ... * +------+ +------+ +------+ +------+ * 2、使用cas将n节点的next字段指向一个marker节点后，从此刻起，任何节点都不会被放在n的后继节点位置，也即不可能出现n->n1、n->n2等，只有n->marker * 3. CAS b's next pointer over both n and its marker. * From this point on, no new traversals will encounter n, * and it can eventually be GCed. * +------+ +------+ * ... | b |----------------------------------->| f | ... * +------+ +------+ * 3、通过cas将b的next指针（越过n节点以及n的后继marker节点）指向f节点，从此刻起，n节点不会被相关操作遍历到，n最终会被GC。
final V doRemove(Object key, Object value){ if (key == null) thrownew NullPointerException(); Comparator<? super K> cmp = comparator; outer: for (;;) { // 1、和doGet、findNode类似设计，首先找到key的前驱节点 for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) { // Object v; int c; if (n == null) break outer; // 经典的(b,n,f)三指针 Node<K,V> f = n.next; // 2、n已不是b的后继节点，也即读n节点前后不一致，则重试 if (n != b.next) // inconsistent read break; // 3、数据节点n节点被标记为删除状态，那么使用helpDelete把n节点删除，然后重试。 if ((v = n.value) == null) { // n is deleted n.helpDelete(b, f); break; } // 4、key的前驱节点b被标记删除状态，只能重试，读取新的b if (b.value == null || v == n) // b is deleted break; //5、 给定的key不在数据链表里面，直接结束 if ((c = cpr(cmp, key, n.key)) < 0) break outer; //6、 给定的key比当前数据节点n还大，那么更新b、n向右继续检索 if (c > 0) { b = n; n = f; continue; } // 以下找到与key相等的n节点 //7、doRemove的入参value默认是null，因此以下会被跳过，若指定value，则还需判断给定的value和当前找到n.value是否相等 if (value != null && !value.equals(v)) break outer; //8、执行流运行到这里，说明满足删除n节点的条件也即key=n.key,n就是要删除的目标数据节点，因此将n.value设为null，cas失败则重试，注意这是是标记删除，不是直接把n节点删除。 if (!n.casValue(v, null)) break; /*9、执行流运行到这里，说明n成功被标记删除状态 条件1：将 b → n → f 变成 b → n → marker → f 条件2：将 b → n → f 变成 b → f 如果条件1CAS失败或者条件2CAS失败，都会调用findNode(key)来删除数据节点n */ if (!n.appendMarker(f) || !b.casNext(n, f)) findNode(key); // retry via findNode else { /*10、不妨假设条件1成立，也即将 b → n → f 变成 b → n → marker → f 需要n节点上方的索引节点都清除（包括清除索引节点的前后指向关系），恰好findPredecessor就是在索引层干这事。 */ findPredecessor(key, cmp); // clean index if (head.right == null) tryReduceLevel(); } @SuppressWarnings("unchecked") V vv = (V)v; return vv; } } returnnull; }
else { /*10、不妨假设条件1成立，也即将 b → n → f 变成 b → n → marker → f 需要n节点上方的索引节点都清除（包括清除索引节点的前后指向关系），恰好findPredecessor就是在索引层干这事。 */ findPredecessor(key, cmp); // clean index if (head.right == null) tryReduceLevel(); }
/** * Helps out a deletion by appending marker or unlinking from * predecessor. This is called during traversals when value * field seen to be null. * @param b predecessor * @param f successor */ // b是n的前驱节点，n是待删除节点，f是n的后继节点 voidhelpDelete(Node<K,V> b, Node<K,V> f){ /* * Rechecking links and then doing only one of the * help-out stages per call tends to minimize CAS * interference among helping threads. */ // 当前线程前后读取的b、n、f保持不变时，就可以实施cas操作 if (f == this.next && this == b.next) { /* 条件1：对于b → n → null这种情况，f=n.next,显然f为null 条件2：对于b → n → f，且f节点不是marker节点，那么给n添加一个marker节点： b → n → marker → f，注意：marker指向f节点指向关系不是因为next指针，而是由marker的value指针指向f完成。 */ if (f == null || f.value != f) // not already marked casNext(f, new Node<K,V>(f)); else /*否则f节点一定是marker节点，且b、n、f以及marker的指向关系如下： b → n → f(marker)→ f.next 变成 b → f.next */ b.casNext(this, f.next); } }
/* * Specialized variant of findNode to get first valid node. * @return first node or null if empty */ final Node<K,V> findFirst(){ for (Node<K,V> b, n;;) { //如上面所解析，如果当前数据层链表仅有一个HeadIndex节点，还没有任何数据节点时，显然只能返回null，这里的b=new Node<K,V>(null, BASE_HEADER, null) if ((n = (b = head.node).next) == null) returnnull; // n作为数据节点第一个头节点没有被标记位删除，那么n节点就是所早的FirstNode if (n.value != null) return n; // 如果发现n已经被标记位删除，那么当前线程就去帮助删除该n节点。 n.helpDelete(b, n.next); } }
* Indexing uses skip list parameters that maintain good search * performance while using sparser-than-usual indices: The * hardwired parameters k=1, p=0.5 (see method doPut) mean * that about one-quarter of the nodes have indices. Of those that * do, half have one level, a quarter have two, and so on (see * Pugh's Skip List Cookbook, sec 3.4). The expected total space * requirement for a map is slightly less than for the current * implementation of java.util.TreeMap.
publicintsize(){ long n = sumCount(); return ((n < 0L) ? 0 : (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)n); }
底层数组最大为$2^{30}$
1 2 3 4 5 6 7 8 9 10
/** * The largest possible table capacity. This value must be * exactly 1<<30 to stay within Java array allocation and indexing * bounds for power of two table sizes, and is further required * because the top two bits of 32bit hash fields are used for * control purposes. */ // top two bits of 32bit hash fields are used for control purposes ，第31和32位被用于相关“控制”，因此底层table的桶位数量最大值为2^30次方 privatestaticfinalint MAXIMUM_CAPACITY = 1 << 30;
