Package org.apache.activemq.util

Class LFUCache<Key,​Value>

  • All Implemented Interfaces:
    Map<Key,​Value>
    public class LFUCache<Key,​Value>
extends Object
implements Map<Key,​Value>
    LFU cache implementation based on http://dhruvbird.com/lfu.pdf, with some notable differences:
    • Frequency list is stored as an array with no next/prev pointers between nodes: looping over the array should be faster and more CPU-cache friendly than using an ad-hoc linked-pointers structure.
    • The max frequency is capped at the cache size to avoid creating more and more frequency list entries, and all elements residing in the max frequency entry are re-positioned in the frequency entry linked set in order to put most recently accessed elements ahead of less recently ones, which will be collected sooner.
    • The eviction factor determines how many elements (more specifically, the percentage of) will be evicted.
    As a consequence, this cache runs in *amortized* O(1) time (considering the worst case of having the lowest frequency at 0 and having to evict all elements).
    Author:
    Sergio Bossa