Class FastMap<K,V>
- java.lang.Object
-
- org.codehaus.plexus.util.FastMap<K,V>
-
- All Implemented Interfaces:
java.io.Serializable
,java.lang.Cloneable
,java.util.Map<K,V>
public class FastMap<K,V> extends java.lang.Object implements java.util.Map<K,V>, java.lang.Cloneable, java.io.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
FastMap.put(key, value)
is up to 5x faster thanjava.util.HashMap.put(key, value)
. This difference is mostly due to the cost of theMap.Entry
allocations thatFastMap
avoids by recycling its entries (see note below).FastMap
has a predictable iteration order, which is the order in which keys were inserted into the map (similar tojava.util.LinkedHashMap
collection class).Applications may change the resizing policy of
FastMap
by overriding thesizeChanged()
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,
FastMap
maintains an internal pool ofMap.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
- See Also:
- Serialized Form
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
FastMap.EntryImpl<K,V>
This class represents aFastMap
entry.private class
FastMap.EntrySet
private class
FastMap.KeySet
private class
FastMap.Values
-
Field Summary
Fields Modifier and Type Field Description private int
_capacity
Holds the map's current capacity.private FastMap.EntryImpl[]
_entries
Holds the map's hash table.private FastMap.EntrySet
_entrySet
private FastMap.KeySet
_keySet
private FastMap.EntryImpl
_mapFirst
Holds the first map entry (linked list).private FastMap.EntryImpl
_mapLast
Holds the last map entry (linked list).private int
_mask
Holds the hash code mask.private FastMap.EntryImpl
_poolFirst
Holds the first pool entry (linked list).private int
_size
Holds the current size.private FastMap.Values
_values
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
addEntry(java.lang.Object key, java.lang.Object value)
Adds a new entry for the specified key and value.int
capacity()
Returns the capacity of thisFastMap
.void
clear()
Removes all mappings from thisFastMap
.java.lang.Object
clone()
Returns a shallow copy of thisFastMap
.boolean
containsKey(java.lang.Object key)
Indicates if thisFastMap
contains a mapping for the specified key.boolean
containsValue(java.lang.Object value)
Indicates if thisFastMap
maps one or more keys to the specified value.java.util.Set
entrySet()
Returns a collection view of the mappings contained in thisFastMap
.boolean
equals(java.lang.Object obj)
Compares the specified object with thisFastMap
for equality.V
get(java.lang.Object key)
Returns the value to which thisFastMap
maps the specified key.java.util.Map.Entry
getEntry(java.lang.Object key)
Returns the entry with the specified key.int
hashCode()
Returns the hash code value for thisFastMap
.private void
initialize(int capacity)
Initializes this instance for the specified capacity.boolean
isEmpty()
Indicates if thisFastMap
contains no key-value mappings.private static int
keyHash(java.lang.Object key)
Returns the hash code for the specified key.java.util.Set
keySet()
Returns a set view of the keys contained in thisFastMap
.java.lang.Object
put(java.lang.Object key, java.lang.Object value)
Associates the specified value with the specified key in thisFastMap
.void
putAll(java.util.Map<? extends K,? extends V> map)
Copies all of the mappings from the specified map to thisFastMap
.private void
readObject(java.io.ObjectInputStream stream)
Requires special handling during de-serialization process.V
remove(java.lang.Object key)
Removes the mapping for this key from thisFastMap
if present.private void
removeEntry(FastMap.EntryImpl entry)
Removes the specified entry from the map.void
setCapacity(int newCapacity)
Changes the current capacity of thisFastMap
.int
size()
Returns the number of key-value mappings in thisFastMap
.protected void
sizeChanged()
This methods is being called when the size of thisFastMap
has changed.java.lang.String
toString()
Returns aString
representation of thisFastMap
.java.util.Collection
values()
Returns a collection view of the values contained in thisFastMap
.private void
writeObject(java.io.ObjectOutputStream stream)
Requires special handling during serialization process.
-
-
-
Field Detail
-
_entries
private transient FastMap.EntryImpl[] _entries
Holds the map's hash table.
-
_capacity
private transient int _capacity
Holds the map's current capacity.
-
_mask
private transient int _mask
Holds the hash code mask.
-
_poolFirst
private transient FastMap.EntryImpl _poolFirst
Holds the first pool entry (linked list).
-
_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).
-
_size
private transient int _size
Holds the current size.
-
_values
private transient FastMap.Values _values
-
_entrySet
private transient FastMap.EntrySet _entrySet
-
_keySet
private transient FastMap.KeySet _keySet
-
-
Constructor Detail
-
FastMap
public FastMap()
Creates aFastMap
with a capacity of256
entries.
-
FastMap
public FastMap(java.util.Map map)
Creates aFastMap
, copy of the specifiedMap
. If the specified map is not an instance ofFastMap
, 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 aFastMap
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
-
size
public int size()
Returns the number of key-value mappings in thisFastMap
.
-
capacity
public int capacity()
Returns the capacity of thisFastMap
. 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.
-
isEmpty
public boolean isEmpty()
Indicates if thisFastMap
contains no key-value mappings.
-
containsKey
public boolean containsKey(java.lang.Object key)
Indicates if thisFastMap
contains a mapping for the specified key.
-
containsValue
public boolean containsValue(java.lang.Object value)
Indicates if thisFastMap
maps one or more keys to the specified value.
-
get
public V get(java.lang.Object key)
Returns the value to which thisFastMap
maps the specified key.
-
getEntry
public java.util.Map.Entry getEntry(java.lang.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.
-
put
public java.lang.Object put(java.lang.Object key, java.lang.Object value)
Associates the specified value with the specified key in thisFastMap
. If theFastMap
previously contained a mapping for this key, the old value is replaced.- Specified by:
put
in interfacejava.util.Map<K,V>
- 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. Anull
return can also indicate that the map previously associatednull
with the specified key. - Throws:
java.lang.NullPointerException
- if the key isnull
.
-
putAll
public void putAll(java.util.Map<? extends K,? extends V> map)
Copies all of the mappings from the specified map to thisFastMap
.
-
remove
public V remove(java.lang.Object key)
Removes the mapping for this key from thisFastMap
if present.- Specified by:
remove
in interfacejava.util.Map<K,V>
- 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. Anull
return can also indicate that the map previously associatednull
with the specified key. - Throws:
java.lang.NullPointerException
- if the key isnull
.
-
clear
public void clear()
Removes all mappings from thisFastMap
.
-
setCapacity
public void setCapacity(int newCapacity)
Changes the current capacity of thisFastMap
. 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.
-
clone
public java.lang.Object clone()
Returns a shallow copy of thisFastMap
. The keys and the values themselves are not cloned.- Overrides:
clone
in classjava.lang.Object
- Returns:
- a shallow copy of this map.
-
equals
public boolean equals(java.lang.Object obj)
Compares the specified object with thisFastMap
for equality. Returnstrue
if the given object is also a map and the two maps represent the same mappings (regardless of collection iteration order).
-
hashCode
public int hashCode()
Returns the hash code value for thisFastMap
.
-
toString
public java.lang.String toString()
Returns aString
representation of thisFastMap
.- Overrides:
toString
in classjava.lang.Object
- Returns:
this.entrySet().toString();
-
values
public java.util.Collection values()
Returns a collection view of the values contained in thisFastMap
. 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 theIterator.remove
,Collection.remove
,removeAll
,retainAll
, andclear
operations. It does not support theadd
oraddAll
operations.
-
entrySet
public java.util.Set entrySet()
Returns a collection view of the mappings contained in thisFastMap
. Each element in the returned collection is aMap.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 theIterator.remove
,Collection.remove
,removeAll
,retainAll
, andclear
operations. It does not support theadd
oraddAll
operations.
-
keySet
public java.util.Set keySet()
Returns a set view of the keys contained in thisFastMap
. 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 theIterator.remove
,Collection.remove
,removeAll
,retainAll
, andclear
operations. It does not support theadd
oraddAll
operations.
-
sizeChanged
protected void sizeChanged()
This methods is being called when the size of thisFastMap
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:
setCapacity(int)
-
keyHash
private static int keyHash(java.lang.Object key)
Returns the hash code for the specified key. The formula being used is identical to the formula used byjava.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.
-
addEntry
private void addEntry(java.lang.Object key, java.lang.Object value)
Adds a new entry for the specified key and value.- Parameters:
key
- the entry's key.value
- the entry's value.
-
removeEntry
private void removeEntry(FastMap.EntryImpl entry)
Removes the specified entry from the map.- Parameters:
entry
- the entry to be removed.
-
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.
-
readObject
private void readObject(java.io.ObjectInputStream stream) throws java.io.IOException, java.lang.ClassNotFoundException
Requires special handling during de-serialization process.- Parameters:
stream
- the object input stream.- Throws:
java.io.IOException
- if an I/O error occurs.java.lang.ClassNotFoundException
- if the class for the object de-serialized is not found.
-
writeObject
private void writeObject(java.io.ObjectOutputStream stream) throws java.io.IOException
Requires special handling during serialization process.- Parameters:
stream
- the object output stream.- Throws:
java.io.IOException
- if an I/O error occurs.
-
-