TLDR: Implementing LFU in O(1)

Date: 2020-08-23 Source: https://arpitbhayani.me/blogs/lfu

Overview

Explore constant time LFU cache implementation using hash tables and doubly-linked lists. Learn how to achieve O(1) complexity! A common strategy to make any system super-performant is Caching).

Key Points

• A common strategy to make any system super-performant is Caching).
• The Hash Table: The Hash Table stores the mapping of the cached key to the Value Node holding the cached value.
• Doubly Linked Lists: This implementation of LFU requires us to maintain one Doubly Linked List of frequencies, called freq_list, holding one node for each unique frequency spanning all the caches values.
• Adding value to the cache: Adding a new value to the cache is a relatively simpler operation that requires a bunch of pointer manipulations and does the job with a constant time running complexity.
• Evicting an item from the cache: Eviction, similar to insertion, is a trivial operation where we simply pick the frequency node with lowest access frequency (the first node in the freq_list) and remove the first Value Node present in its values_list.