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