LRU Cache


Source: LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

  • get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

  • set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.


  • Use HashMap to cache key and value.
  • Use PriorityQueue to mark LRU item as the hottest. Drop coldest element when over capacity.

A Java Solution

class Item {
  int key;
  int value;
  Item prev;
  Item next;
  public Item(int key, int value) {
    this.key = key;
    this.value = value;
    this.prev = null; = null;
class LRUList {

  Item head = null, tail = null;
  int current_capacity = 0;

  public LRUList() {
    head = new Item(-1, -1);
    tail = new Item(-1, -1); = tail;
    head.prev = null; = null;
    tail.prev = head;

  public void update(Item item) { // SHIT: public update(Item item)
    Item orig_prev = item.prev;
    Item orig_next =; = orig_next;
    orig_next.prev = orig_prev;

  public void insert(Item item) {
    Item first =; = item;
    item.prev = head;
    first.prev = item; = first;

  public void delete(Item item) {
    Item orig_prev = item.prev;
    Item orig_next =; = orig_next;
    orig_next.prev = orig_prev;
    item = null;

  public void deleteTail() {

public class LRUCache {
  Map<Integer, Item> map;
  LRUList list;
  int total;
  int capacity;

  public LRUCache(int capacity) { = new HashMap<Integer, Item>(capacity);
    this.list = new LRUList(); = 0;
    this.capacity = capacity;

  public int get(int key) {
    Item item =;
    if (item == null) {
      return -1;
    return item.value;

  public void set(int key, int value) {
    Item item =;
    if (item == null) {
      item = new Item(key, value);
      this.list.insert(item);, item);;
      if ( > this.capacity) {
        Item last = this.list.tail.prev;
    } else {
      item.value = value;



It’s difficult to participate in Clojure’s abstraction for lacking of documentations. Anyway, a helper function from clojure programming is really useful for us to dive into it.

(defn scaffold
"Given an interface, returns a 'hollow' body suitable for use with `deftype`." [interface]
(doseq [[iface methods] (->> interface
(map #(vector (.getName (.getDeclaringClass %))
(symbol (.getName %))
(count (.getParameterTypes %)))) (group-by first))]
(println (str " " iface))
(doseq [[_ name argcount] methods]
(str " "
(list name (into '[this] (take argcount (repeatedly gensym)))))))))

By looking at the output of the ancestors and methods of them, we can determine what to do next:

user=> (scaffold clojure.lang.IPersistentMap)
 (assoc [this G__809 G__810])
 (without [this G__811])
 (assocEx [this G__812 G__813])

 (iterator [this])

 (entryAt [this G__814])
 (assoc [this G__815 G__816])
 (containsKey [this G__817])

 (empty [this])
 (equiv [this G__818])
 (count [this])
 (cons [this G__819])

 (seq [this])

 (valAt [this G__820])
 (valAt [this G__821 G__822])

 (count [this])

To implement a LRU Cache, we need to implement those methods. Some trival knowledge:

  • cons is the name that backs conj;
  • equiv is similar to equals, but ensures sane equivalence semantics when applied to numerics
  • There is two assoc definition, but only 1 is available. The one in clojure.lang.Associative will be replaced by clojure.lang.IPersistentMap. That means we only need to implement the one in clojure.lang.Associative.
  • Nothing ever uses assocEx anymore. It is a remnant of an earlier time. If you are writing your own map type, you can implement (assocEx [m k v] (throw (Exception.))).1


(defprotocol CacheProtocol
  "This is the protocol describing the basic cache capability."
  (lookup [cache e]
          [cache e not-found]
   "Retrieve the value associated with `e` if it exists, else `nil` in
   the 2-arg case.  Retrieve the value associated with `e` if it exists,
   else `not-found` in the 3-arg case.")
  (has?    [cache e]
   "Checks if the cache contains a value associated with `e`")
  (hit     [cache e]
   "Is meant to be called if the cache is determined to contain a value
   associated with `e`")
  (miss    [cache e ret]
   "Is meant to be called if the cache is determined to **not** contain a
   value associated with `e`")
  (evict  [cache e]
   "Removes an entry from the cache")
  (seed    [cache base]
   "Is used to signal that the cache should be created with a seed.
   The contract is that said cache should return an instance of its
   own type."))

(deftype LRUCache
  [cache lru limit]

   [this key]
   (lookup this key))
   [this key not-found]
   (if (has? this key)
     (lookup this key)

  (assoc [this key value]
    (miss this key value))
  (without [this key]
    (evict this key))

   [this key]
   (has? this key))
   [this key]
   (when (has? this key)
     (clojure.lang.MapEntry. key (lookup this key))))

   [this elem]
   (seed this (conj cache elem)))
   (seed this (empty cache)))
   [this other]
   (= other cache))

  (seq [this]
       (seq cache))

   [this key]
   (get cache key))
   [this key not-found]
   (get cache key not-found))
   [this key]
   (contains? cache key))
   [this key]
   (LRUCache. cache
              (if (contains? cache key)
                (for [k lru :when (not= k key)] k)
   [this key value]
   (if (>= (count lru) limit)
     (let [miss-key (if (some #{key} lru)
                      (last lru))]
       (println (-> cache (dissoc miss-key) (assoc key value)))
       (LRUCache. (-> cache (dissoc miss-key) (assoc key value))
                  (conj (for [k lru :when (not= k miss-key)]  k) key)
     (LRUCache. (assoc cache key value)
                (conj lru key)
   [this key]
   (let [v (get cache key ::miss)]
     (if (= v ::miss)
       (LRUCache. (dissoc cache key)
                  (for [k lru :when (not= k key)] k)
   [this key]
   (LRUCache. cache

   (str cache \, \space lru \, \space limit)))

(defn lru-cache-factory
  (LRUCache. {} (clojure.lang.PersistentQueue/EMPTY) limit))


  • LRU remove: O(N). A better solution is using PriorityDataStructure to reduce to O(1).
  • Use Memcached or Redis to replace clojure map and list for better scalable.
  • Why not rebuild a wheel?