ARTICLES

460 LFU Cache

By adam

Requirements

  • O(1) insertion
    • requires O(1) getting the least frequently used

Suggested data structures

  • f: a map from frequency to a tuple containing the head and tail of a portion of a double linked list
  • kv: a map from key to a node in the double linked list
  • dll: a double linked list where the least frequent item is at the head of the list
  • node: element of dll, containing frequency info, as well a prev, next, value, the usual stuff

put(a,v)

  1. find corresponding node via kv[a]
  2. delete head of double linked list and update f accordingly
  3. delete node from its current position and insert it at the head of the next frequency, i.e. f[freq+1].head
  4. update its value

get(a)

same as put(a,v), but don’t delete LFU node, or update its value, just return it

some things to take care of

  1. if a not in kv
  2. if there is no entry for f[freq+1]

comments

I tried to make this as simple as possible, if you have some other ideas please let me know.