散列是一种将key通过某种散列函数映射到数组的数据结构，又叫 Hash Table。
散列函数是将key通过运算得到散列值的映射函数，有如下要求:
- 散列函数计算得到的散列值是一个非负整数
- 如果 key1 = key2 ， 那么 hash(key1) == hash(key2)
- 如果 key1 != key2, 那么hash(key1) != hash(key2)
散列函数设计的再好也避免不了散列冲突，解决散列冲突通常两种办法：开放寻址法和链表法
开放寻址法的思想是，如果出现了散列冲突，就重新探测一个空闲位置。探测空闲位置的方式常见的也是最简单的就是线性探测：如果发现了散列冲突，就按着顺序向后找一个空闲位置插入。
链表法是将散列表中每个 slot 对应一条链表，所有散列值相同的元素都放到相同 slot 的链表中:
散列表常与链表一起使用，让链表具有数组的随机访问属性
LRU的实现就是一个散列表加上一个链表， 通过散列表快速定位到 Node 的位置， 然后用链表记录 Node 的访问顺序:
可以看到上图除了 prev 和 next 指针，还有一个hnext指针。 prev 和 next 维护了一个双向的访问顺序链表， 而hnext则负责将Node串在散列的拉链中。
除了LRU之外，Redis的有序集合(zset)也是使用了跳表。