org.codehaus.plexus.util
Class FastMap
java.lang.Object
org.codehaus.plexus.util.FastMap
- Cloneable, Map, Serializable
public class FastMap
extends java.lang.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
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
FastMap
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 to
java.util.LinkedHashMap
collection class).
Applications may change the resizing policy of
FastMap
by overriding the
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,
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).
private void | addEntry(Object key, Object value) - Adds a new entry for the specified key and value.
|
int | capacity() - Returns the capacity of this
FastMap .
|
void | clear() - Removes all mappings from this
FastMap .
|
Object | clone() - Returns a shallow copy of this
FastMap .
|
boolean | containsKey(Object key) - Indicates if this
FastMap contains a mapping for the specified
key.
|
boolean | containsValue(Object value) - Indicates if this
FastMap maps one or more keys to the
specified value.
|
Set | entrySet() - Returns a collection view of the mappings contained in this
FastMap .
|
boolean | equals(Object obj) - Compares the specified object with this
FastMap for equality.
|
Object | get(Object key) - Returns the value to which this
FastMap maps the specified key.
|
Map.Entry | getEntry(Object key) - Returns the entry with the specified key.
|
int | hashCode() - Returns the hash code value for this
FastMap .
|
private void | initialize(int capacity) - Initializes this instance for the specified capacity.
|
boolean | isEmpty() - Indicates if this
FastMap contains no key-value mappings.
|
private static int | keyHash(Object key) - Returns the hash code for the specified key.
|
Set | keySet() - Returns a set view of the keys contained in this
FastMap .
|
Object | put(Object key, Object value) - Associates the specified value with the specified key in this
FastMap .
|
void | putAll(Map map) - Copies all of the mappings from the specified map to this
FastMap .
|
private void | readObject(ObjectInputStream stream) - Requires special handling during de-serialization process.
|
Object | remove(Object key) - Removes the mapping for this key from this
FastMap if present.
|
private void | removeEntry(FastMap.EntryImpl entry) - Removes the specified entry from the map.
|
void | setCapacity(int newCapacity) - Changes the current capacity of this
FastMap .
|
int | size() - Returns the number of key-value mappings in this
FastMap .
|
protected void | sizeChanged() - This methods is being called when the size of this
FastMap
has changed.
|
String | toString() - Returns a
String representation of this FastMap .
|
Collection | values() - Returns a collection view of the values contained in this
FastMap .
|
private void | writeObject(ObjectOutputStream stream) - Requires special handling during serialization process.
|
_capacity
private int _capacity
Holds the map's current capacity.
_mapFirst
private FastMap.EntryImpl _mapFirst
Holds the first map entry (linked list).
_mask
private int _mask
Holds the hash code mask.
_poolFirst
private FastMap.EntryImpl _poolFirst
Holds the first pool entry (linked list).
_size
private int _size
Holds the current size.
FastMap
public FastMap()
Creates a
FastMap
with a capacity of
256
entries.
FastMap
public FastMap(Map map)
Creates a
FastMap
, copy of the specified
Map
.
If the specified map is not an instance of
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);
map
- the map whose mappings are to be placed in this map.
FastMap
public FastMap(int capacity)
Creates a
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.
capacity
- the number of buckets in the hash table; it also
defines the number of pre-allocated entries.
addEntry
private void addEntry(Object key,
Object value)
Adds a new entry for the specified key and value.
key
- the entry's key.value
- the entry's value.
capacity
public int capacity()
Returns the capacity of this
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.
clear
public void clear()
Removes all mappings from this
FastMap
.
clone
public Object clone()
Returns a shallow copy of this
FastMap
. The keys and
the values themselves are not cloned.
- a shallow copy of this map.
containsKey
public boolean containsKey(Object key)
Indicates if this
FastMap
contains a mapping for the specified
key.
key
- the key whose presence in this map is to be tested.
true
if this map contains a mapping for the
specified key; false
otherwise.
containsValue
public boolean containsValue(Object value)
Indicates if this
FastMap
maps one or more keys to the
specified value.
value
- the value whose presence in this map is to be tested.
true
if this map maps one or more keys to the
specified value.
entrySet
public Set entrySet()
Returns a collection view of the mappings contained in this
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.
- a collection view of the mappings contained in this map.
equals
public boolean equals(Object obj)
Compares the specified object with this
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).
obj
- the object to be compared for equality with this map.
true
if the specified object is equal to this map;
false
otherwise.
get
public Object get(Object key)
Returns the value to which this
FastMap
maps the specified key.
key
- the key whose associated value is to be returned.
- the value to which this map maps the specified key,
or
null
if there is no mapping for the key.
getEntry
public Map.Entry getEntry(Object key)
Returns the entry with the specified key.
key
- the key whose associated entry is to be returned.
- the entry for the specified key or
null
if none.
hashCode
public int hashCode()
Returns the hash code value for this
FastMap
.
- 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).
capacity
- the initial capacity.
isEmpty
public boolean isEmpty()
Indicates if this
FastMap
contains no key-value mappings.
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).
key
- the key to calculate the hashcode for.
- the hash code for the specified key.
keySet
public Set keySet()
Returns a set view of the keys contained in this
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.
- 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
FastMap
. If the
FastMap
previously contained a mapping
for this key, the old value is replaced.
key
- the key with which the specified value is to be associated.value
- the value to be associated with the specified key.
- 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.
putAll
public void putAll(Map map)
Copies all of the mappings from the specified map to this
FastMap
.
map
- the mappings to be stored in this map.
readObject
private void readObject(ObjectInputStream stream)
throws IOException,
ClassNotFoundException
Requires special handling during de-serialization process.
stream
- the object input stream.
remove
public Object remove(Object key)
Removes the mapping for this key from this
FastMap
if present.
key
- the key whose mapping is to be removed from the map.
- 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.
removeEntry
private void removeEntry(FastMap.EntryImpl entry)
Removes the specified entry from the map.
entry
- the entry to be removed.
setCapacity
public void setCapacity(int newCapacity)
Changes the current capacity of this
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.
newCapacity
- the new capacity of this map.
size
public int size()
Returns the number of key-value mappings in this
FastMap
.
sizeChanged
protected void sizeChanged()
This methods is being called when the size of this
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.
}
};
toString
public String toString()
Returns a
String
representation of this
FastMap
.
this.entrySet().toString();
values
public Collection values()
Returns a collection view of the values contained in this
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.
- a collection view of the values contained in this map.
writeObject
private void writeObject(ObjectOutputStream stream)
throws IOException
Requires special handling during serialization process.
stream
- the object output stream.