Java concurrency集合之ConcurrentSkipListMap_動(dòng)力節(jié)點(diǎn)Java學(xué)院整理

// 構(gòu)造一個(gè)新的空映射，該映射按照鍵的自然順序進(jìn)行排序。
ConcurrentSkipListMap()
// 構(gòu)造一個(gè)新的空映射，該映射按照指定的比較器進(jìn)行排序。
ConcurrentSkipListMap(Comparator<? super K> comparator)
// 構(gòu)造一個(gè)新映射，該映射所包含的映射關(guān)系與給定映射包含的映射關(guān)系相同，并按照鍵的自然順序進(jìn)行排序。
ConcurrentSkipListMap(Map<? extends K,? extends V> m)
// 構(gòu)造一個(gè)新映射，該映射所包含的映射關(guān)系與指定的有序映射包含的映射關(guān)系相同，使用的順序也相同。
ConcurrentSkipListMap(SortedMap<K,? extends V> m)

// 返回與大于等于給定鍵的最小鍵關(guān)聯(lián)的鍵-值映射關(guān)系；如果不存在這樣的條目，則返回 null。
Map.Entry<K,V> ceilingEntry(K key)
// 返回大于等于給定鍵的最小鍵；如果不存在這樣的鍵，則返回 null。
K ceilingKey(K key)
// 從此映射中移除所有映射關(guān)系。
void clear()
// 返回此 ConcurrentSkipListMap 實(shí)例的淺表副本。
ConcurrentSkipListMap<K,V> clone()
// 返回對(duì)此映射中的鍵進(jìn)行排序的比較器；如果此映射使用鍵的自然順序，則返回 null。
Comparator<? super K> comparator()
// 如果此映射包含指定鍵的映射關(guān)系，則返回 true。
boolean containsKey(Object key)
// 如果此映射為指定值映射一個(gè)或多個(gè)鍵，則返回 true。
boolean containsValue(Object value)
// 返回此映射中所包含鍵的逆序 NavigableSet 視圖。
NavigableSet<K> descendingKeySet()
// 返回此映射中所包含映射關(guān)系的逆序視圖。
ConcurrentNavigableMap<K,V> descendingMap()
// 返回此映射中所包含的映射關(guān)系的 Set 視圖。
Set<Map.Entry<K,V>> entrySet()
// 比較指定對(duì)象與此映射的相等性。
boolean equals(Object o)
// 返回與此映射中的最小鍵關(guān)聯(lián)的鍵-值映射關(guān)系；如果該映射為空，則返回 null。
Map.Entry<K,V> firstEntry()
// 返回此映射中當(dāng)前第一個(gè)（最低）鍵。
K firstKey()
// 返回與小于等于給定鍵的最大鍵關(guān)聯(lián)的鍵-值映射關(guān)系；如果不存在這樣的鍵，則返回 null。
Map.Entry<K,V> floorEntry(K key)
// 返回小于等于給定鍵的最大鍵；如果不存在這樣的鍵，則返回 null。
K floorKey(K key)
// 返回指定鍵所映射到的值；如果此映射不包含該鍵的映射關(guān)系，則返回 null。
V get(Object key)
// 返回此映射的部分視圖，其鍵值嚴(yán)格小于 toKey。
ConcurrentNavigableMap<K,V> headMap(K toKey)
// 返回此映射的部分視圖，其鍵小于（或等于，如果 inclusive 為 true）toKey。
ConcurrentNavigableMap<K,V> headMap(K toKey, boolean inclusive)
// 返回與嚴(yán)格大于給定鍵的最小鍵關(guān)聯(lián)的鍵-值映射關(guān)系；如果不存在這樣的鍵，則返回 null。
Map.Entry<K,V> higherEntry(K key)
// 返回嚴(yán)格大于給定鍵的最小鍵；如果不存在這樣的鍵，則返回 null。
K higherKey(K key)
// 如果此映射未包含鍵-值映射關(guān)系，則返回 true。
boolean isEmpty()
// 返回此映射中所包含鍵的 NavigableSet 視圖。
NavigableSet<K> keySet()
// 返回與此映射中的最大鍵關(guān)聯(lián)的鍵-值映射關(guān)系；如果該映射為空，則返回 null。
Map.Entry<K,V> lastEntry()
// 返回映射中當(dāng)前最后一個(gè)（最高）鍵。
K lastKey()
// 返回與嚴(yán)格小于給定鍵的最大鍵關(guān)聯(lián)的鍵-值映射關(guān)系；如果不存在這樣的鍵，則返回 null。
Map.Entry<K,V> lowerEntry(K key)
// 返回嚴(yán)格小于給定鍵的最大鍵；如果不存在這樣的鍵，則返回 null。
K lowerKey(K key)
// 返回此映射中所包含鍵的 NavigableSet 視圖。
NavigableSet<K> navigableKeySet()
// 移除并返回與此映射中的最小鍵關(guān)聯(lián)的鍵-值映射關(guān)系；如果該映射為空，則返回 null。
Map.Entry<K,V> pollFirstEntry()
// 移除并返回與此映射中的最大鍵關(guān)聯(lián)的鍵-值映射關(guān)系；如果該映射為空，則返回 null。
Map.Entry<K,V> pollLastEntry()
// 將指定值與此映射中的指定鍵關(guān)聯(lián)。
V put(K key, V value)
// 如果指定鍵已經(jīng)不再與某個(gè)值相關(guān)聯(lián)，則將它與給定值關(guān)聯(lián)。
V putIfAbsent(K key, V value)
// 從此映射中移除指定鍵的映射關(guān)系（如果存在）。
V remove(Object key)
// 只有目前將鍵的條目映射到給定值時(shí)，才移除該鍵的條目。
boolean remove(Object key, Object value)
// 只有目前將鍵的條目映射到某一值時(shí)，才替換該鍵的條目。
V replace(K key, V value)
// 只有目前將鍵的條目映射到給定值時(shí)，才替換該鍵的條目。
boolean replace(K key, V oldValue, V newValue)
// 返回此映射中的鍵-值映射關(guān)系數(shù)。
int size()
// 返回此映射的部分視圖，其鍵的范圍從 fromKey 到 toKey。
ConcurrentNavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
// 返回此映射的部分視圖，其鍵值的范圍從 fromKey（包括）到 toKey（不包括）。
ConcurrentNavigableMap<K,V> subMap(K fromKey, K toKey)
// 返回此映射的部分視圖，其鍵大于等于 fromKey。
ConcurrentNavigableMap<K,V> tailMap(K fromKey)
// 返回此映射的部分視圖，其鍵大于（或等于，如果 inclusive 為 true）fromKey。
ConcurrentNavigableMap<K,V> tailMap(K fromKey, boolean inclusive)
// 返回此映射中所包含值的 Collection 視圖。
Collection<V> values()

