18散列表
散列表(哈希表)
表示一种映射关系的线性表
把“长”的值,映射到“短”的key,存到数组中,通过数组索引,快速访问与操作
散列冲突解决方法
- 开发寻址发
- 地址产生冲突,往下找,直到有空位,插入,否则散列表满了
- 链表法
- 散列表数组对应一条链表,冲突往链上加
word文档中单词拼写检查功能是如何实现的?
当用户输入某个英文单词时,我们拿用户输入的单词去散列表中查找。如果查到,则说明拼写正确;如果没有查到,则说明拼写可能有误,给予提示。借助散列表这种数据结构,我们就可以轻松实现快速判断是否存在拼写错误。
为什么散列表和链表经常一起使用?
散列表,采用连续空间存储, 优势:支持随机访问值 劣势:添加和删除元素需要移动排序在其后面的数据,效率低,扩容消耗空间大
链表,采用不连续的空间存储, 优势:添加和删除元素方便,扩容简单只需要增加链表长度 劣势:不支持随机访问,需要遍历链表才能找到需要的值 双向链表,用空间换时间的思想解决后继节点不能查找前继节点的问题
LRU缓存淘汰算法
我们需要实现一个缓存算法,用队列来实现。借助散列表,可以把算法时间复杂度降到O(1)。
我们需要维护一个按照访问时间从大到小排序的链表结构。当缓存空间不够,需要淘汰一个数据时,直接将链表头节点删掉。
当要缓存某个数据时,先在链表中查找这个数据。如果没有找到,则直接将数据放到尾部;如果找到了,把它移动到链表的尾部。因为查找需要遍历链表,单纯用链表实现LRU缓存淘汰算法时间复杂度很高,是O(n)。
一个缓存系统主要包括下面几个操作:
- 往缓存中添加一个数据
- 从缓存中删除一个数据
- 在缓存中查找一个数据
这三个操作都设计“查找”操作,如果单纯的采用链表,时间复杂度是O(n)。如果我们将散列表和链表两种数据结构结合使用,可以将这三个操作时间复杂度降低到O(1)。具体的结构是下面这个样子:

我们使用双向链表存储数据,链表中每个节点处理数据存储(data)、前驱指针(prev)、后继指针(next),还新增了一个特殊字段hnext,这个hnext有什么作用呢?
因为我们的散列表是通过链表法解决散列冲突的,所以每个节点会再两条链中。一条链式双向链表,另一条是散列表的拉链。前驱和后继指针是为了将节点串在双向链表中,hnext指针是为了将节点串在散列表的拉链中。