LRU Table

in     1 minute read

LRU(Least Recently Used) table is a simple data structure that is composed of hash table and linked list. The insert, erase, lookup/search can be done naturally in O(1) by its hash-table part. But the best thing is, it can return the least or most recently used data in O(1) by the its linked-list in a least-to-most recently used order.

Use Cases

There are several use cases:

  • (LRU) cache:
    • A data cache with limited capacity that only cache the most recently touched \(N\)-element
    • The real worl use case is a mediabuffer with LRU mechanism in chromium
  • Focus problem: Keep tracking the touched elements, in a least-to-most recently used order
    • For example, in browser, we may want to prioritize the elements by the touched-by-user order
    • We can give user a way for a user to control the last touched element. One element at a time.
    • If the last touched element is destroyed, then the user can control the second-last touched element, and so on.

Sample Code

A Simple LRU Table

See the files on gist here.

A LRU table with Key-Value Pair

See the files on gist here.

Practice

Can’t wait to give it a try? Play the leetcode here. There are many ways to implement the LRU cache. Good luck!


  Tagged with  •   •   •