LRU的O(1)时间复杂度的实现

LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。

不考虑时间和空间复杂度,最简单的实现方式为使用一个双向链表。

由此可见一个双向链表就能解决LRU。但是只能应付数据量小的情况。

交换过程需要先查询key,再进行插入操作,链表中进行查询时间复杂度是O(n)。插入时间复杂度是O(1)。

所以我们需要优化查询的过程,就是使用Hash表。

这样就可以通过key访问对应的链表的节点时间复杂度为O(1),插入的时间复杂度同样为O(1)。

具体实现代码查看Algorithm

You Might Also Like
发表评论