// 构造一个新的空映射，该映射按照键的自然顺序进行排序。
ConcurrentSkipListMap()
// 构造一个新的空映射，该映射按照指定的比较器进行排序。
ConcurrentSkipListMap(Comparator<? super K> comparator)
// 构造一个新映射，该映射所包含的映射关系与给定映射包含的映射关系相同，并按照键的自然顺序进行排序。
ConcurrentSkipListMap(Map<? extends K,? extends V> m)
// 构造一个新映射，该映射所包含的映射关系与指定的有序映射包含的映射关系相同，使用的顺序也相同。
ConcurrentSkipListMap(SortedMap<K,? extends V> m)

// 返回与大于等于给定键的最小键关联的键-值映射关系；如果不存在这样的条目，则返回 null。
Map.Entry<K,V> ceilingEntry(K key)
// 返回大于等于给定键的最小键；如果不存在这样的键，则返回 null。
K ceilingKey(K key)
// 从此映射中移除所有映射关系。
void clear()
// 返回此 ConcurrentSkipListMap 实例的浅表副本。
ConcurrentSkipListMap<K,V> clone()
// 返回对此映射中的键进行排序的比较器；如果此映射使用键的自然顺序，则返回 null。
Comparator<? super K> comparator()
// 如果此映射包含指定键的映射关系，则返回 true。
boolean containsKey(Object key)
// 如果此映射为指定值映射一个或多个键，则返回 true。
boolean containsValue(Object value)
// 返回此映射中所包含键的逆序 NavigableSet 视图。
NavigableSet<K> descendingKeySet()
// 返回此映射中所包含映射关系的逆序视图。
ConcurrentNavigableMap<K,V> descendingMap()
// 返回此映射中所包含的映射关系的 Set 视图。
Set<Map.Entry<K,V>> entrySet()
// 比较指定对象与此映射的相等性。
boolean equals(Object o)
// 返回与此映射中的最小键关联的键-值映射关系；如果该映射为空，则返回 null。
Map.Entry<K,V> firstEntry()
// 返回此映射中当前第一个（最低）键。
K firstKey()
// 返回与小于等于给定键的最大键关联的键-值映射关系；如果不存在这样的键，则返回 null。
Map.Entry<K,V> floorEntry(K key)
// 返回小于等于给定键的最大键；如果不存在这样的键，则返回 null。
K floorKey(K key)
// 返回指定键所映射到的值；如果此映射不包含该键的映射关系，则返回 null。
V get(Object key)
// 返回此映射的部分视图，其键值严格小于 toKey。
ConcurrentNavigableMap<K,V> headMap(K toKey)
// 返回此映射的部分视图，其键小于（或等于，如果 inclusive 为 true）toKey。
ConcurrentNavigableMap<K,V> headMap(K toKey, boolean inclusive)
// 返回与严格大于给定键的最小键关联的键-值映射关系；如果不存在这样的键，则返回 null。
Map.Entry<K,V> higherEntry(K key)
// 返回严格大于给定键的最小键；如果不存在这样的键，则返回 null。
K higherKey(K key)
// 如果此映射未包含键-值映射关系，则返回 true。
boolean isEmpty()
// 返回此映射中所包含键的 NavigableSet 视图。
NavigableSet<K> keySet()
// 返回与此映射中的最大键关联的键-值映射关系；如果该映射为空，则返回 null。
Map.Entry<K,V> lastEntry()
// 返回映射中当前最后一个（最高）键。
K lastKey()
// 返回与严格小于给定键的最大键关联的键-值映射关系；如果不存在这样的键，则返回 null。
Map.Entry<K,V> lowerEntry(K key)
// 返回严格小于给定键的最大键；如果不存在这样的键，则返回 null。
K lowerKey(K key)
// 返回此映射中所包含键的 NavigableSet 视图。
NavigableSet<K> navigableKeySet()
// 移除并返回与此映射中的最小键关联的键-值映射关系；如果该映射为空，则返回 null。
Map.Entry<K,V> pollFirstEntry()
// 移除并返回与此映射中的最大键关联的键-值映射关系；如果该映射为空，则返回 null。
Map.Entry<K,V> pollLastEntry()
// 将指定值与此映射中的指定键关联。
V put(K key, V value)
// 如果指定键已经不再与某个值相关联，则将它与给定值关联。
V putIfAbsent(K key, V value)
// 从此映射中移除指定键的映射关系（如果存在）。
V remove(Object key)
// 只有目前将键的条目映射到给定值时，才移除该键的条目。
boolean remove(Object key, Object value)
// 只有目前将键的条目映射到某一值时，才替换该键的条目。
V replace(K key, V value)
// 只有目前将键的条目映射到给定值时，才替换该键的条目。
boolean replace(K key, V oldValue, V newValue)
// 返回此映射中的键-值映射关系数。
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的前继节点
    Node<K,V> b = findPredecessor(key);
    // 设置n为“key的前继节点的后继节点”，即n应该是“插入节点”的“后继节点”
    Node<K,V> n = b.next;
    for (;;) {
      if (n != null) {
        Node<K,V> f = n.next;
        // 如果两次获得的b.next不是相同的Node，就跳转到”外层for循环“，重新获得b和n后再遍历。
        if (n != b.next)
          break;
        // v是“n的值”
        Object v = n.value;
        // 当n的值为null(意味着其它线程删除了n)；此时删除b的下一个节点，然后跳转到”外层for循环“，重新获得b和n后再遍历。
        if (v == null) {        // n is deleted
          n.helpDelete(b, f);
          break;
        }
        // 如果其它线程删除了b；则跳转到”外层for循环“，重新获得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
      }

      // 新建节点(对应是“要插入的键值对”)
      Node<K,V> z = new Node<K,V>(kkey, value, n);
      // 设置“b的后继节点”为z
      if (!b.casNext(n, z))
        break;     // 多线程情况下，break才可能发生(其它线程对b进行了操作)
      // 随机获取一个level
      // 然后在“第1层”到“第level层”的链表中都插入新建节点
      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的前继节点
    Node<K,V> b = findPredecessor(key);
    // 设置n为key的后继节点
    Node<K,V> n = b.next;
    for (;;) {
      
      // 新建节点(对应是“要被插入的键值对”)
      Node<K,V> z = new Node<K,V>(kkey, value, n);
      // 设置“b的后继节点”为z
      b.casNext(n, z);

      // 随机获取一个level
      // 然后在“第1层”到“第level层”的链表中都插入新建节点
      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的前继节点”
    Node<K,V> b = findPredecessor(key);
    // 设置n为“b的后继节点”(即若key存在于“跳表中”，n就是key对应的节点)
    Node<K,V> n = b.next;
    for (;;) {
      if (n == null)
        return null;
      // f是“当前节点n的后继节点”
      Node<K,V> f = n.next;
      // 如果两次读取到的“b的后继节点”不同(其它线程操作了该跳表)，则返回到“外层for循环”重新遍历。
      if (n != b.next)          // inconsistent read
        break;
      // 如果“当前节点n的值”变为null(其它线程操作了该跳表)，则返回到“外层for循环”重新遍历。
      Object v = n.value;
      if (v == null) {          // n is deleted
        n.helpDelete(b, f);
        break;
      }
      // 如果“前继节点b”被删除(其它线程操作了该跳表)，则返回到“外层for循环”重新遍历。
      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;
      // 设置“当前节点n”的值为null
      if (!n.casValue(v, null))
        break;
      // 设置“b的后继节点”为f
      if (!n.appendMarker(f) || !b.casNext(n, f))
        findNode(key);         // Retry via findNode
      else {
        // 清除“跳表”中每一层的key节点
        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的前继节点”
    Node<K,V> b = findPredecessor(key);
    // 设置n为“b的后继节点”(即若key存在于“跳表中”，n就是key对应的节点)
    Node<K,V> n = b.next;
    for (;;) {
      // f是“当前节点n的后继节点”
      Node<K,V> f = n.next;

      // 设置“当前节点n”的值为null
      n.casValue(v, null);

      // 设置“b的后继节点”为f
      b.casNext(n, f);
      // 清除“跳表”中每一层的key节点
      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对应的节点”
    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的前继节点
    Node<K,V> b = findPredecessor(key);
    // 设置n为“b的后继节点”(即若key存在于“跳表中”，n就是key对应的节点)
    Node<K,V> n = b.next;
    for (;;) {
      // 如果“n为null”，则跳转中不存在key对应的节点，直接返回null。
      if (n == null)
        return null;
      Node<K,V> f = n.next;
      // 如果两次读取到的“b的后继节点”不同(其它线程操作了该跳表)，则返回到“外层for循环”重新遍历。
      if (n != b.next)        // inconsistent read
        break;
      Object v = n.value;
      // 如果“当前节点n的值”变为null(其它线程操作了该跳表)，则返回到“外层for循环”重新遍历。
      if (v == null) {        // n is deleted
        n.helpDelete(b, f);
        break;
      }
      if (v == n || b.value == null) // b is deleted
        break;
      // 若n是当前节点，则返回n。
      int c = key.compareTo(n.key);
      if (c == 0)
        return n;
      // 若“节点n的key”小于“key”，则说明跳表中不存在key对应的节点，返回null
      if (c < 0)
        return null;
      // 若“节点n的key”大于“key”，则更新b和n，继续查找。
      b = n;
      n = f;
    }
  }
}

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

/*
 *  ConcurrentSkipListMap是“线程安全”的哈希表，而TreeMap是非线程安全的。
 *
 *  下面是“多个线程同时操作并且遍历map”的示例
 *  (01) 当map是ConcurrentSkipListMap对象时，程序能正常运行。
 *  (02) 当map是TreeMap对象时，程序会产生ConcurrentModificationException异常。
 *
 * @author skywang
 */
public class ConcurrentSkipListMapDemo1 {

  // TODO: map是TreeMap对象时，程序会出错。
  //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) {
  
    // 同时启动两个线程对map进行操作！
    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) {
        // “线程名” + "序号"
        String val = Thread.currentThread().getName()+i;
        map.put(val, "0");
        // 通过“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),