org.codehaus.plexus.util

Class FastMap

public class FastMap extends Object implements Map, Cloneable, Serializable

This class represents a Map collection with real-time behavior. Unless the map's size exceeds its current capacity, no dynamic memory allocation is ever performed and response time is extremely fast and consistent.

Our benchmark indicates that {@link FastMap#put FastMap.put(key, value)} is up to 5x faster than java.util.HashMap.put(key, value). This difference is mostly due to the cost of the Map.Entry allocations that {@link FastMap} avoids by recycling its entries (see note below).

{@link FastMap} has a predictable iteration order, which is the order in which keys were inserted into the map (similar to java.util.LinkedHashMap collection class).

Applications may change the resizing policy of {@link FastMap} by overriding the {@link #sizeChanged} method. For example, to improve predictability, automatic resizing can be disabled.

This implementation is not synchronized. Multiple threads accessing or modifying the collection must be synchronized externally.

Note: To avoid dynamic memory allocations, {@link FastMap} maintains an internal pool of Map.Entry objects. The size of the pool is determined by the map's capacity. When an entry is removed from the map, it is automatically restored to the pool.

This class is public domain (not copyrighted).

Version: 5.3, October 31 2003

Author: Jean-Marie Dautelle

Nested Class Summary
static classFastMap.EntryImpl
This class represents a {@link FastMap} entry.
classFastMap.EntrySet
classFastMap.KeySet
classFastMap.Values
Field Summary
int_capacity
Holds the map's current capacity.
FastMap.EntryImpl[]_entries
Holds the map's hash table.
FastMap.EntrySet_entrySet
FastMap.KeySet_keySet
FastMap.EntryImpl_mapFirst
Holds the first map entry (linked list).
FastMap.EntryImpl_mapLast
Holds the last map entry (linked list).
int_mask
Holds the hash code mask.
FastMap.EntryImpl_poolFirst
Holds the first pool entry (linked list).
int_size
Holds the current size.
FastMap.Values_values
Constructor Summary
FastMap()
Creates a {@link FastMap} with a capacity of 256 entries.
FastMap(Map map)
Creates a {@link FastMap}, copy of the specified Map.
FastMap(int capacity)
Creates a {@link FastMap} with the specified capacity.
Method Summary
voidaddEntry(Object key, Object value)
Adds a new entry for the specified key and value.
intcapacity()
Returns the capacity of this {@link FastMap}.
voidclear()
Removes all mappings from this {@link FastMap}.
Objectclone()
Returns a shallow copy of this {@link FastMap}.
booleancontainsKey(Object key)
Indicates if this {@link FastMap} contains a mapping for the specified key.
booleancontainsValue(Object value)
Indicates if this {@link FastMap} maps one or more keys to the specified value.
SetentrySet()
Returns a collection view of the mappings contained in this {@link FastMap}.
booleanequals(Object obj)
Compares the specified object with this {@link FastMap} for equality.
Objectget(Object key)
Returns the value to which this {@link FastMap} maps the specified key.
EntrygetEntry(Object key)
Returns the entry with the specified key.
inthashCode()
Returns the hash code value for this {@link FastMap}.
voidinitialize(int capacity)
Initializes this instance for the specified capacity.
booleanisEmpty()
Indicates if this {@link FastMap} contains no key-value mappings.
static intkeyHash(Object key)
Returns the hash code for the specified key.
SetkeySet()
Returns a set view of the keys contained in this {@link FastMap}.
Objectput(Object key, Object value)
Associates the specified value with the specified key in this {@link FastMap}.
voidputAll(Map map)
Copies all of the mappings from the specified map to this {@link FastMap}.
voidreadObject(ObjectInputStream stream)
Requires special handling during de-serialization process.
Objectremove(Object key)
Removes the mapping for this key from this {@link FastMap} if present.
voidremoveEntry(FastMap.EntryImpl entry)
Removes the specified entry from the map.
voidsetCapacity(int newCapacity)
Changes the current capacity of this {@link FastMap}.
intsize()
Returns the number of key-value mappings in this {@link FastMap}.
protected voidsizeChanged()
This methods is being called when the size of this {@link FastMap} has changed.
StringtoString()
Returns a String representation of this {@link FastMap}.
Collectionvalues()
Returns a collection view of the values contained in this {@link FastMap}.
voidwriteObject(ObjectOutputStream stream)
Requires special handling during serialization process.

Field Detail

_capacity

private transient int _capacity
Holds the map's current capacity.

_entries

private transient FastMap.EntryImpl[] _entries
Holds the map's hash table.

_entrySet

private transient FastMap.EntrySet _entrySet

_keySet

private transient FastMap.KeySet _keySet

_mapFirst

private transient FastMap.EntryImpl _mapFirst
Holds the first map entry (linked list).

_mapLast

private transient FastMap.EntryImpl _mapLast
Holds the last map entry (linked list).

_mask

private transient int _mask
Holds the hash code mask.

_poolFirst

private transient FastMap.EntryImpl _poolFirst
Holds the first pool entry (linked list).

_size

private transient int _size
Holds the current size.

_values

private transient FastMap.Values _values

Constructor Detail

FastMap

public FastMap()
Creates a {@link FastMap} with a capacity of 256 entries.

FastMap

public FastMap(Map map)
Creates a {@link FastMap}, copy of the specified Map. If the specified map is not an instance of {@link FastMap}, the newly created map has a capacity set to the specified map's size. The copy has the same order as the original, regardless of the original map's implementation:
     TreeMap dictionary = ...;
     FastMap dictionaryLookup = new FastMap(dictionary);
 

Parameters: map the map whose mappings are to be placed in this map.

FastMap

public FastMap(int capacity)
Creates a {@link FastMap} with the specified capacity. Unless the capacity is exceeded, operations on this map do not allocate entries. For optimum performance, the capacity should be of the same order of magnitude or larger than the expected map's size.

Parameters: capacity the number of buckets in the hash table; it also defines the number of pre-allocated entries.

Method Detail

addEntry

private void addEntry(Object key, Object value)
Adds a new entry for the specified key and value.

Parameters: key the entry's key. value the entry's value.

capacity

public int capacity()
Returns the capacity of this {@link FastMap}. The capacity defines the number of buckets in the hash table, as well as the maximum number of entries the map may contain without allocating memory.

Returns: this map's capacity.

clear

public void clear()
Removes all mappings from this {@link FastMap}.

clone

public Object clone()
Returns a shallow copy of this {@link FastMap}. The keys and the values themselves are not cloned.

Returns: a shallow copy of this map.

containsKey

public boolean containsKey(Object key)
Indicates if this {@link FastMap} contains a mapping for the specified key.

Parameters: key the key whose presence in this map is to be tested.

Returns: true if this map contains a mapping for the specified key; false otherwise.

Throws: NullPointerException if the key is null.

containsValue

public boolean containsValue(Object value)
Indicates if this {@link FastMap} maps one or more keys to the specified value.

Parameters: value the value whose presence in this map is to be tested.

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

Throws: NullPointerException if the key is null.

entrySet

public Set entrySet()
Returns a collection view of the mappings contained in this {@link FastMap}. Each element in the returned collection is a Map.Entry. The collection is backed by the map, so changes to the map are reflected in the collection, and vice-versa. The collection supports element removal, which removes the corresponding mapping from this map, via the Iterator.remove, Collection.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations.

Returns: a collection view of the mappings contained in this map.

equals

public boolean equals(Object obj)
Compares the specified object with this {@link FastMap} for equality. Returns true if the given object is also a map and the two maps represent the same mappings (regardless of collection iteration order).

Parameters: obj the object to be compared for equality with this map.

Returns: true if the specified object is equal to this map; false otherwise.

get

public Object get(Object key)
Returns the value to which this {@link FastMap} maps the specified key.

Parameters: key the key whose associated value is to be returned.

Returns: the value to which this map maps the specified key, or null if there is no mapping for the key.

Throws: NullPointerException if key is null.

getEntry

public Entry getEntry(Object key)
Returns the entry with the specified key.

Parameters: key the key whose associated entry is to be returned.

Returns: the entry for the specified key or null if none.

hashCode

public int hashCode()
Returns the hash code value for this {@link FastMap}.

Returns: the hash code value for this map.

initialize

private void initialize(int capacity)
Initializes this instance for the specified capacity. Once initialized, operations on this map should not create new objects (unless the map's size exceeds the specified capacity).

Parameters: capacity the initial capacity.

isEmpty

public boolean isEmpty()
Indicates if this {@link FastMap} contains no key-value mappings.

Returns: true if this map contains no key-value mappings; false otherwise.

keyHash

private static int keyHash(Object key)
Returns the hash code for the specified key. The formula being used is identical to the formula used by java.util.HashMap (ensures similar behavior for ill-conditioned hashcode keys).

Parameters: key the key to calculate the hashcode for.

Returns: the hash code for the specified key.

keySet

public Set keySet()
Returns a set view of the keys contained in this {@link FastMap}. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. The set supports element removal, which removes the corresponding mapping from this map, via the Iterator.remove, Collection.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations.

Returns: a set view of the keys contained in this map.

put

public Object put(Object key, Object value)
Associates the specified value with the specified key in this {@link FastMap}. If the {@link FastMap} previously contained a mapping for this key, the old value is replaced.

Parameters: key the key with which the specified value is to be associated. value the value to be associated with the specified key.

Returns: the previous value associated with specified key, or null if there was no mapping for key. A null return can also indicate that the map previously associated null with the specified key.

Throws: NullPointerException if the key is null.

putAll

public void putAll(Map map)
Copies all of the mappings from the specified map to this {@link FastMap}.

Parameters: map the mappings to be stored in this map.

Throws: NullPointerException the specified map is null, or the specified map contains null keys.

readObject

private void readObject(ObjectInputStream stream)
Requires special handling during de-serialization process.

Parameters: stream the object input stream.

Throws: IOException if an I/O error occurs. ClassNotFoundException if the class for the object de-serialized is not found.

remove

public Object remove(Object key)
Removes the mapping for this key from this {@link FastMap} if present.

Parameters: key the key whose mapping is to be removed from the map.

Returns: previous value associated with specified key, or null if there was no mapping for key. A null return can also indicate that the map previously associated null with the specified key.

Throws: NullPointerException if the key is null.

removeEntry

private void removeEntry(FastMap.EntryImpl entry)
Removes the specified entry from the map.

Parameters: entry the entry to be removed.

setCapacity

public void setCapacity(int newCapacity)
Changes the current capacity of this {@link FastMap}. If the capacity is increased, new entries are allocated and added to the pool. If the capacity is decreased, entries from the pool are deallocated (and are eventually garbage collected). The capacity also determined the number of buckets for the hash table.

Parameters: newCapacity the new capacity of this map.

size

public int size()
Returns the number of key-value mappings in this {@link FastMap}.

Returns: this map's size.

sizeChanged

protected void sizeChanged()
This methods is being called when the size of this {@link FastMap} has changed. The default behavior is to double the map's capacity when the map's size reaches the current map's capacity. Sub-class may override this method to implement custom resizing policies or to disable automatic resizing. For example:
     Map fixedCapacityMap = new FastMap(256) { 
           protected sizeChanged() {
               // Do nothing, automatic resizing disabled.
           }
     };

See Also: FastMap

toString

public String toString()
Returns a String representation of this {@link FastMap}.

Returns: this.entrySet().toString();

values

public Collection values()
Returns a collection view of the values contained in this {@link FastMap}. The collection is backed by the map, so changes to the map are reflected in the collection, and vice-versa. The collection supports element removal, which removes the corresponding mapping from this map, via the Iterator.remove, Collection.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations.

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

writeObject

private void writeObject(ObjectOutputStream stream)
Requires special handling during serialization process.

Parameters: stream the object output stream.

Throws: IOException if an I/O error occurs.