LRU

LRU (Least recently used) §

LRU，最近最小使用算法，是一种缓存淘汰算法，淘汰最久没有被使用的数据。

LRU 数据结构实现 §

LRU 可以使用链表加哈希表的数据结构实现。其中，如果链表使用单链表，数据查询和数据插入的时间复杂度都为O(n)；如果链表使用双链表，可以将查询和插入的时间复杂度减小到O(1)。

通过链表的数据结构来保证数据的有序性，实现按最长未使用时间的排序。哈希表的 key 即为数据的 key，value 存储数据对应的双链表节点，哈希表的作用是降低查询的时间复杂度。