SkipList

The Skip List data structure

public class SkipList<TKey, TValue> : IVisitableDictionary<TKey, TValue>
{
      // Methods
      public void Accept(IVisitor<KeyValuePair<TKey, TValue>> visitor);
      public void Add(KeyValuePair<TKey, TValue> item);
      public void Add(TKey key, TValue value);
      public bool ContainsKey(TKey key);
      public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex);
      public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator();
      public bool Remove(TKey key);
      public bool TryGetValue(TKey key, out TValue value);
      // ...
      
      // Properties
      public IComparer<TKey> Comparer { get; }
      public int CurrentListLevel { get; }
      public TValue this[TKey key] { get; set; }
      public ICollection<TKey> Keys { get; }
      public int MaxListLevel { get; }
      public double Probability { get; }
      public ICollection<TValue> Values { get; }
      // ...
} 

A SkipList is an ingenious data structure, first proposed by William Pugh in 1990. You can find his original paper here. The crux of a SkipList is that items get duplicated on different levels of linked lists, the level (almost) randomly selected. It allows for quick searching for an item by "skipping" over several list items as opposed to a normal linked list where comparisons would be sequential.

Skip lists are usually implemented in one of two ways, using either several linked lists, or a matrix structure (like a 2D linked list). The SkipList implemented here is implemented using the matrix style, and is based on the excellent work done by Leslie Stanford and ger. It implements the IDictionary<TKey, TValue> interface, and thus can be used like the standard Dictionary<TKey, TValue> class in the framework.

Just note that while the performance is excellent, the duplication of items can cause that you run out of memory very quickly, especially if the maximum number of levels are high.

More information on Skip Lists