org.ceryle.util
Class HashCache

java.lang.Object
  org.ceryle.util.HashCache

All Implemented Interfaces:

Map

Direct Known Subclasses:

AssertionQueryCache

public class HashCache
extends Object
implements Map

Creates a hash-keyed cache sensitive to access frequency by combining a FrequencyModel (for frequency-sorting the keys) with a Hashtable. Because this is a cache, values are wrapped in WeakReferences so that there is no strong binding that would deter garbage collection due to caching.

Duplicate Key Sets

Since the key table of the Hashtable class is private, unless we wanted to completely rewrite the class to be able to sort the keys, we by necessity must keep a second, sortable key set (implementing List) as found in the FrequencyModel class. Most methods will directly reference the backing Hashtable's keys and values; only those concerned with ranking will use the FrequencyModel's keys.

Just as in Hashtable, as a key is removed from the key set(s), the stored Object is removed from the Hashtable's value set. Any access of a key decreases its ranking (i.e., moves it towards the zeroeth position in the list).

Different Weakness from WeakHashMap

This class is almost an opposite of WeakHashMap since its keys are not weakly linked as in that class, but instead use WeakReferences as links to its values. Keys never expire in this class, only what they reference. Since the initial application for this class was to use Strings (IDs) as keys, a WeakHashMap wouldn't help much.

This class can also be considered an ordered Map, since its keys are sorted according to access frequency.

Changes to the Map API

Please check the notes on each method to see how it may differ from the Map interface, as some methods are effected by the use of the WeakReference storage of values.

IMPORTANT:

Whereas in the Map interface operations (such as remove) are permitted on the values returned by some methods, this class deliberately returns unmodifiable Sets or Collections in those instances to prohibit such changes, since this would potentially put the two key sets out of synchronization. Attempts to modify the backing Collection via the class' access to the Hashtable will result in an UnsupportedOperationException being thrown.

Version:

$Id: HashCache.java,v 3.1 2007-06-15 12:09:55 altheim Exp $

Author:

Murray Altheim

Nested Class Summary

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

Map.Entry<K,V>

Constructor Summary

HashCache()
Constructor for a HashCache.

Method Summary

void	clear() Removes all mappings from this Map (optional operation).
boolean	contains(Object value) Returns true if this Map maps one or more keys to the specified value.
boolean	containsKey(Object key) Returns true if this Map contains a mapping for the specified key.
boolean	containsValue(Object value) Returns true if this Map maps one or more keys to the specified value.
Set	entrySet() Returns a set view of the mappings contained in this Map.
boolean	equals(Object o) Compares the specified object with this Map for equality.
Object	get(Object key) Returns the value to which this Map maps the specified key.
int	hashCode() Returns the hash code value for this Map.
boolean	isEmpty() Returns true if this Map contains no key-value mappings.
Set	keySet() Returns a set view of the keys contained in this Map.
Object	put(Object key, Object value) Associates the specified value with the specified key in this Map (optional operation).
void	putAll(Map t) Copies all of the mappings from the specified Map to this Map (optional operation).
int	rankOf(Object key) Returns the current ranking of Object key as an int.
Object	remove(Object key) Removes the mapping for this key from this Map if it is present (optional operation).
void	setMaximumSize(int max) If the maximum size is set (by default it is not), the list will be auto-trimmed to limit, from the bottom (least popular).
int	size() Returns the number of key-value mappings in this Map.
protected void	trimCache() Trims the bottom off the cache based on the set limit.
Collection	values() Returns a collection view of the values contained in this map.

Methods inherited from class java.lang.Object

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

Constructor Detail

HashCache

public HashCache()

Constructor for a HashCache.

Method Detail

clear

public void clear()

Removes all mappings from this Map (optional operation).

Specified by:

clear in interface Map

See Also:

Map.clear()

containsKey

public boolean containsKey(Object key)

Returns true if this Map contains a mapping for the specified key.

Specified by:

containsKey in interface Map

See Also:

Map.containsKey(Object)

containsValue

public boolean containsValue(Object value)

Returns true if this Map maps one or more keys to the specified value.

Notes

Because the values are stored as WeakReferences this forces a test of all the WeakReference's stored references, which is more expensive than a simple query of the backing Hashtable.

Note that this method is identical in functionality to contains(Object) (which predates the Map interface).