public V put(K key, V value) {
  if (value == null)
    throw new NullPointerException();
  return doPut(key, value, false);
}

private V doPut(K kkey, V value, boolean onlyIfAbsent) {
  Comparable<? super K> key = comparable(kkey);
  for (;;) {
    // 找到key的前繼節(jié)點(diǎn)
    Node<K,V> b = findPredecessor(key);
    // 設(shè)置n為“key的前繼節(jié)點(diǎn)的后繼節(jié)點(diǎn)”，即n應(yīng)該是“插入節(jié)點(diǎn)”的“后繼節(jié)點(diǎn)”
    Node<K,V> n = b.next;
    for (;;) {
      if (n != null) {
        Node<K,V> f = n.next;
        // 如果兩次獲得的b.next不是相同的Node，就跳轉(zhuǎn)到”外層for循環(huán)“，重新獲得b和n后再遍歷。
        if (n != b.next)
          break;
        // v是“n的值”
        Object v = n.value;
        // 當(dāng)n的值為null(意味著其它線程刪除了n)；此時(shí)刪除b的下一個(gè)節(jié)點(diǎn)，然后跳轉(zhuǎn)到”外層for循環(huán)“，重新獲得b和n后再遍歷。
        if (v == null) {        // n is deleted
          n.helpDelete(b, f);
          break;
        }
        // 如果其它線程刪除了b；則跳轉(zhuǎn)到”外層for循環(huán)“，重新獲得b和n后再遍歷。
        if (v == n || b.value == null) // b is deleted
          break;
        // 比較key和n.key
        int c = key.compareTo(n.key);
        if (c > 0) {
          b = n;
          n = f;
          continue;
        }
        if (c == 0) {
          if (onlyIfAbsent || n.casValue(v, value))
            return (V)v;
          else
            break; // restart if lost race to replace value
        }
        // else c < 0; fall through
      }

      // 新建節(jié)點(diǎn)(對(duì)應(yīng)是“要插入的鍵值對(duì)”)
      Node<K,V> z = new Node<K,V>(kkey, value, n);
      // 設(shè)置“b的后繼節(jié)點(diǎn)”為z
      if (!b.casNext(n, z))
        break;     // 多線程情況下，break才可能發(fā)生(其它線程對(duì)b進(jìn)行了操作)
      // 隨機(jī)獲取一個(gè)level
      // 然后在“第1層”到“第level層”的鏈表中都插入新建節(jié)點(diǎn)
      int level = randomLevel();
      if (level > 0)
        insertIndex(z, level);
      return null;
    }
  }
}

