散列表(下)

Friday, April 26, 2019

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

LRU缓存淘汰算法

先回顾一下LRU缓存淘汰算法,我们需要维护一个按照访问时间从大到小排列的链表结构。因为缓存有限,当缓存不够时,需要淘汰数据的时候,我们就直接将链表头部的节点删除。

如果将散列表和链表组合使用,可以将查找,插入,删除操作都降到复杂度O(1)

file

除了使用双向链表,还增加了一个hnext。 因为我们散列表是通过链表法解决冲突的,所以每个结点会在两条链中,一个是双向链表,几个是链在散列表中的拉链。前驱和后驱是为了将节点串在双向链表中,hnext指针是为了将结点串在散列表的拉链中。

我们首先看看怎么查找数据,通过散列表我们能在O(1)的时间复杂度找到数据,找到之后我们还要将其放入双向链表尾部。

其次怎么删除数据,我们借助散列表找到数据,又因为是双向链表,所以可以通过O(1)获得前驱结点,所以删除节点也只需要O(1)

最后我们看看如何添加数据,我们先查找是否存在,如果存在,将其移到尾部,如果不在,还要看缓存,如果满了,将链表头部删除,再在尾部插入。如果没有满,则直接插入尾部。

所以,通过上述方法,我们就能实现一个都是O(1)的高效LRU

JAVA LinkedHashMap

HashMap是通过散列表实现的,但LinkedHashMap不仅仅代表它是通过链表法解决散列冲突。

LinkedHashMap 打印数据会按照插入顺序打印。它不仅仅支持按照插入顺序遍历数据,还支持按照访问顺序遍历数据。

每次put数据进去,都会将数据添加到链表尾部。

file

将(3,11)删除,并将(3,26)插入

file

后面同理处理key为5的数据

file

通过上面发现,这就是一个支持LRU缓存淘汰策略的huan’cun缓存系统。

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

数据结构-算法

二叉树基础(上)

散列表(中)