数据结构与算法Day16----散列表（下）数据结构与算法Day16----散列表

一、LRU(Least recently used,最近最少使用)缓存淘汰算法： 1、仅使用链表：
【数据结构与算法Day16----散列表（下）】??维护一个按照访问时间从大到小有序排列的链表结构。因为缓存大小有限，当缓存空间不够，需要淘汰一个数据的时候，我们就直接将链表头部的结点删除。当要缓存某个数据的时候，先在链表中查找这个数据。如果没有找到，则直接将数据放到链表的尾部；如果找到了，我们就把它移动到链表的尾部。因为查找数据需要遍历链表，所以单纯用链表实现的LRU缓存淘汰算法的时间复杂很高，是O(n)。
2、散列表和链表两种数据结构组合使用：
<1>、可以将这三个操作的时间复杂度都降低到O(1)。 <2>、具体结构：
文章图片
18599817-6725ca82e5c81bc9.png ??使用双向链表存储数据，链表中的每个结点处理存储数据（data）、前驱指针（prev）、后继指针（next）之外，还新增了一个特殊的字段hnext。因为我们的散列表是通过链表法解决散列冲突的，所以每个结点会在两条链中。一个链是刚刚我们提到的双向链表，另一个链是散列表中的拉链。前驱和后继指针是为了将结点串在双向链表中， hnext指针是为了将结点串在散列表的拉链中。
二、Redis有序集合： 1、集合的构成：
??在有序集合中，每个成员对象有两个重要的属性， key（键值）和score（分值）。
2、相关操作：
??①、添加一个成员对象；
??②、按照键值来删除一个成员对象；
??③、按照键值来查找一个成员对象；
??④、按照分值区间查找数据；
??⑤、按照分值从小到大排序成员变量；
三、HaLinkedHashMap： 1、实现方式：
??LinkedHashMap是通过散列表和链表组合在一起实现的。不仅支持按照插入顺序遍历数据，还支持按照访问顺序来遍历数据。
2、这段代码打印顺序分析：

// 10是初始大小， 0.75是装载因子， true是表示按照访问时间排序 HashMap m = new LinkedHashMap<>(10, 0.75f, true); m.put(3, 11); m.put(1, 12); m.put(5, 23); m.put(2, 22); m.put(3, 26); m.get(5); for (Map.Entry e : m.entrySet()) { System.out.println(e.getKey()); }

每次调用put()函数，往LinkedHashMap中添加数据的时候，都会将数据添加到链表的尾部，所以，在前四个操作完成之后，链表中的数据是下面这样：