Specified by:

containsValue in interface Map

See Also:

Map.containsValue(Object)

entrySet

public Set entrySet()

Returns a set view of the mappings contained in this Map.

Notes

Note that this returns the entrySet of the backing Hashtable's set of WeakReferences, not the values themselves. Any attempts to modify the entrySet will throw an UnsupportedOperationException.

Specified by:

entrySet in interface Map

See Also:

Changes to API, Map.entrySet()

equals

public boolean equals(Object o)

Compares the specified object with this Map for equality.

Notes

If o is a Map, this as necessary iterates the entire table's dereferenced WeakReferences to match the Map's values.

Specified by:

equals in interface Map

Overrides:

equals in class Object

See Also:

Map.equals(Object)

get

public Object get(Object key)

Returns the value to which this Map maps the specified key.

Notes

This returns the Object dereferenced from the stored WeakReference, which may be null if the reference has expired. Any request on a key is considered as an FrequencyModel.action(Object), which decreases (moves towards zero, the "top" of the list) its ranking.

Specified by:

get in interface Map

See Also:

Map.get(Object)

hashCode

public int hashCode()

Returns the hash code value for this Map.

Notes

This returns the hash code of the backing Hashtable, disregarding the FrequencyModel.

Specified by:

hashCode in interface Map

Overrides:

hashCode in class Object

See Also:

Map.hashCode()

isEmpty

public boolean isEmpty()

Returns true if this Map contains no key-value mappings.

Notes

Note that this returns the size of the backing hashtable and does not take into account any expired WeakReferences.

Specified by:

isEmpty in interface Map

See Also:

Map.isEmpty()

keySet

public Set keySet()

Returns a set view of the keys contained in this Map.

Notes

This returns the keySet of the backing Hashtable. Any attempts to modify the keySet will throw an UnsupportedOperationException.

Specified by:

keySet in interface Map

See Also:

Changes to API, Map.keySet()

put

public Object put(Object key,
                  Object value)

Associates the specified value with the specified key in this Map (optional operation).

Notes

This stores the key in both the FrequencyModel and the Hashtable. If the cache's maximum size has been set this may remove Objects from the bottom of the list (the largest rankings in the list).

Specified by:

put in interface Map

See Also:

Map.put(Object,Object)

putAll

public void putAll(Map t)

Copies all of the mappings from the specified Map to this Map (optional operation).

Specified by:

putAll in interface Map

See Also:

Map.putAll(Map)

remove

public Object remove(Object key)

Removes the mapping for this key from this Map if it is present (optional operation).

Notes

As according to the interface, the removed Object is returned. This returns the dereferenced Object, not its WeakReference wrapper. Even if the WeakReference still exists in the Map its referent may be null, so returning a null is not necessarily an indication of the mapping existing in the Map as it would in a typical Map.

Specified by:

remove in interface Map

See Also:

Map.remove(Object)

size

public int size()

Returns the number of key-value mappings in this Map.

Notes

Note that this returns the size of the backing hashtable and does not take into account any expired WeakReferences.

Specified by:

size in interface Map

See Also:

Map.size()

values

public Collection values()

Returns a collection view of the values contained in this map.

Notes

Notes

This returns the values of the backing Hashtable. Any attempts to modify the keySet will throw an UnsupportedOperationException.

Specified by:

values in interface Map

See Also:

Changes to API, Map.values()

contains

public boolean contains(Object value)

Returns true if this Map maps one or more keys to the specified value.

Notes

Because the values are stored as WeakReferences this forces a test of all the WeakReference's stored references, which is more expensive than a simple query of the backing Hashtable.

Note that this method is identical in functionality to containsValue(Object), (which is part of the Map interface in the Collections framework).

See Also:

Map.containsValue(Object)

trimCache

protected void trimCache()

Trims the bottom off the cache based on the set limit. If there is no maximum set this does nothing.

setMaximumSize

public void setMaximumSize(int max)

If the maximum size is set (by default it is not), the list will be auto-trimmed to limit, from the bottom (least popular). Setting to a negative number disables the feature again.

rankOf

public int rankOf(Object key)

Returns the current ranking of Object key as an int. This may change with any accesses or modifications to the list, though the ranking is not affected by this method. If the Object is not in the cache, returns -1.