算法学习十五、散列表(下)

LRU 缓存淘汰算法

一个缓存(cache)系统主要包含下面这几个操作:

  • 往缓存中添加一个数据
  • 从缓存中删除一个数据
  • 在缓存中查找一个数据

这三个操作都要涉及“查找”操作,如果单纯地采用链表的话,时间复杂度只能是 O(n)。如果我们将散列表和链表两种数据结构组合使用,可以将这三个操作的时间复杂度都降低到 O(1)。具体的结构就是下面这个样子:

往链表添加元素时,对 data 进行散列,得到散列值,散列值指向双向链表的子链。

双向链表如 LRU 时一样维护,链表中的节点,多了一个 hnext 指向散列冲突的下一个节点。

每个结点会在两条链中。一个链是刚刚我们提到的双向链表,另一个链是散列表中的拉链。前驱和后继指针是为了将结点串在双向链表中,hnext 指针是为了将结点串在散列表的拉链中。

查找一个数据:通过散列表,在缓存中找到一个数据。当找到数据之后,将它移动到双向链表的尾部。需要设置一个尾指针。

Redis 有序集合

在有序集合中,每个成员对象有两个重要的属性,key(键值)和 score(分值)。我们不仅会通过 score 来查找数据,还会通过 key 来查找数据。

仅仅按照分值将成员对象组织成跳表的结构,那按照键值来删除、查询成员对象就会很慢,按照键值构建一个散列表(散列表对应的应该是一个指针)。

Java LinkedHashMap

对于下面一段代码:

// 10是初始大小,0.75是装载因子,true是表示按照访问时间排序
HashMap<Integer, Integer> m = new LinkedHashMap<>(10, 0.75f, true);
m.put(3, 11);
m.put(1, 12);
m.put(5, 23);
m.put(2, 22);


m.put(3, 26);
m.get(5);


for (Map.Entry e : m.entrySet()) {
  System.out.println(e.getKey());

打印的顺序就是 1,2,3,5,并不是打乱的顺序,因为 LinkedHashMap 也是通过散列表和链表组合在一起实现的。

按照访问时间排序的 LinkedHashMap 本身就是一个支持 LRU 缓存淘汰策略的缓存系统。

LinkedHashMap 是通过双向链表和散列表这两种数据结构组合实现的。LinkedHashMap 中的“Linked”实际上是指的是双向链表,并非指用链表法解决散列冲突。

为什么散列表和链表经常一块使用?

散列表这种数据结构虽然支持非常高效的数据插入、删除、查找操作,但是散列表中的数据都是通过散列函数打乱之后无规律存储的。如果希望按照顺序遍历散列表中的数据,那我们需要将散列表中的数据拷贝到数组中,然后排序,再遍历。

为了解决这个问题,我们将散列表和链表(或者跳表)结合在一起使用。