词典类型
- 定义，这样一类数据类型，它支持按照键值进行获取元素；
class Dictionary(metaclass=abc.ABCMeta):
@abc.abstractmethod
def put(self, key, item):
"""
放置一个键值对
:param key: 键
:param item: 值
:return:
"""
pass
@abc.abstractmethod
def get(self, key):
"""
根据一个键获取对应的值
:param key:
:return:
"""
pass
@abc.abstractmethod
def remove(self, key):
"""
根据键删除值
:param key:
:return:
"""
pass
@abc.abstractmethod
def size(self):
"""
获取尺寸
:return:
"""
pass
词典数据类型可以使用哈希表来实现，如果本身键可以定义顺序，则可以采用搜索树来或者跳转表来实现，下面介绍hash表和跳转表；
Hash表
Hash表的主要思路就是对键值进行hash计算，从而获取一个索引，将元素放在数组中对应的位置上去；这样，每次获取的时候，就调用hash算法，对键进行一次计算，获取索引后，获得对应位置的元素即可；
本质上是使用数组进行存储的结构，但是，无论怎样的hash算法，总是会出现不同键计算出hash值相同的场景，这种情况称之为hash碰撞，处理hash碰撞的方式，常见的有如下两种：
- 开放寻址法，即当发现hash冲突后，通过一定的手段再次获取hash值，一直到没有冲突为止，例如可以准备多个hash算法，或者对计算出来的hash值再次计算hash，这样来获取新的索引，也可以直接从当前索引开始向后逐个寻找，找到第一个空为止，就把元素放进去，java中的ThreadLocal中的hashMap就是采用这样的方式来处理hash冲突问题的，好处是简单，并且向后逐个探查的方式有利于CPU的读取（顺序读取数据），同时简单的存储结构更加有利于序列化；
- 链表法，相同hash值的元素使用链表储存，好处是对内存的利用率较高，同时，如果碰撞的数据过于多的时候可以采用红黑树等搜索树来组织相同hash值的元素，从而有利于查找，java的HashMap就是这样处理的；
Hash表主要是采用数组进行存储，因此实际存储的量和申请的空间存在一个比值，这个比值为装载因子，一般来说装载因子不能太大，太大的话hash碰撞必然增多，因此当装载因子达到一定值的时候需要进行扩容，一般采用成倍的扩容方法，同样的当装载因子过小的时候进行缩容来节省空间；
分布式存储
在存储数据量较大的时候，可能需要采用多台机器去存储，这时候，可以利用Hash表的思路，对于要存储的内容进行hash计算后再对机器数量取模，从而获取具体要存储在那台机器上；
这样的存储方式存在一个问题，就是当存储量不够的时候需要进行扩容时，动态的增加一台机器，所有的存储内容均需要进行重新移动，拓展，如果是存储的缓存的话，那么原本所有的缓存同时都失效了；
这里解决的方式可以采用一致性Hash算法来处理，主要的思路如下：要存储的元素的hash值的范围是0-Max，那么，每台机器负责存储的一个区间内的Hash的元素，例如0-Max/k存储在第一台机器内，这样，如果增加一台机器的话，则仅有一部分的数据从原来的位置搬到的新的机器中去（不是全部），这样就可以缓解这个问题；
等效的处理方式，可以借助一个虚拟的环来说明问题，我们将0-\(2^{32}\)，这样的数据均匀的分散到一个圆环上，这样的环成为Hash环，然后对存储的机器的ip进行取模计算，从而获取到一个环上的位置，如下图：
同样的数据也可通过取模的方式处于环上的一个点，然后这个数据点顺时针旋转找到的第一台机器便是存储的机器；
这样就可以实现增加或减少机器的时候，仅移动部分数据而不是直接全部数据进行一次重新分配；
不过这样做存在另外的一个问题，就是机器在环上的分布不一定是均匀的，这样会造成机器本身负载的不均衡，这个问题可以通过虚拟节点来处理，在均匀的位置上添加虚拟节点，并且记录虚拟节点和真实节点的对应关系，则可以解决节点不均匀的问题；
跳转表
主要的思路是在有序链表中，将各个节点以1/2的概率向上增加一个节点，然后再对上层构成一个有序链表，然后再做同样的操作，直到最顶层的链表节点数为0；
构建出来的结构如图所示：
搜索时从最顶端的数据节点开始，向左找目标键，找到第一个大于等于该键或者尾结点的前置节点，如果该节点键和要找的键一致，则返回，否则向下找，直到找到对应键或者最底层失败返回；
首先是时间复杂度，以一半的概率增长，所以高度的期望值是\(log(n)\)，所以纵向移动的最多为\(log(n)\)个节点，再来看横向的访问节点数量为例，以上图为例，最顶层节点数量为1，从该节点开始，无论查找什么数据，每层的访问节点数量不超过3个（高层查找的时候会略过大量的底层元素），从另一个角度来讲，从最顶层开始查找，没过一层要略过一半的元素，类似二分查找，在整个横向查找的过程中，查看的节点数不超过\(o(logn)\)个，再加上纵向的查找节点，最终得出结论，搜索的时间复杂度为\(olog(n)\)；
空间复杂度，总结点数量为：\(N=n(1+1/2+1/4+1/8+...)=2n\)，因此空间复杂度依旧是\(o(n)\)；
class Entry:
def __init__(self, k, v):
self.key = k
self.value = v
class QuadNode:
def __init__(self):
"""
跳转表中的主要节点，具备上中下左四个指针引用，用来构建四链表
"""
self.above: QuadNode = None
self.below: QuadNode = None
self.prev: QuadNode = None
self.succ: QuadNode = None
self.data: Entry = None
def insert_below(self, node):
"""
在本节点的下方插入一个节点
:param node:
:return:
"""
tem = self.below
self.below = node
node.above = self
if tem:
tem.above = node
node.below = tem
def insert_above(self, node):
"""
在本节点的额上方插入一个节点
:param node:
:return:
"""
tem = self.above
self.above = node
node.below = self
if tem:
node.above = tem
tem.below = node
def insert_after(self, node):
"""
在本节点的后方插入一个节点
:param node:
:return:
"""
tem = self.succ
self.succ = node
node.prev = self
node.succ = tem
tem.prev = node
class QuadList:
def __init__(self):
"""
每个表示跳转表中的一行
"""
self.header = QuadNode()
self.trailer = QuadNode()
self.header.succ = self.trailer
self.trailer.prev = self.header
class ListNode:
def __init__(self):
"""
跳转表使用链表组成，由多个行同时构成
"""
self.prev: ListNode = None
self.succ: ListNode = None
self.data: QuadList = QuadList()
def insert_init_after(self, node):
"""
想节点后方插入一个初始节点（仅包含头尾节点）
:param node:
:return:
"""
self.data.header.insert_below(node.data.header)
self.data.trailer.insert_below(node.data.trailer)
tem = self.succ
self.succ = node
node.prev = self
node.succ = tem
if tem:
tem.prev = node
class SkipList(Dictionary):
def __init__(self):
"""
跳转表，由一个四链表构成，最上端有一个头结点（空）。
"""
self.header = ListNode()
self.header.insert_init_after(ListNode())
self.__size = 0
# 用来记录搜索的结果
self._insert_point: QuadNode = None
def __search(self, point: QuadNode, key):
"""
搜索，使用一个成员变量来记录搜索的结果，
如果成功，则成员变量给定的就是找到的节点，
如果失败，则是要找的节点的前继节点
:param point:
:param key:
:return:
"""
while True:
while point.data and point.data.key <= key:
point = point.succ
point = point.prev
self._insert_point = point
if point.data and point.data.key == key:
# 找到了
return True
# 向下一层
point = point.below
if point is None:
# 到底层了，没有找到
return False
if point.data is None:
point = point.succ
def put(self, key, item):
"""
放置一个新的元素，如果key本身存在，则不存储
:param key:
:param item:
:return:
"""
if not self.__search(self.header.succ.data.header.succ, key):
# 没找着的话
entry = Entry(key, item)
node = QuadNode()
node.data = entry
p = self._insert_point
while p.below:
p = p.below
# 插入点
p.insert_after(node)
self.__size += 1
while random.randint(0, 1):
# 0.5的概率往上涨
# 先找上一层的最近前置节点
p = node.prev
while True:
if p.above and p.data:
p = p.above
break
if p.data is None:
p = p.above
if not p.above:
self.header.insert_init_after(ListNode())
p = self.header.succ.data.header
break
p = p.prev
tem = QuadNode()
tem.data = entry
p.insert_after(tem)
node.insert_above(tem)
node = tem
def get(self, key):
if self.__search(self.header.succ.data.header.succ, key):
return self._insert_point.data.value
def remove(self, key):
if self.__search(self.header.succ.data.header.succ, key):
res = self._insert_point.data.value
p = self._insert_point
self.__size -= 1
while p.below:
p = p.below
while p:
prev = p.prev
succ = p.succ
prev.succ = succ
succ.prev = prev
p = p.above
return res
def size(self):
return self.__size