com.aliasi.util
Class HardFastCache<K,V>

java.lang.Object
  extended by java.util.AbstractMap<K,V>
      extended by com.aliasi.util.HardFastCache<K,V>
Type Parameters:
K - the type of keys in the map
V - the type of values in the map
All Implemented Interfaces:
Map<K,V>

public class HardFastCache<K,V>
extends AbstractMap<K,V>

A HardFastCache is a map implemented with hard references, optimistic copy-on-write updates, and approximate count-based pruning. It is intended for scalable multi-threaded caches. It sacrifices recall of mappings for speed of put and get operations along with conservative memory guarantees.

Note: The class FastCache is nearly identical, but with hash buckets wrapped in soft references for automatic resizing by the garbage collector.

The basis of the cache is a fixed-size hash map, based on values returned by objects' hashCode() and equals(Object) methods.

The map entries in the hash map are stored in buckets held by ordinary references. Thus entries in the mapping may be garbage collected. In the implementation, whole hash buckets are collected, which is safe and highly efficient but may require some additional recomputation of values that were removed by pruning.

Entries are stored in the map using a very optimistic update. No synchronization at all is performed on the cache entries or their counts. A copy-on-write strategy coupled with Java's memory model for references ensures that the cache remains consistent, if not complete. What this means is that multiple threads may both try to cache a mapping and only one will be saved and/or incremented in count.

When the table approximately exceeds the specified load factor, the thread performing the add will perform a garbage collection by reducing reference counts by half, rounding down, and removing entries with zero counts. Pruning is subject to the caveats mentioned in the last paragraph. Counts are not guaranteed to be accurate. Pruning itself is synchronized and more conservatively copy-on-write. By setting the load factor to Double.POSITIVE_INFINITY there will be never be any pruning done by this class.

A fast cache acts as a mapping with copy-on-write semantics. Equality and iteration are defined as usual, with the caveat that the snapshot taken of the elements may not be up to date. Iterators may be used concurrently, but their remove methods do not affect the underlying cache. For information on copy-on-write and optimistic updates, see section 2.4 of:

Since:
LingPipe3.5.1
Version:
3.8.3
Author:
Bob Carpenter

Nested Class Summary
 
Nested classes/interfaces inherited from interface java.util.Map
Map.Entry<K,V>
 
Constructor Summary
HardFastCache(int size)
          Constrcut a fast cache of the specified size and default load factor.
HardFastCache(int size, double loadFactor)
          Construct a fast cache of the specified size and load factor.
 
Method Summary
 Set<Map.Entry<K,V>> entrySet()
          Returns a snapshot of the entries in this map.
 V get(Object key)
          Returns the value of the specified key or null if there is no value attached.
 void prune()
          Prunes this cache by (approximately) dividing the counts of entries by two and removing the ones with zero counts.
 V put(K key, V value)
          Sets the value of the specified key to the specified value.
 
Methods inherited from class java.util.AbstractMap
clear, clone, containsKey, containsValue, equals, hashCode, isEmpty, keySet, putAll, remove, size, toString, values
 
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
 

Constructor Detail

HardFastCache

public HardFastCache(int size)
Constrcut a fast cache of the specified size and default load factor. The default load factor is 0.5.

Parameters:
size - Size of cache.
Throws:
IllegalArgumentException - if the size is less than 2.

HardFastCache

public HardFastCache(int size,
                     double loadFactor)
Construct a fast cache of the specified size and load factor. The size times the load factor must be greater than or equal to 1. When the (approximate) number of entries exceeds the load factor times the size, the cache is pruned.

Parameters:
size - Size of the cache.
loadFactor - Load factor of the cache.
Throws:
IllegalArgumentException - If the size times the load factor is less than one.
Method Detail

get

public V get(Object key)
Returns the value of the specified key or null if there is no value attached. Note that the argument is not the generic <K> key type, but Object to match the requirements of java.util.Map.

Warning: Because of the approximate cache-like behavior of this class, key-value pairs previously added by the put(Object,Object) method may disappear.

Specified by:
get in interface Map<K,V>
Overrides:
get in class AbstractMap<K,V>
Parameters:
key - Mapping key.
Returns:
The value for the specified key.

put

public V put(K key,
             V value)
Sets the value of the specified key to the specified value. If there is already a value for the specified key, the count is incremented, but the value is not replaced.

Warning: Because of the approximate cache-like behavior of this class, setting the value of a key with this method is not guaranteed to replace older values or remain in the mapping until the next call to get(Object).

Specified by:
put in interface Map<K,V>
Overrides:
put in class AbstractMap<K,V>
Parameters:
key - Mapping key.
value - New value for the specified key.
Returns:
null, even if there is an existing value for the specified key.

prune

public void prune()
Prunes this cache by (approximately) dividing the counts of entries by two and removing the ones with zero counts. If the cache is not full (more entries than size times load factor), no pruning will be done.

Warning: This operation is approximate in the sense that the optimistic update strategy applied is not guaranteed to actually do any pruning or decrements of counts.


entrySet

public Set<Map.Entry<K,V>> entrySet()
Returns a snapshot of the entries in this map. This set is not backed by this cache, so that changes to the cache do not affect the cache and vice-versa.

Specified by:
entrySet in interface Map<K,V>
Specified by:
entrySet in class AbstractMap<K,V>
Returns:
The set of entries in this cache.