http://www.developer.com/design/article.php/10925_3795251_3/Java-Ordered-Collections-Trees-and-Skip-Lists.htm
java.util.concurrent.ConcurrentSkipListSet is a thread-safe implementation of the SortedSet interface. Multiple threads can add and remove objects at the same time and work correctly. However, individual search, add, and remove operations take longer for aConcurrentSkipListSet than for a TreeSet, so you usually should not use ConcurrentSkipListSet unless concurrency is an issue.
One other caution about the ConcurrentSkipListSet is that thesize() method can take a long time. To avoid needing locks, theConcurrentSkipListSet does not keep a running count of the number of objects that are currently in the set. For this reason, thesize method works by iterating over the objects in theConcurrentSkipListSet and counts them.
The ConcurrentSkipListSet is based on a data structure called a skip list. Unlike a binary tree, the internal organization of a skip list does not need to be adjusted because of the order that data is added or removed. The internal organization of a skip list is based on random numbers and is not dependent on the actual data in the skip list.
Figure 5 shows an example of a skip list.
Figure 5: Skip List
The first node in the skip list is called the header. It refers to other nodes or an object called NIL. NIL is at the end of every skip list. Both the header and NIL are in every skip list, even if the skip list is empty.
The header is the first node in multiple linked lists. These linked lists are called level 1, level 2, … In Figure 5, the level 1 list is shown towards the bottom of the diagram and the level 4 list is shown towards the top of the list.
Nodes that appear in the linked lists between the header and NIL have associated value objects. The order in which nodes appear in the linked lists is based on their value objects and determined by the natural ordering of the value objects or by a Comparator.
All of the nodes in a skip list are in the level 1 linked list. Roughly ½ of the nodes in a skip list are in the level 1 and 2 linked lists. About ½ of those nodes (about ¼ of all the nodes) are also in the level 3 linked list. If there are higher levels of linked lists, each linked list includes about ½ of the nodes in the linked list in the next lower level.
The algorithm for searching a skip list starts at the highest level linked list, looking for a node whose value is greater than or equal to the value being searched for. If the value of a node is equal to what is being searched for, the search is done. Otherwise, the search backs up a node and continues one level of linked list down until either the search is successful or there are no more nodes to search. To clarify the search process, here is an example:
When a node is added to a skip list, a random number generator is used to determine what levels of linked list the node will be included in. There is a ½ chance that a new node will be included in the level 2 linked list. There is a ¼ chance that the new node will be included in the level 3 linked list. For each higher level of linked list, the chance of a new node being included in the linked list is ½ of the chance of its being included in the next lower level linked list.
