org.apache.activemq.util

Class LFUCache<Key,Value>

java.lang.Object

org.apache.activemq.util.LFUCache<Key,Value>

All Implemented Interfaces:

java.util.Map<Key,Value>

public class LFUCache<Key,Value>
extends java.lang.Object
implements java.util.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

Nested Class Summary

Nested classes/interfaces inherited from interface java.util.Map

java.util.Map.Entry<K,V>

Constructor Summary

Constructors

Constructor and Description
LFUCache(int maxCacheSize, float evictionFactor)

Method Summary

Methods

Modifier and Type	Method and Description
void	clear()
boolean	containsKey(java.lang.Object o)
boolean	containsValue(java.lang.Object o)
java.util.Set<java.util.Map.Entry<Key,Value>>	entrySet()
int	frequencyOf(Key k)
Value	get(java.lang.Object k)
boolean	isEmpty()
java.util.Set<Key>	keySet()
Value	put(Key k, Value v)
void	putAll(java.util.Map<? extends Key,? extends Value> map)
Value	remove(java.lang.Object k)
int	size()
java.util.Collection<Value>	values()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface java.util.Map

equals, hashCode

Constructor Detail

LFUCache

public LFUCache(int maxCacheSize,
        float evictionFactor)

Method Detail

put

public Value put(Key k,
        Value v)

Specified by:

put in interface java.util.Map<Key,Value>

putAll

public void putAll(java.util.Map<? extends Key,? extends Value> map)

Specified by:

putAll in interface java.util.Map<Key,Value>

get

public Value get(java.lang.Object k)

Specified by:

get in interface java.util.Map<Key,Value>

remove

public Value remove(java.lang.Object k)

Specified by:

remove in interface java.util.Map<Key,Value>

frequencyOf

public int frequencyOf(Key k)

clear

public void clear()

Specified by:

clear in interface java.util.Map<Key,Value>

keySet

public java.util.Set<Key> keySet()

Specified by:

keySet in interface java.util.Map<Key,Value>

values

public java.util.Collection<Value> values()

Specified by:

values in interface java.util.Map<Key,Value>

entrySet

public java.util.Set<java.util.Map.Entry<Key,Value>> entrySet()

Specified by:

entrySet in interface java.util.Map<Key,Value>

size

public int size()

Specified by:

size in interface java.util.Map<Key,Value>

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface java.util.Map<Key,Value>

containsKey

public boolean containsKey(java.lang.Object o)

Specified by:

containsKey in interface java.util.Map<Key,Value>

containsValue

public boolean containsValue(java.lang.Object o)

Specified by:

containsValue in interface java.util.Map<Key,Value>