TreeMap、ConcurrentSkipListMap的关系
TreeMap是一种支持key数组的key-value数据结构，但用于单线程，并发运行时不安全线程。 ConcurrentSkipListMap是一种基于跳表的实现，也是一种支持key有序数组的key-value数据结构，是一种在并发情况下优秀、在空间上改变时间的实现，ConcurrentSkipListMap
(这里借用一下网上的照片)
ConcurrentSkipListMap使用volatile关键字实现并发操作，方法是存储节点数据节点和索引节点。
静态final class nodek，V { final K key； volatile对象值； //value值volatile NodeK，V next； //next引用……}静态类别索引，V { final NodeK，V node； final IndexK，V down； //down引用电压索引，V right； //right参考……}看看节点数据吧。 正在维护next的节点。 正在实现的所有数据节点node都是链表的实现方法。 索引节点保存当前索引节点的节点数据以及索引的右引用和下引用。 如果搜索时检测到索引节点level=1，即down引用为null，则将根据与当前索引节点对应的节点的链表搜索与key对应的数据。
看看如何从插入数据中实现高并发
publicvput(kkey，V value ) if ) value==null (throw new nullpointerexception )； returndoput(key，value，false )； }隐私保护(kkk ey、V value、布尔在线) { Comparable？ sperkkey=comparable(kkey )； for (； ({ NodeK，VB=查找预测器(key )； 找到//key的前驱Node数据节点NodeK，然后单击V n=b.next； for (； (if ) n！=null}{nodek，V f=n.next； //1，b的next节点两次读取不匹配，跳出第二层for循环重试(这里可能是其他现有产品在b和n之间执行了插入) ) if(n！=b.next (//inconsistentreadbreak； Object v=n.value； //2，表示数据节点的值为null，表示该数据节点被标记为已删除，删除该数据节点并重试。 if(v==null ) (/nisdeletedn.helpdelete ) ) b，f )； 布雷克； (/3，b节点标记为已删除，if(v==n||b.value==null )//b is deleted break； intc=key.comPareto(n.key )； if(c0 )//继续寻找给定密钥大于当前且合适的插入点b=n； n=f； 继续； }找到了}if(c==0) (/keyif onlyifabsent|||n.cas value (v，value ) )。 返回(v ) 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); if (!b.casNext(n, z)) break; // restart if lost race to append to b int level = randomLevel();//随机一个索引级别，这是skiplist随机性的一个体现 if (level > 0) insertIndex(z, level); return null; } } } [java] view plain copy/** * Creates and adds index nodes for the given node. * @param z the node * @param level the level of the index */ private void insertIndex(Node<K,V> z, int level) { HeadIndex<K,V> h = head; int max = h.level; if (level <= max) {//索引级别已经存在 Index<K,V> idx = null; for (int i = 1; i <= level; ++i)//首先得到一个包含1~level个索引级别的down关系的链表，最后的inx为最高level索引 idx = new Index<K,V>(z, idx, null); addIndex(idx, h, level);//Adds given index nodes from given level down to 1.新增索引 } else { // Add a new level 新增索引级别 /* To reduce interference by other threads checking for empty levels in tryReduceLevel, new levels are added * with initialized right pointers. Which in turn requires keeping levels in an array to access them while * creating new head index nodes from the opposite direction. */ level = max + 1; Index<K,V>[] idxs = (Index<K,V>[])new Index[level+1]; Index<K,V> idx = null; for (int i = 1; i <= level; ++i) idxs[i] = idx = new Index<K,V>(z, idx, null); HeadIndex<K,V> oldh; int k; for (;;) { oldh = head; int oldLevel = oldh.level;//更新head if (level <= oldLevel) { // lost race to add level k = level; break; } HeadIndex<K,V> newh = oldh; Node<K,V> oldbase = oldh.node; for (int j = oldLevel+1; j <= level; ++j) newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j); if (casHead(oldh, newh)) { k = oldLevel; break; } } addIndex(idxs[k], oldh, k); } }private void addIndex(Index<K,V> idx, HeadIndex<K,V> h, int indexLevel) { // insertionLevel 代表要插入的level，该值会在indexLevel~1间遍历一遍 int insertionLevel = indexLevel; Comparable<? super K> key = comparable(idx.node.key); if (key == null) throw new NullPointerException(); // 和get操作类似，不同的就是查找的同时在各个level上加入了对应的key for (;;) { int j = h.level; Index<K,V> q = h; Index<K,V> r = q.right; Index<K,V> t = idx; for (;;) { if (r != null) { Node<K,V> n = r.node; // compare before deletion check avoids needing recheck int c = key.compareTo(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) {//在该层level中执行插入操作 // Don't insert index if node already deleted if (jydpd()) { findNode(key); // cleans up return; } if (!q.link(r, t))//执行link操作，其实就是inset的实现部分 break; // restart if (--insertionLevel == 0) { // need final deletion check before return if (jydpd()) findNode(key); return; } } if (--j >= insertionLevel && j < indexLevel)//key移动到下一层level t = t.down; q = q.down; r = q.right; } } }