private V doPut(K kkey, V value, boolean onlyIfAbsent) {
  Comparable<? super K> key = comparable(kkey);
  for (;;) {
    // 找到key的前繼節(jié)點(diǎn)
    Node<K,V> b = findPredecessor(key);
    // 設(shè)置n為key的后繼節(jié)點(diǎn)
    Node<K,V> n = b.next;
    for (;;) {
      
      // 新建節(jié)點(diǎn)(對(duì)應(yīng)是“要被插入的鍵值對(duì)”)
      Node<K,V> z = new Node<K,V>(kkey, value, n);
      // 設(shè)置“b的后繼節(jié)點(diǎn)”為z
      b.casNext(n, z);

      // 隨機(jī)獲取一個(gè)level
      // 然后在“第1層”到“第level層”的鏈表中都插入新建節(jié)點(diǎn)
      int level = randomLevel();
      if (level > 0)
        insertIndex(z, level);
      return null;
    }
  }
}

public V remove(Object key) {
  return doRemove(key, null);
}

final V doRemove(Object okey, Object value) {
  Comparable<? super K> key = comparable(okey);
  for (;;) {
    // 找到“key的前繼節(jié)點(diǎn)”
    Node<K,V> b = findPredecessor(key);
    // 設(shè)置n為“b的后繼節(jié)點(diǎn)”(即若key存在于“跳表中”，n就是key對(duì)應(yīng)的節(jié)點(diǎn))
    Node<K,V> n = b.next;
    for (;;) {
      if (n == null)
        return null;
      // f是“當(dāng)前節(jié)點(diǎn)n的后繼節(jié)點(diǎn)”
      Node<K,V> f = n.next;
      // 如果兩次讀取到的“b的后繼節(jié)點(diǎn)”不同(其它線程操作了該跳表)，則返回到“外層for循環(huán)”重新遍歷。
      if (n != b.next)          // inconsistent read
        break;
      // 如果“當(dāng)前節(jié)點(diǎn)n的值”變?yōu)閚ull(其它線程操作了該跳表)，則返回到“外層for循環(huán)”重新遍歷。
      Object v = n.value;
      if (v == null) {          // n is deleted
        n.helpDelete(b, f);
        break;
      }
      // 如果“前繼節(jié)點(diǎn)b”被刪除(其它線程操作了該跳表)，則返回到“外層for循環(huán)”重新遍歷。
      if (v == n || b.value == null)   // b is deleted
        break;
      int c = key.compareTo(n.key);
      if (c < 0)
        return null;
      if (c > 0) {
        b = n;
        n = f;
        continue;
      }

      // 以下是c=0的情況
      if (value != null && !value.equals(v))
        return null;
      // 設(shè)置“當(dāng)前節(jié)點(diǎn)n”的值為null
      if (!n.casValue(v, null))
        break;
      // 設(shè)置“b的后繼節(jié)點(diǎn)”為f
      if (!n.appendMarker(f) || !b.casNext(n, f))
        findNode(key);         // Retry via findNode
      else {
        // 清除“跳表”中每一層的key節(jié)點(diǎn)
        findPredecessor(key);      // Clean index
        // 如果“表頭的右索引為空”，則將“跳表的層次”-1。
        if (head.right == null)
          tryReduceLevel();
      }
      return (V)v;
    }
  }
}

