美文网首页
散列表(下)为什么散列表和链表经常会一起使用?

散列表(下)为什么散列表和链表经常会一起使用?

作者: 尼桑麻 | 来源:发表于2019-05-29 11:43 被阅读0次

    一、为什么散列表和链表经常放在一起使用?

    1.散列表的优点:支持高效的数据插入、删除和查找操作
    2.散列表的缺点:不支持快速顺序遍历散列表中的数据
    3.如何按照顺序快速遍历散列表的数据?只能将数据转移到数组,然后排序,最后再遍历数据。
    4.我们知道散列表是动态的数据结构,需要频繁的插入和删除数据,那么每次顺序遍历之前都需要先排序,这势必会造成效率非常低下。
    5.如何解决上面的问题呢?就是将散列表和链表(或跳表)结合起来使用。

    二、散列表和链表如何组合起来使用?

    LRU缓存淘汰算法

    借助散列表,我们可以把LRU缓存淘汰算法的时间复杂度降低为O(1)。
    首先,我们来回顾一下当时我们是如何通过链表实现LRU缓存淘汰算法的。
    我们需要维护一个按照访问时间从大到小有序排列的链表结构。因为缓存大小有限,当缓存空间不够,需要淘汰一个数据的时候,我们就直接将链表头部的结点删除。
    当要缓存某个数据的时候,先在链表中查找这个数据。如果没有找到,则直接将数据放到链表的尾部;如果找到了,我们就把它移动到链表的尾部。因为查找数 据需要遍历链表,所以单纯用链表实现的LRU缓存淘汰算法的时间复杂很高,是O(n)。
    实际上,我总结一下,一个缓存(cache)系统主要包含下面这几个操作:
    1.往缓存中添加一个数据;
    2.从缓存中删除一个数据;
    3.在缓存中查找一个数据。
    这三个操作都要涉及“查找”操作,如果单纯地采用链表的话,时间复杂度只能是O(n)。如果我们将散列表和链表两种数据结构组合使用,可以将这三个操作的时间 复杂度都降低到O(1)。
    具体的结构就是下面这个样子:


    image.png

    我们使用双向链表存储数据,链表中的每个结点处理存储数据(data)、前驱指针(prev)、后继指针(next)之外,还新增了一个特殊的字段hnext。这个hnext有 什么作用呢?
    因为我们的散列表是通过链表法解决散列冲突的,所以每个结点会在两条链中。一个链是刚刚我们提到的双向链表,另一个链是散列表中的拉链。前驱和后继指针是为了将结点串在双向链表中,hnext指针是为了将结点串在散列表的拉链中。 了解了这个散列表和双向链表的组合存储结构之后,我们再来看,前面讲到的缓存的三个操作,是如何做到时间复杂度是O(1)的?
    首先,我们来看如何查找一个数据。我们前面讲过,散列表中查找数据的时间复杂度接近O(1),所以通过散列表,我们可以很快地在缓存中找到一个数据。当找 到数据之后,我们还需要将它移动到双向链表的尾部。
    其次,我们来看如何删除一个数据。我们需要找到数据所在的结点,然后将结点删除。借助散列表,我们可以在O(1)时间复杂度里找到要删除的结点。因为我们 的链表是双向链表,双向链表可以通过前驱指针O(1)时间复杂度获取前驱结点,所以在双向链表中,删除结点只需要O(1)的时间复杂度。
    最后,我们来看如何添加一个数据。添加数据到缓存稍微有点麻烦,我们需要先看这个数据是否已经在缓存中。如果已经在其中,需要将其移动到双向链表的尾
    部;如果不在其中,还要看缓存有没有满。如果满了,则将双向链表头部的结点删除,然后再将数据放到链表的尾部;如果没有满,就直接将数据放到链表的尾
    部。
    这整个过程涉及的查找操作都可以通过散列表来完成。其他的操作,比如删除头结点、链表尾部插入数据等,都可以在O(1)的时间复杂度内完成。所以,这三个 操作的时间复杂度都是O(1)。至此,我们就通过散列表和双向链表的组合使用,实现了一个高效的、支持LRU缓存淘汰算法的缓存系统原型。

    结论:

    散列表这种数据结构虽然支持非常高效的数据插入、删除、查找操作,但是散列表中的数据都是通过散列函数打乱之后无规律存储的。也就说,它无法支持按照某种顺序快速地遍历数据。如果希望按照顺序遍历散列表中的数据,那我们需要将散列表中的数据拷贝到数组中,然后排序,再遍历。
    因为散列表是动态数据结构,不停地有数据的插入、删除,所以每当我们希望按顺序遍历散列表中的数据的时候,都需要先排序,那效率势必会很低。为了解决这个问题,我们将散列表和链表(或者跳表)结合在一起使用。

    扩展阅读:

    LinkedHashMap https://blog.csdn.net/a724888/article/details/80290276

    相关文章

      网友评论

          本文标题:散列表(下)为什么散列表和链表经常会一起使用?

          本文链接:https://www.haomeiwen.com/subject/bkretctx.html