Java教程

[算法整理] 词典类型:hash表和跳转表

本文主要是介绍[算法整理] 词典类型:hash表和跳转表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

词典类型

  • 定义,这样一类数据类型,它支持按照键值进行获取元素;
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

这篇关于[算法整理] 词典类型:hash表和跳转表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!