LFU缓存的get与set操作如何实现O(1)时间复杂度？

Great question—LFU (Least Frequently Used) is definitely trickier than LRU because we have to track access frequencies and handle ties when multiple keys share the lowest frequency. Let’s break down the data structure combo and operations that make both get and set run in constant time.

Core Data Structures #

To pull off O(1) operations, you’ll need three components working together:

• Key-to-Node Hash Map: Maps each cache key to a custom node object. Each node stores:
  • The key and value
  • Its current access frequency
  • Pointers to the previous and next nodes in a doubly linked list (for O(1) insertion/deletion)
• Frequency-to-List Hash Map: Maps each frequency value to a doubly linked list. All nodes with that exact frequency live in this list. This lets us quickly access all nodes with the lowest frequency when we need to evict.
• Minimum Frequency Tracker: A variable that keeps track of the current lowest frequency in the cache. This avoids having to iterate through all frequencies to find the minimum every time we need to evict.

Step-by-Step Operation Breakdown #

get(int key)

1. Check existence: If the key isn’t in the key-to-node map, return -1 immediately.
2. Retrieve and update the node:
   • Pull the node from the key map.
   • Remove it from its current frequency’s linked list (using the node’s prev/next pointers—O(1) operation).
   • If the list we just emptied was the one corresponding to min_freq, increment min_freq by 1 (since that frequency no longer has any nodes).
   • Increment the node’s frequency by 1.
   • Add the node to the linked list for its new frequency (create the list in the frequency map if it doesn’t exist yet).
3. Return the value: Return the node’s stored value.

set(int key, int value)

1. Check if key exists:
   • If it does, follow the same frequency update steps as get, then update the node’s value to the new one. Done.
2. Handle new key:
   • Evict if necessary: If the cache is at capacity:
     • Grab the linked list corresponding to min_freq.
     • Remove the tail node of this list (since within the same frequency, we evict the least recently used entry—using the tail ensures we get the oldest one).
     • Delete this evicted key from the key-to-node map.
   • Create new node: Make a new node with the key, value, and frequency set to 1.
   • Add to maps: Insert the node into the key-to-node map, and add it to the linked list for frequency 1 (create the list if needed).
   • Reset min_freq: Set min_freq to 1—since the new node has the lowest possible frequency.

Why This Is All O(1) #

• Hash map operations (lookup, insert, delete) are O(1) average case.
• Doubly linked list operations (remove a node given pointers, add to head/tail) are O(1).
• Updating the min_freq variable is just a simple integer operation, no loops involved.

The key insight is that we never have to iterate through all keys or frequencies—every operation relies on direct lookups and constant-time list manipulations.

内容的提问来源于stack exchange，提问作者Jimbo