散列表支持非常高效的数据插入、删除、查找操作，但是散列表中的数据都是通过散列函数打乱之后无规律的存储的，无法支持按照某种顺序快速地遍历数据。如果希望按照顺序遍历散列表中的数据，需要将散列表中的数据拷贝到数组中，然后排序再遍历。
散列表是动态数据结构，不停地有数据的插入、删除，每次希望按顺序遍历散列表中的数据的时候，都需要先排序，效率很低，为了解决这个问题，将散列表和链表（或者跳表）结合在一起使用。
LRU缓存淘汰算法
通过链表实现LRU缓存淘汰算法：维护一个按照访问时间从大到小有序排列的链表结构。因为缓存大小有限，当缓存空间不够，需要淘汰一个数据的时候，直接将链表头部的结点删除。
当要缓存某个数据的时候，先在链表中查找这个数据。如果没有找到，则直接将数据放到链表的尾部；如果找到了，就把它移动到链表的尾部。因为查找数据需要遍历链表，所以单纯使用链表实现的LRU缓存淘汰算法的时间复杂度很高为O(n)。将散列表和链表两种结构组合使用，可以将添加、删除、查找操作的时间复杂度都降低到O(1)。使用双向链表存储数据，链表中的每个节点除了存储数据data、前驱指针prev、后继指针next之外，还新增了一个特殊的字段hnext。这里的散列表通过链表法解决散列冲突，每个节点会在两条链中。一个链式双向链表，一个是散列表中的拉链。前驱和后继指针将结点串在双向链表中，hnext指针将结点串在散列表的拉链中。
- 查找数据，散列表中查找数据的时间复杂度为O(1)。找到数据之后将其移动到双向链表的尾部。
- 删除数据，散列表中在O(1)时间复杂度里找到要删除的结点，双向链表中通过前驱指针O(1)时间复杂度获取前驱结点。则删除结点的时间复杂度为O(1)。
- 添加数据，先判断数据是否已经在缓存中。如果存在，需要将其移动到双向链表的尾部；如果不存在，判断缓存是否已满，如果已满，则将双向链表头部的结点删除在将数据放到链表的尾部，如果未满，则直接将数据放到链表的尾部。
涉及查找操作都通过散列表来完成，其他删除、插入操作通过链表来完成，只需更改指针指向。时间复杂度都为O(1)。
Redis有序集合
有序集合中，每个成员对象有两个重要的属性，键值key和分值score，可以通过score查找数据，也可以通过key来查找数据。
按照分值将对象组织成跳表的结构
按照键值构建一个散列表
LinkedHashMap
通过散列表和双向链表组合实现。Linked指的是双向链表，并非指用链表法解决散列冲突。
不仅支持按照插入顺序遍历数据，还支持按照访问数据遍历数据。
1 | // 10是初始大小，0.75是装载因子，true是表示按照访问时间排序 |