我们可以用很多有趣的方式实现映射，如散列表、二叉搜索树、跳表等。
下面是对上面数据结构一些简单的介绍：
散列表 ：给定一组键和一个散列函数，将键放入集合中，并搜索和取出关联的值。这种搜索操作的的时间复杂度为$O(1)$，不过去性能会因为表的大小、冲突、冲突解决策略等因素而降低。二叉搜索树 ：把键存储在树中时，搜索操作的时间复杂度是$O(logn)$。 不过，这只有在树平衡时才成立，即树的左右子树差不多大时。跳表 ：其本质上是一个二维链表，链接的方向向前或者向下。表头在左上角，它是跳表的唯一入口。既能高效搜索，又避免了上述的缺点。
基本概念 跳表示例如下图所示：
由上图可知，跳表是由节点组成，分为头节点 和数据节点 ，头节点保存了down和next的引用，数据节点每个节点存有一个键 及其关联的值 ，每个节点有两个向外的引用，分别为down和next，down指向下一层的头节点，next引用指向数据节点的链表。由数据节点构成的纵列称为塔 ，塔是由数据节点中的down引用连起来的。跳表水平方向是由一系列节点集合组成的有序链表，其链表的名称为其层数 ，0层包含了所有数据的节点，层数越高，包含的节点越少，其有助于提高搜索效率。
实现 对跳表的实现主要分为节点的实现，相关方法的实现。
节点 首先对跳表的头部和其数据节点进行了实现，并且实现了相关的方法，其结构类似于链表：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 class HeaderNode : def __init__ (self) : self.next = None self.down = None def get_next (self) : return self.next def get_down (self) : return self.down def set_next (self, new_next) : self.next = new_next def set_down (self, new_down) : self.down = new_down class DataNode : def __init__ (self, key, value) : self.key = key self.data = value self.next = None self.down = None def get_key (self) : return self.key def get_data (self) : return self.data def get_next (self) : return self.next def get_down (self) : return self.down def set_data (self, new_data) : self.data = new_data def set_next (self, new_next) : self.next = new_next def set_down (self, new_down) : self.down = new_down
搜索 搜索一般从表头开始，知道找到键，或者检查完所有的数据节点。下面是关于跳表搜索的相关python实现，其中found和stop用于条件的控制，其基本思路是从顶层的头节点开始往右查找，如果没有数据节点，就下降一层；如果有数据节点就比较大小，如果匹配则将found置为True：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class SkipList : def __init__ (self) : self.head = None def search (self, key) : current = self.head found = False stop = False while not found and not stop: if current is None : stop = True else : if current.get_next() is None : current = current.get_down() else : if current.get_next().get_key() == key: found = True else : if key < current.get_next.get_key(): current = current.get_down() else : current.get_next() if found: return current.get_next().get_data() else : return None
加入键值对 要往跳表中新增键值对，本质上需要两步：
搜索跳表，寻找插入位置；
新建一个数据节点，并将它加入到第0层的链表中。
为新的数据节点构建塔，其他的高度是随机的，本质上通过抛硬币的方式决定是否在塔中加入一层。
其代码实现的部分如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 class SkipList : ... """ 上面为已实现部分 """ def insert (self, key, data) : if self.head is None : self.head = HeaderNode() temp = DataNode(key, data) self.head.set_next(temp) top = temp while self.flip() == 1 : new_head = HeaderNode() temp = DataNode(key, data) temp.set_down(top) new_head.set_next(temp) new_head.set_down(self.head) self.head = new_head top = temp else : tower_stack = [] current = self.head stop = False while not stop: if current is None : stop = True else : if current.get_next() is None : tower_stack.append(current) current = current.get_down() else : if current.get_next().get_key() > key: tower_stack.append(current) current = current.get_down() else : current = current.get_next() lowest_level = tower_stack.pop() temp = DataNode(key, data) temp.set_next(lowest_level.get_next()) lowest_level.set_next(temp) top = temp while self.flip() == 1 : if not tower_stack: new_head = HeaderNode() temp = DataNode(key, data) temp.set_down(top) new_head.set_next(temp) new_head.set_down(self.head) self.head = new_head top = temp else : next_level = tower_stack.pop() temp = DataNode(key, data) temp.set_down(top) temp.set_next(next_level.get_next()) next_level.set_next(temp) top = temp @staticmethod def flip () : return randrange(2 )
分析跳表 跳表是基于概率的数据结构，这意味着其性能基于某些事件的概率。从理论上来说，每添加一个数据节点，添加的概率为$1/2$，那么我们可以说有$n/2$个键的高度是2，$n/4$个键的高度是3，以此类推，那么这个它的高度是$log_2n + 1$ ，以大$O$记法，可以说跳表的高度为$O(logn)$。
给定一个键，在查找的时候要扫描两个方向，一个是向下，找到目标的概率是$O(logn)$，第二个方向是沿着每一层向前扫描，每当遇到以下两种情况
因为插入操作的大部分时间花在查找插入位置上，所以插入操作的时间复杂度也是$O(logn)$。