final V doRemove(Object okey, Object value) {
  Comparable<? super K> key = comparable(okey);
  for (;;) {
    // 找到“key的前繼節(jié)點(diǎn)”
    Node<K,V> b = findPredecessor(key);
    // 設(shè)置n為“b的后繼節(jié)點(diǎn)”(即若key存在于“跳表中”，n就是key對(duì)應(yīng)的節(jié)點(diǎn))
    Node<K,V> n = b.next;
    for (;;) {
      // f是“當(dāng)前節(jié)點(diǎn)n的后繼節(jié)點(diǎn)”
      Node<K,V> f = n.next;

      // 設(shè)置“當(dāng)前節(jié)點(diǎn)n”的值為null
      n.casValue(v, null);

      // 設(shè)置“b的后繼節(jié)點(diǎn)”為f
      b.casNext(n, f);
      // 清除“跳表”中每一層的key節(jié)點(diǎn)
      findPredecessor(key);
      // 如果“表頭的右索引為空”，則將“跳表的層次”-1。
      if (head.right == null)
        tryReduceLevel();
      return (V)v;
    }
  }
}

public V get(Object key) {
  return doGet(key);
}

private V doGet(Object okey) {
  Comparable<? super K> key = comparable(okey);
  for (;;) {
    // 找到“key對(duì)應(yīng)的節(jié)點(diǎn)”
    Node<K,V> n = findNode(key);
    if (n == null)
      return null;
    Object v = n.value;
    if (v != null)
      return (V)v;
  }
}

private Node<K,V> findNode(Comparable<? super K> key) {
  for (;;) {
    // 找到key的前繼節(jié)點(diǎn)
    Node<K,V> b = findPredecessor(key);
    // 設(shè)置n為“b的后繼節(jié)點(diǎn)”(即若key存在于“跳表中”，n就是key對(duì)應(yīng)的節(jié)點(diǎn))
    Node<K,V> n = b.next;
    for (;;) {
      // 如果“n為null”，則跳轉(zhuǎn)中不存在key對(duì)應(yīng)的節(jié)點(diǎn)，直接返回null。
      if (n == null)
        return null;
      Node<K,V> f = n.next;
      // 如果兩次讀取到的“b的后繼節(jié)點(diǎn)”不同(其它線程操作了該跳表)，則返回到“外層for循環(huán)”重新遍歷。
      if (n != b.next)        // inconsistent read
        break;
      Object v = n.value;
      // 如果“當(dāng)前節(jié)點(diǎn)n的值”變?yōu)閚ull(其它線程操作了該跳表)，則返回到“外層for循環(huán)”重新遍歷。
      if (v == null) {        // n is deleted
        n.helpDelete(b, f);
        break;
      }
      if (v == n || b.value == null) // b is deleted
        break;
      // 若n是當(dāng)前節(jié)點(diǎn)，則返回n。
      int c = key.compareTo(n.key);
      if (c == 0)
        return n;
      // 若“節(jié)點(diǎn)n的key”小于“key”，則說(shuō)明跳表中不存在key對(duì)應(yīng)的節(jié)點(diǎn)，返回null
      if (c < 0)
        return null;
      // 若“節(jié)點(diǎn)n的key”大于“key”，則更新b和n，繼續(xù)查找。
      b = n;
      n = f;
    }
  }
}

