由于作者水平有限，如有什么錯誤點，多謝指出，
ConcurrentSkipListMap
/*頭節點 索引節點(最底層保存的是 資料節點 其他層保存的是 索引節點)
* +-+ right +-+ +-+
* |2|---------------->| |--------------------->| |->null
* +-+ +-+ +-+
* | down | |
* v v v
* +-+ +-+ +-+ +-+ +-+ +-+
* |1|----------->| |->| |------>| |----------->| |------>| |->null
* +-+ +-+ +-+ +-+ +-+ +-+
* v | | | | |
* Nodes next v v v v v
* +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
* | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null
*/
public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
implements ConcurrentNavigableMap<K,V>, Cloneable, Serializable {
//鏈表頭部的 特殊值
private static final Object BASE_HEADER = new Object();
// 跳表 最頂層索引
private transient volatile HeadIndex<K,V> head;
// 比較器 K按照什么比較
final Comparator<? super K> comparator;
/** Lazily initialized key set */ //懶加載的 幾個集合
private transient KeySet<K> keySet;
/** Lazily initialized entry set */
private transient EntrySet<K,V> entrySet;
/** Lazily initialized values collection */
private transient Values<V> values;
/** Lazily initialized descending key set */
private transient ConcurrentNavigableMap<K,V> descendingMap;
//保存K-V的節點
static final class Node<K,V> {
final K key;
volatile Object value;
volatile Node<K,V> next;
//創建節點
Node(K key, Object value, Node<K,V> next) {
this.key = key;
this.value = value;
this.next = next;
}
//創建一個新的標記節點， 標記的區別在于它的值欄位指向它自己，
//創建新的標記節點，在洗掉節點時使用，注意這里的節點 k null v 指向它自己
Node(Node<K,V> next) {
this.key = null;
this.value = this;
this.next = next;
}
}
// 跳表的索引節點， 層級結構
static class Index<K,V> {
final Node<K,V> node;
final Index<K,V> down;
volatile Index<K,V> right;
}
//每層 index 索引節點的頭節點
static final class HeadIndex<K,V> extends Index<K,V> {
final int level;
HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {
super(node, down, right);
this.level = level;
}
}
//默認構造
public ConcurrentSkipListMap() {
this.comparator = null;
initialize();
}
}
initialize初始化
private void initialize() {
keySet = null;
entrySet = null;
values = null;
descendingMap = null;
//初始化頭部索引節點
head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),
null, null, 1);
}
put操作
public V put(K key, V value) {
if (value == null)
throw new NullPointerException();
return doPut(key, value, false);
}
private V doPut(K key, V value, boolean onlyIfAbsent) {
Node<K,V> z; // 要添加的節點
if (key == null)
throw new NullPointerException();
Comparator<? super K> cmp = comparator; //比較器
outer: for (;;) {//回圈 直到插入node節點
//找到 k要放的的位置的 前一個和后一個節點 b n
for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
if (n != null) { //b后邊還有節點
Object v; int c;
Node<K,V> f = n.next; //n的下一個節點
if (n != b.next) // n不是 b的下一個節點了 重新開始
break;
if ((v = n.value) == null) { // n 被洗掉了， 幫助洗掉，重試
n.helpDelete(b, f);
break;
}
if (b.value == null || v == n) // b被洗掉了
break;
if ((c = cpr(cmp, key, n.key)) > 0) {//當前k 和 n的k比較， 需不需要更新
b = n;
n = f;
continue;
}
if (c == 0) { //二者相等
//如果onlyIfAbsent 設定為true，不進行舊值替換，否則替換舊值并回傳舊值
if (onlyIfAbsent || n.casValue(v, value)) {
@SuppressWarnings("unchecked") V vv = (V)v;
return vv;
}
break; // 如果 失敗，此時退出當前回圈 重試
}
}
//找到了插入當前的位置
z = new Node<K,V>(key, value, n);
if (!b.casNext(n, z))
break; // CAS將b的next修改為z ，失敗重試
break outer;//退出外回圈 完成插入
}
}
// 插入成功 是否需要更新索引
int rnd = ThreadLocalRandom.nextSecondarySeed(); //當前執行緒獲取一個亂數
if ((rnd & 0x80000001) == 0) { //10000000000000000000000000000001 & 亂數 :最高最低 是不是1
int level = 1, max;
while (((rnd >>>= 1) & 1) != 0)//當前節點應該處于的層級 (亂數右移 & 1)
++level;
Index<K,V> idx = null;
HeadIndex<K,V> h = head; //索引鏈表的頭節點
if (level <= (max = h.level)) { //當前節點的層數 <= 頭節點的層數
for (int i = 1; i <= level; ++i)
idx = new Index<K,V>(z, idx, null);
}
else { // 當前層大于 head 的層
level = max + 1; // 當前level 設定為 原 + 1
//創建層級索引 陣列
@SuppressWarnings("unchecked")Index<K,V>[] idxs =
(Index<K,V>[])new Index<?,?>[level+1];
for (int i = 1; i <= level; ++i)//創建層級索引
idxs[i] = idx = new Index<K,V>(z, idx, null);
for (;;) {// 更新頭節點
h = head; //原頭節點
int oldLevel = h.level;//原 層
if (level <= oldLevel) // 如果已經 小于了 原層，表示其他執行緒更新了 退出
break;
HeadIndex<K,V> newh = h;
Node<K,V> oldbase = h.node; //原頭節點指向的 node
for (int j = oldLevel+1; j <= level; ++j)//創建每一層 索引的頭節點
// 頭節點的 right 節點指向當前 idxs[j] 層數為j
newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j);
if (casHead(h, newh)) {//更新索引節點的 頭節點
h = newh; //h為最新的頭節點
idx = idxs[level = oldLevel]; //當前索引節點為 level 下標處的節點
break;
}
}
}
// 找到插入點并拼接進去
splice: for (int insertionLevel = level;;) {//從最頂層 level開始
int j = h.level; //頭節點的層數
for (Index<K,V> q = h, r = q.right, t = idx;;) {//回圈直到插入成功
if (q == null || t == null)//頭節點或者剛 創建的節點已經被洗掉
break splice;
if (r != null) {//q 是不是最后一個
Node<K,V> n = r.node;
// 比較當前K 和 right索引的 node節點的 V的值
int c = cpr(cmp, key, n.key);
if (n.value == null) {//如果 n的V為空
if (!q.unlink(r))//q的 next指向 r的next 失敗重試 成功 獲取新的 right節點
break;
r = q.right;
continue;
}
if (c > 0) {
q = r; //更新q為右邊索引
r = r.right;//r 更新為原來r 的 right 節點
continue;
}
}
//頭節點的層 等于 待插入的 層
if (j == insertionLevel) {
if (!q.link(r, t))// 節點插入q r 中間
break; // 失敗重試
if (t.node.value == null) {//node 節點被洗掉 呼叫findNode - 洗掉中間被洗掉的節點，然后停止索引節點插入
findNode(key);
break splice;
}
//全部插入完成
if (--insertionLevel == 0)
break splice;
}
//從 索引頭節點往下尋找 找到正確的插入的 層
if (--j >= insertionLevel && j < level)
t = t.down;
q = q.down; //層 下移
r = q.right;//獲取新的 right節點
}
}
}
return null;
}
get方法
首先通過 head索引節點獲取到層級的 頭節點然后 這個節點找到 下一個索引節點 去判斷
public V get(Object key) {
return doGet(key);
}
private V doGet(Object key) {
if (key == null)
throw new NullPointerException();
Comparator<? super K> cmp = comparator;
outer: for (;;) {
//findPredecessor 找到小于給定K 的前一個節點 以及下一個節點 n
for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
Object v; int c;
if (n == null)//b是最后一個節點 退出
break outer;
Node<K,V> f = n.next; //獲取n的下一個節點
if (n != b.next) // b的next發生了改變
break;
if ((v = n.value) == null) { // n洗掉了
n.helpDelete(b, f);
break;
}
if (b.value == null || v == n) // b 洗掉了
break;
if ((c = cpr(cmp, key, n.key)) == 0) {//比較n的k和傳入的k， 如果相同回傳 V值
@SuppressWarnings("unchecked") V vv = (V)v;
return vv;
}
if (c < 0)//表示K 的值小于 n的值，表示鏈表中 不存在
break outer;
b = n;//往后繼續查找
n = f;
}
}
return null;
}
//找到小于給定K的前一個節點
private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) {
if (key == null)
throw new NullPointerException(); // don't postpone errors
for (;;) {
//索引節點的頭節點 和 right 節點
for (Index<K,V> q = head, r = q.right, d;;) {
if (r != null) {//右節點存在
Node<K,V> n = r.node;
K k = n.key;
if (n.value == null) { //n被洗掉了
if (!q.unlink(r)) //嘗試斷開r
break;
r = q.right; // 讀取新的右節點
continue;
}
if (cpr(cmp, key, k) > 0) { // 當前K 大于節點 n的值，根據索引節點往后查找
q = r;
r = r.right;
continue;
}
}
//下一層找，如果是最后溢位 q.node 就是找到的節點
if ((d = q.down) == null)
return q.node;
q = d;// 更新q 下降后的
r = d.right; //右 也更新
}
}
}
remove
public V remove(Object key) {
return doRemove(key, null);
}
final V doRemove(Object key, Object value) {
if (key == null)
throw new NullPointerException();
Comparator<? super K> cmp = comparator;
outer: for (;;) {
//先找到 給定K 的 前面的節點b 和 后面 n
for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
Object v; int c;
if (n == null) //n 不存在
break outer;
Node<K,V> f = n.next; //n的 next f
if (n != b.next) // n 不是 b的next了
break;
if ((v = n.value) == null) { // n被刪
n.helpDelete(b, f);
break;
}
if (b.value == null || v == n) // b 被刪
break;
if ((c = cpr(cmp, key, n.key)) < 0) //如果 n 的K 大于 給定的K，n不是要找的k
break outer;
if (c > 0) {//n的K 小于給定的K， 可能其他執行緒插入了比K小的，往前找，更新 b n
b = n;
n = f;
continue;
}
//如果 value 不為空 和當前n 的value 比較，不等退出
if (value != null && !value.equals(v))
break outer;
if (!n.casValue(v, null)) //n的value 設定為null
break;
if (!n.appendMarker(f) || !b.casNext(n, f))//清除， b的next設定為 f
findNode(key); // 如果其他執行緒完成了 findNode(回傳滿足當前K的節點，并洗掉沿途發現的已經被洗掉的節點)
else {
findPredecessor(key, cmp); // 洗掉成功 findPredecessor(洗掉n的索引節點)
if (head.right == null)
tryReduceLevel();
}
@SuppressWarnings("unchecked") V vv = (V)v;
return vv;
}
}
return null;
}
ConcurrentSkipListSet
就是通過Map 來實作的
public class ConcurrentSkipListSet<E>
extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable {
public ConcurrentSkipListSet() {
m = new ConcurrentSkipListMap<E,Object>();
}
public boolean add(E e) {
return m.putIfAbsent(e, Boolean.TRUE) == null;
}
public boolean remove(Object o) {
return m.remove(o, Boolean.TRUE);
}
public boolean contains(Object o) {
return m.containsKey(o);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/395120.html
標籤：其他