Tag: Data Structure

双向链表和哈希表实现 LRUCache

背景LRUCache 是一个很常用的缓存实现,本文会首先介绍一下 LRUCache 的定义,然后尝试用 Python 实现它。 定义LRUCache 首先是一个 Cache,那么对于一个 Cache 而言,肯定需要提供 get 和 set 两个方法,而且,这两个方法的时间复杂度越低越好,最好达到 O(1) 级别。 LRU 是 Least Recently Used 的缩写,近期最少使用策略。LRU