import java.util.*;
import java.util.concurrent.*;

/*
 *  ConcurrentSkipListMap是“線程安全”的哈希表，而TreeMap是非線程安全的。
 *
 *  下面是“多個(gè)線程同時(shí)操作并且遍歷map”的示例
 *  (01) 當(dāng)map是ConcurrentSkipListMap對(duì)象時(shí)，程序能正常運(yùn)行。
 *  (02) 當(dāng)map是TreeMap對(duì)象時(shí)，程序會(huì)產(chǎn)生ConcurrentModificationException異常。
 *
 * @author skywang
 */
public class ConcurrentSkipListMapDemo1 {

  // TODO: map是TreeMap對(duì)象時(shí)，程序會(huì)出錯(cuò)。
  //private static Map<String, String> map = new TreeMap<String, String>();
  private static Map<String, String> map = new ConcurrentSkipListMap<String, String>();
  public static void main(String[] args) {
  
    // 同時(shí)啟動(dòng)兩個(gè)線程對(duì)map進(jìn)行操作！
    new MyThread("a").start();
    new MyThread("b").start();
  }

  private static void printAll() {
    String key, value;
    Iterator iter = map.entrySet().iterator();
    while(iter.hasNext()) {
      Map.Entry entry = (Map.Entry)iter.next();
      key = (String)entry.getKey();
      value = (String)entry.getValue();
      System.out.print("("+key+", "+value+"), ");
    }
    System.out.println();
  }

  private static class MyThread extends Thread {
    MyThread(String name) {
      super(name);
    }
    @Override
    public void run() {
        int i = 0;
      while (i++ < 6) {
        // “線程名” + "序號(hào)"
        String val = Thread.currentThread().getName()+i;
        map.put(val, "0");
        // 通過(guò)“Iterator”遍歷map。
        printAll();
      }
    }
  }
}

 (a1, 0), (a1, 0), (b1, 0), (b1, 0),

(a1, 0), (b1, 0), (b2, 0), 
(a1, 0), (a1, 0), (a2, 0), (a2, 0), (b1, 0), (b1, 0), (b2, 0), (b2, 0), (b3, 0), 
(b3, 0), (a1, 0), 
(a2, 0), (a3, 0), (a1, 0), (b1, 0), (a2, 0), (b2, 0), (a3, 0), (b3, 0), (b1, 0), (b4, 0), 
(b2, 0), (a1, 0), (b3, 0), (a2, 0), (b4, 0), 
(a3, 0), (a1, 0), (a4, 0), (a2, 0), (b1, 0), (a3, 0), (b2, 0), (a4, 0), (b3, 0), (b1, 0), (b4, 0), (b2, 0), (b5, 0), 
(b3, 0), (a1, 0), (b4, 0), (a2, 0), (b5, 0), 
(a3, 0), (a1, 0), (a4, 0), (a2, 0), (a5, 0), (a3, 0), (b1, 0), (a4, 0), (b2, 0), (a5, 0), (b3, 0), (b1, 0), (b4, 0), (b2, 0), (b5, 0), (b3, 0), (b6, 0), 
(b4, 0), (a1, 0), (b5, 0), (a2, 0), (b6, 0), 
(a3, 0), (a4, 0), (a5, 0), (a6, 0), (b1, 0), (b2, 0), (b3, 0), (b4, 0), (b5, 0), (b6, 0),