LRU缓存机制在操作系统和其他缓存系统中常会用到，这里的题目要求是：1、以整数key，value键值对的形式进行存取；2、以一定的容量进行初始化；3、实现get和put操作，如果get传入的key有对应的value值则返回value，否则返回-1，put如果已经有key对应的cache，则更新value值，如果put时容量超限，则逐出最久未使用的关键字。并要求这些实现在O(1)的复杂度里完成。有名的缓存系统redis就是基于LRU的缓存机制实现的。
这道题如果读者没有较为系统的学习和刷题数据结构和算法，也许想不到用哈希表和双向链表相结合去实现，这道题目是数据结构的一道综合题在实际场景下的应用，主要考察两个点，1、哈希函数的即时O(1)时间复杂度寻址能力及其实现（哈希函数功能可以直接用unordered_map数据结构来实现）；2、双向链表的实现，双向链表支持从中间任何位置挪出节点并放置到表头，双向链表的表头和表尾的节点都可以作为哨兵节点（用变量存储head和tail），这样双向链表就方便实现O(1)时间内移动节点。这里补充下hash函数和双向链表的的相关知识细节供大家参考，欢迎读者关于这些内容提出问题和意见建议。
首先哈希函数可以将整数或字符串进行映射为特定范围内的整数值(取模运算，字符串作为输入的哈希函数有多种，如简单的将每个字符的ascii相加等），这样就可能存在着不同的输入值映射为相同结果的可能（如15%10和25%10都等于5）。这样不同的输入映射到同一个结果就需要解决冲突问题（hash collision)，解决hash冲突的方法有链式地址法(chaining)和开放寻址法（open addressing）。链式地址法的思想是相同结果的输入(key)所对应的value（基础树类型外也支持任何可扩展的灵活自定义的类型）值存放到该hash函数结果对应的链表中（hash函数的结果值表示的含义是以链表的节点指针类型申请的数组对应的位置的下标索引，hash值所对应的数组位置存放链表的表头）。开放寻址法的思想是通过探查（probe）去按一定的规则继续寻找可能的空闲位置，常见的探查方法有一次探查（linear probing，即索引逐渐加1直至找到），二次探查（quadratic probing，逐渐加2的次方直至找到空闲位置）以及双重哈希（两个哈希函数，第一个用来计算初始映射位置，如出现冲突，则第二函数用来计算索引的搜索步长）。在标准模板库中提供了hash函数std:hash。unordered_map提供了灵活的使用哈希函数的方式，既可以用标准提供的，也可以用自定义的。
双向链表的实现也在这里做一下简要说明，双向链表的每一个节点都会保存两个临近节点的指针，即前驱节点和后继节点（头节点的前驱节点为空，尾节点的后续节点为空，如果是双向循环链表，则首尾相连，头节点的前驱节点为尾节点，尾节点的后继节点为头节点）。在本题中，双向链表的表尾节点为记录最久未访问的key（可以理解为双向链表从表头到表尾按时间先后顺序记录着这些key的访问记录），如果缓存已满，则需要将表尾节点更新为表头节点（key和value值用最近访问的值去更新），表尾的前置节点更新为表尾节点。这里为了直接能访问表尾节点，需要在程序中将表尾节点也作为哨兵节点。如果get的key为中间某个节点，则可以通过hash函数首先找到该节点，并将该节点挪动到表头更新为表头节点，同时也说明当前的key是最近访问的。实现了LRU的按时间排序访问节点的功能，并且由于hash函数的O(1)复杂度特性，也保证了LRU的O(1)访问效率要求。
References
Leave a Reply