上述代码表示从队列中拿走一个元素。当有空闲位置时，在第7行，通知等待入队的线程。
BlockingQueue的使用非常普遍。在后续的“5.3生产者消费者”一节中，我们还会看到他们的身影。在那里，我们可以更清楚地看到如何使用BlockingQueue解耦生产者和消费者。
3.3.7 随机数据结构：跳表（SkipList）
在JDK的并发包中，除了常用的哈希表外，还实现了一种有趣的数据结构——跳表。跳表是一种可以用来快速查找的数据结构，有点类似于平衡树。它们都可以对元素进行快速的查找。但一个重要的区别是：对平衡树的插入和删除往往很可能导致平衡树进行一次全局的调整。而对跳表的插入和删除只需要对整个数据结构的局部进行操作即可。这样带来的好处是：在高并发的情况下，你会需要一个全局锁来保证整个平衡树的线程安全。而对于跳表，你只需要部分锁即可。这样，在高并发环境下，你就可以拥有更好的性能。而就查询的性能而言，跳表的时间复杂度也是O(log n)。所以在并发数据结构中，JDK使用跳表来实现一个Map。
跳表的另外一个特点是随机算法。跳表的本质是同时维护了多个链表，并且链表是分层的，如图3.16所示。
图3.16 跳表结构示意图
最低层的链表维护了跳表内所有的元素，每上面一层链表都是下面一层的子集，一个元素插入哪些层是完全随机的。因此，如果你运气不好的话，你可能会得到一个性能很糟糕的结构。但是在实际工作中，它的表现是非常好的。
跳表内的所有链表的元素都是排序的。查找时，可以从顶级链表开始找。一旦发现被查找的元素大于当前链表中的取值，就会转入下一层链表继续找。这也就是说在查找过程中，搜索是跳跃式的，如图3.17所示，在跳表中查找元素7。查找从顶层的头部索引节点开始。由于顶层的元素最少，因此，可以快速跳跃那些小于7的元素。很快，查找过程就能到元素6。由于在第2层，元素8大于7，故肯定无法在第2层找到元素7，故直接进入底层（包含所有元素）开始查找，并且很快就可以根据元素6搜索到元素7。整个过程，要比一般链表从元素1开始逐个搜索快很多。
图3.17 跳表的查找过程
因此，很显然，跳表是一种使用空间换时间的算法。
使用跳表实现Map和使用哈希算法实现Map的另外一个不同之处是：哈希并不会保存元素的顺序，而跳表内所有的元素都是排序的。因此在对跳表进行遍历时，你会得到一个有序的结果。所以，如果你的应用需要有序性，那么跳表就是你不二的选择。
实现这一数据结构的类是ConcurrentSkipListMap。下面展示了跳表的简单使用：
Map＜Integer, Integer＞ map=new ConcurrentSkipListMap＜Integer, Integer＞(); for(int i=0;i＜30;i++){ map.put(i,i); } for(Map.Entry＜Integer, Integer＞ entry:map.entrySet()){ System.out.println(entry.getKey()); }
和HashMap不同，对跳表的遍历输出是有序的。
跳表的内部实现有几个关键的数据结构组成。首先是Node，一个Node就是表示一个节点，里面含有两个重要的元素key和value（就是Map的key和value）。每个Node还会指向下一个Node，因此还有一个元素next。
static final class Node＜K,V＞ { final K key; volatile Object value; volatile Node＜K,V＞ next;
对Node的所有操作，使用的CAS方法：
boolean casValue(Object cmp, Object val) { return UNSAFE.compareAndSwapObject(this, valueOffset, cmp, val); } boolean casNext(Node＜K,V＞ cmp, Node＜K,V＞ val) { return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val); }
方法casValue()用来设置value的值，相对的casNext()用来设置next的字段。
另外一个重要的数据结构是Index。顾名思义，这个表示索引。它内部包装了Node，同时增加了向下的引用和向右的引用。
static class Index＜K,V＞ { final Node＜K,V＞ node; final Index＜K,V＞ down; volatile Index＜K,V＞ right;
整个跳表就是根据Index进行全网的组织的。
此外，对于每一层的表头，还需要记录当前处于哪一层。为此，还需要一个称为HeadIndex的数据结构，表示链表头部的第一个Index。它继承自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; } }
这样核心的内部元素就介绍完成了。对于跳表的所有操作，就是组织好这些Index之间的连接关系。
3.4 参考资料
这篇博客讲解了ScheduledThreadPoolExecutor的使用注意事项
http://segmentfault.com/a/1190000000371905
这里讲解了几个有关线程池的使用技巧
http://it.deepinmind.com/java/2014/11/26/executorservice-10-tips-and-tricks.html
有关Fork/Join的简单实现原理
http://www.infoq.com/cn/articles/fork-join-introduction
有关ConcurrentLinkedQueue的实现具体分析（其使用的JDK版本与本书不同）
http://my.oschina.net/xianggao/blog/389332
http://www.ibm.com/developerworks/cn/java/j-lo-concurrent/
有关ConcurrentSkipListMap的运作原理（示例图示很好）
http://www.liuhaihua.cn/archives/40657.html
