一、什么是跳表 跳表全称叫做跳跃表，简称跳表。跳表是一个随机化的数据结构，可以被看做二叉树的一个变种，它在性能上和红黑树，AVL树不相上下，但是跳表的原理非常简单，目前在Redis和LeveIDB中都有用到。 在对有序顺序表进行搜索时，使用二分查找时间复杂度是O(logn)，但是有序顺序表的插入和删除却是O(n)的算法。 在对有序链表进行搜索时，时间复杂度是O(n)，但是对链表的插入算法却是O(1)。 可以看到有序顺序表和链表各有各的优势，同时也有自身的缺点，而我们要讲的跳跃表就是集成了以上两种数据结构的优点，但是自身多耗费一部分空间的数据结构。
二、跳表的原理 跳表的原理非常简单，跳表其实就是一种可以进行二分查找的有序链表。跳表的数据结构模型如图:
可以看到，跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。首先在最高级索引上查找最后一个小于当前查找元素的位置，然后再跳到次高级索引继续查找，直到跳到最底层为止，这时候以及十分接近要查找的元素的位置了(如果查找元素存在的话)。由于根据索引可以一次跳过多个元素，所以跳查找的查找速度也就变快了。 最理想的情况下，跳表就像一颗满二叉树，查找的时间复杂度是O(logn)。问题 是怎么决定一个结点有多少级索引？？？ 针对这个问题跳表的创始人提出了一种抛硬币的方法，用随机函数产生一个0或者1，如果是1的话则leve++,直到产生0位置，当数据量足够大的时候，leve的取值会趋向于正态分布。
三、跳表与红黑树，AVL树等平衡数据结构的比较 跳表与红黑树和AVL树相比，效率不相上下，但是它胜在实现起来比较简单，我们可以很快的实现出来。跳表在更新的时候需要改动的地方很少，而红黑树和AVL树需要改动的地方很多。如果在多线程的情况下，红黑树和AVL树在维持平衡的时候，需要的锁资源很多，越是在靠近根节点的地方越容易产生竞争。但是跳表的操作更加局部性一点，需要锁住的资源很少。
四、跳表的实现 跳表的性质： 1、由很多层组成 2、每一层都是一个有序链表 3、最底层的链表包含所有元素 4、如果一个元素出现在第i层的链表中，则它在i-1层中也会出现。 5、上层节点可以跳转到下层。 跳表的实现:
#ifndef _SKIPLIST_H__ #define _SKIPLIST_H__ #include<time.h> #include<iostream> #include<vector> #include<cstdio> #include<cstdlib> using namespace std; #define MAXLEVE 8 //跳表的最大层数 template<typename K,typename V> struct SkipNode //跳表的节点类型 { K _key; V _value; size_t _sz; //表示该节点的层数 vector<SkipNode<K,V> *> _pleve; //存放每一层的指针 SkipNode(K key=K(),V value=V(),size_t sz=size_t()) :_key(key) ,_value(value) ,_sz(sz) { _pleve.resize(0); for(size_t i=0;i<sz;i++) { _pleve.push_back(NULL); } } ~SkipNode() { _key=-1; _value=-1; _sz=-1; _pleve.clear(); } }; template<typename K,typename V> class SkipList //跳表类 { public: typedef SkipNode<K,V> Node; SkipList(); void Insert(K key,V value); bool Find(K key,V& value); bool Erase(K key); void Print(); int GetLeve(); //返回跳表的最大层数 size_t Size(); ~SkipList(); private: int Random(); //产生随机层数的函数 protected: SkipList(SkipList<K,V> &); //防拷贝 SkipList<K,V>& operator=(SkipList<K,V>); //防赋值 private: Node *_head; int _maxLeve; //记录跳表的最大层数 int _size; //记录跳表最底层元素的个数 }; #endif //_SKIPLIST_H__ template<typename K,typename V> size_t SkipList<K,V>::Size() { return _size; } template<typename K,typename V> int SkipList<K,V>::GetLeve() { return _maxLeve; } template<class K,class V> int SkipList<K,V>::Random() { int leve=1; while(rand()%2&&leve<=MAXLEVE) //产生0或1,1的话leve++,最后平均下来leve的值趋向与正态分布 { leve++; } return leve; } template<typename K,typename V> SkipList<K,V>::SkipList() { _maxLeve=1; _size=0; _head=new Node(-1,-1,MAXLEVE); } template<typename K,typename V> void SkipList<K,V>::Insert(K key,V value) { int i=_maxLeve-1; int j=0; Node* cur=_head; //指向跳表的起点 Node* s[MAXLEVE]; //用来保存每层向下跳转位置的前驱 while(i>=0) { while(cur->_pleve[i]) { if(key>=cur->_pleve[i]->_key) { cur=cur->_pleve[i]; } else break; } s[j++]=cur; i--; } i=0; int leve=Random(); //产生一个随机层数 _maxLeve<leve?_maxLeve=leve:_maxLeve; //更新跳表的最大层数 Node* newNode=new Node(key,value,leve); //创建一个节点 for(i=0;i<leve;i++) { if(i<j) { newNode->_pleve[i]=s[j-i-1]->_pleve[i]; s[j-i-1]->_pleve[i]=newNode; } else { _head->_pleve[i]=newNode; } } _size++; } template<typename K,typename V> bool SkipList<K,V>::Find(K key,V& value) { int i=_maxLeve-1; Node* cur=_head; //指向跳表的起点 while(i>=0) { while(cur->_pleve[i]) { if(key>=cur->_pleve[i]->_key) { cur=cur->_pleve[i]; } else break; } i--; } i=0; if(cur->_key==key) //最好采用仿函数进行比较 { value=cur->_value; return true; } return false; } template<typename K,typename V> bool SkipList<K,V>::Erase(K key) { int i=_maxLeve-1; int j=0; Node* cur=_head; //指向跳表的起点 Node* s[MAXLEVE]; //用来保存每层向下跳转位置的前驱 while(i>=0) { while(cur->_pleve[i]) { if(key>cur->_pleve[i]->_key) { cur=cur->_pleve[i]; } else break; } s[j++]=cur; i--; } if(cur->_pleve[0]&&cur->_pleve[0]->_key==key) { cur=cur->_pleve[0]; int leve=cur->_sz; Node *del=NULL; del=cur; for(i=0;i<leve;i++) //将该节点的每层都进行删除 { s[j-i-1]->_pleve[i]=cur->_pleve[i]; } delete del; while(_maxLeve>1) //如果某一层只有头结点，则删除整层 { if(NULL==_head->_pleve[_maxLeve-1]) _maxLeve--; else break; } if(_size>0) _size--; } return false; } template<typename K,typename V> void SkipList<K,V>::Print() { int i=_maxLeve-1; while(i>=0) { Node* cur=_head; printf("this is %d leve:",i+1); while(cur) { cout<<cur->_key<<":"<<"["<<cur->_value<<"]"<<" "; cur=cur->_pleve[i]; } i--; printf("\n"); } } template<typename K,typename V> SkipList<K,V>::~SkipList() { Node* cur=_head; Node* del; while(cur) { del=cur; cur=cur->_pleve[0]; delete del; } _head=NULL; } 例： #include"skiplist.hpp" void test() { { SkipList<int,int> s; // s.Insert(1,1); // s.Insert(3,3); // s.Insert(2,2); // s.Insert(4,4); // s.Insert(5,5); // s.Insert(6,6); // s.Insert(7,7); // s.Insert(8,8); // s.Insert(9,9); // s.Insert(10,10); s.Erase(6); // s.Insert(11,11); // s.Insert(12,12); s.Print(); cout<<s.GetLeve()<<endl;; cout<<s.Size()<<endl;; } cout<<"destroy SkipList"<<endl;; // s.Erase(1); // s.Print(); // s.Erase(2); // s.Print(); // s.Erase(3); // s.Print(); // int i=1; // for(i=1;i<13;i++) // { // printf("delete %d leve\n",i-1); // s.Erase(i); // s.Print(); // } // cout<<endl; // s.Print(); // int value=0; // int key=13; // if(s.Find(key,value)) // { // cout<<"key="<<key<<",value is:"<<value<<endl; // } // else // { // cout<<"not found"<<endl; // } } int main() { test(); return 0; }