Documentation
¶
Overview ¶
Package lfucache implements LFU (Least Frequently Used) cache
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type LFUCache ¶
type LFUCache struct {
sync.RWMutex
cache.UnImplementedCache
// contains filtered or unexported fields
}
LFUCache data structure
func (*LFUCache) Get ¶
Get through checking node[key], we can get the node in O(1) time. Just performs update, then we can return the value of node.
func (*LFUCache) Put ¶
Put If `key` already exists in self._node, we do the same operations as `get`, except updating the node.val to new value. Otherwise 1. if the cache reaches its capacity, pop the least frequently used item. (*) 2. add new node to self._node 3. add new node to the DLinkedList with frequency 1 4. reset minFreq to 1
(*) How to pop the least frequently used item? Two facts: 1. we maintain the minFreq, the minimum possible frequency in cache. 2. All cache with the same frequency are stored as a DLinkedList, with recently used order (Always append at head) 3. The tail of the DLinkedList with minFreq is the least recently used one, pop it.
Source Files