词典类型

• 定义，这样一类数据类型，它支持按照键值进行获取元素；

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碰撞的方式，常见的有如下两种：

1. 开放寻址法，即当发现hash冲突后，通过一定的手段再次获取hash值，一直到没有冲突为止，例如可以准备多个hash算法，或者对计算出来的hash值再次计算hash，这样来获取新的索引，也可以直接从当前索引开始向后逐个寻找，找到第一个空为止，就把元素放进去，java中的ThreadLocal中的hashMap就是采用这样的方式来处理hash冲突问题的，好处是简单，并且向后逐个探查的方式有利于CPU的读取（顺序读取数据），同时简单的存储结构更加有利于序列化；
2. 链表法，相同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