org.apache.commons.collections.map
public class AbstractHashedMap extends AbstractMap implements IterableMap
This class implements all the features necessary for a subclass hash-based map.
Key-value entries are stored in instances of the HashEntry
class,
which can be overridden and replaced. The iterators can similarly be replaced,
without the need to replace the KeySet, EntrySet and Values view classes.
Overridable methods are provided to change the default hashing behaviour, and to change how entries are added to and removed from the map. Hopefully, all you need for unusual subclasses is here.
NOTE: From Commons Collections 3.1 this class extends AbstractMap. This is to provide backwards compatibility for ReferenceMap between v3.0 and v3.1. This extends clause will be removed in v4.0.
Since: Commons Collections 3.0
Version: $Revision: 171349 $ $Date: 2005-05-22 18:48:56 +0100 (Sun, 22 May 2005) $
Nested Class Summary | |
---|---|
protected static class | AbstractHashedMap.EntrySet
EntrySet implementation. |
protected static class | AbstractHashedMap.EntrySetIterator
EntrySet iterator. |
protected static class | AbstractHashedMap.HashEntry
HashEntry used to store the data.
|
protected abstract static class | AbstractHashedMap.HashIterator
Base Iterator |
protected static class | AbstractHashedMap.HashMapIterator
MapIterator implementation. |
protected static class | AbstractHashedMap.KeySet
KeySet implementation. |
protected static class | AbstractHashedMap.KeySetIterator
KeySet iterator. |
protected static class | AbstractHashedMap.Values
Values implementation. |
protected static class | AbstractHashedMap.ValuesIterator
Values iterator. |
Field Summary | |
---|---|
protected AbstractHashedMap.HashEntry[] | data Map entries |
protected static int | DEFAULT_CAPACITY The default capacity to use |
protected static float | DEFAULT_LOAD_FACTOR The default load factor to use |
protected static int | DEFAULT_THRESHOLD The default threshold to use |
protected AbstractHashedMap.EntrySet | entrySet Entry set |
protected static String | GETKEY_INVALID |
protected static String | GETVALUE_INVALID |
protected AbstractHashedMap.KeySet | keySet Key set |
protected float | loadFactor Load factor, normally 0.75 |
protected int | modCount Modification count for iterators |
protected static int | MAXIMUM_CAPACITY The maximum capacity allowed |
protected static String | NO_NEXT_ENTRY |
protected static String | NO_PREVIOUS_ENTRY |
protected static Object | NULL An object for masking null |
protected static String | REMOVE_INVALID |
protected int | size The size of the map |
protected static String | SETVALUE_INVALID |
protected int | threshold Size at which to rehash |
protected AbstractHashedMap.Values | values Values |
Constructor Summary | |
---|---|
protected | AbstractHashedMap()
Constructor only used in deserialization, do not use otherwise. |
protected | AbstractHashedMap(int initialCapacity, float loadFactor, int threshold)
Constructor which performs no validation on the passed in parameters.
|
protected | AbstractHashedMap(int initialCapacity)
Constructs a new, empty map with the specified initial capacity and
default load factor.
|
protected | AbstractHashedMap(int initialCapacity, float loadFactor)
Constructs a new, empty map with the specified initial capacity and
load factor.
|
protected | AbstractHashedMap(Map map)
Constructor copying elements from another map.
|
Method Summary | |
---|---|
protected void | addEntry(AbstractHashedMap.HashEntry entry, int hashIndex)
Adds an entry into this map.
|
protected void | addMapping(int hashIndex, int hashCode, Object key, Object value)
Adds a new key-value mapping into this map.
|
protected int | calculateNewCapacity(int proposedCapacity)
Calculates the new capacity of the map.
|
protected int | calculateThreshold(int newCapacity, float factor)
Calculates the new threshold of the map, where it will be resized.
|
protected void | checkCapacity()
Checks the capacity of the map and enlarges it if necessary.
|
void | clear()
Clears the map, resetting the size to zero and nullifying references
to avoid garbage collection issues. |
protected Object | clone()
Clones the map without cloning the keys or values.
|
boolean | containsKey(Object key)
Checks whether the map contains the specified key.
|
boolean | containsValue(Object value)
Checks whether the map contains the specified value.
|
protected Object | convertKey(Object key)
Converts input keys to another object for storage in the map.
|
protected AbstractHashedMap.HashEntry | createEntry(AbstractHashedMap.HashEntry next, int hashCode, Object key, Object value)
Creates an entry to store the key-value data.
|
protected Iterator | createEntrySetIterator()
Creates an entry set iterator.
|
protected Iterator | createKeySetIterator()
Creates a key set iterator.
|
protected Iterator | createValuesIterator()
Creates a values iterator.
|
protected void | destroyEntry(AbstractHashedMap.HashEntry entry)
Kills an entry ready for the garbage collector.
|
protected void | doReadObject(ObjectInputStream in)
Reads the map data from the stream. |
protected void | doWriteObject(ObjectOutputStream out)
Writes the map data to the stream. |
protected void | ensureCapacity(int newCapacity)
Changes the size of the data structure to the capacity proposed.
|
protected int | entryHashCode(AbstractHashedMap.HashEntry entry)
Gets the hashCode field from a HashEntry .
|
protected Object | entryKey(AbstractHashedMap.HashEntry entry)
Gets the key field from a HashEntry .
|
protected AbstractHashedMap.HashEntry | entryNext(AbstractHashedMap.HashEntry entry)
Gets the next field from a HashEntry .
|
Set | entrySet()
Gets the entrySet view of the map.
|
protected Object | entryValue(AbstractHashedMap.HashEntry entry)
Gets the value field from a HashEntry .
|
boolean | equals(Object obj)
Compares this map with another.
|
Object | get(Object key)
Gets the value mapped to the key specified.
|
protected AbstractHashedMap.HashEntry | getEntry(Object key)
Gets the entry mapped to the key specified.
|
protected int | hash(Object key)
Gets the hash code for the key specified.
|
int | hashCode()
Gets the standard Map hashCode.
|
protected int | hashIndex(int hashCode, int dataSize)
Gets the index into the data storage for the hashCode specified.
|
protected void | init()
Initialise subclasses during construction, cloning or deserialization. |
boolean | isEmpty()
Checks whether the map is currently empty.
|
protected boolean | isEqualKey(Object key1, Object key2)
Compares two keys, in internal converted form, to see if they are equal.
|
protected boolean | isEqualValue(Object value1, Object value2)
Compares two values, in external form, to see if they are equal.
|
Set | keySet()
Gets the keySet view of the map.
|
MapIterator | mapIterator()
Gets an iterator over the map.
|
Object | put(Object key, Object value)
Puts a key-value mapping into this map.
|
void | putAll(Map map)
Puts all the values from the specified map into this map.
|
Object | remove(Object key)
Removes the specified mapping from this map.
|
protected void | removeEntry(AbstractHashedMap.HashEntry entry, int hashIndex, AbstractHashedMap.HashEntry previous)
Removes an entry from the chain stored in a particular index.
|
protected void | removeMapping(AbstractHashedMap.HashEntry entry, int hashIndex, AbstractHashedMap.HashEntry previous)
Removes a mapping from the map.
|
protected void | reuseEntry(AbstractHashedMap.HashEntry entry, int hashIndex, int hashCode, Object key, Object value)
Reuses an existing key-value mapping, storing completely new data.
|
int | size()
Gets the size of the map.
|
String | toString()
Gets the map as a String.
|
protected void | updateEntry(AbstractHashedMap.HashEntry entry, Object newValue)
Updates an existing key-value mapping to change the value.
|
Collection | values()
Gets the values view of the map.
|
Parameters: initialCapacity the initial capacity, must be a power of two loadFactor the load factor, must be > 0.0f and generally < 1.0f threshold the threshold, must be sensible
Parameters: initialCapacity the initial capacity
Throws: IllegalArgumentException if the initial capacity is less than one
Parameters: initialCapacity the initial capacity loadFactor the load factor
Throws: IllegalArgumentException if the initial capacity is less than one IllegalArgumentException if the load factor is less than or equal to zero
Parameters: map the map to copy
Throws: NullPointerException if the map is null
This implementation adds the entry to the data storage table. Subclasses could override to handle changes to the map.
Parameters: entry the entry to add hashIndex the index into the data array to store at
This implementation calls createEntry()
, addEntry()
and checkCapacity()
.
It also handles changes to modCount
and size
.
Subclasses could override to fully control adds to the map.
Parameters: hashIndex the index into the data array to store at hashCode the hash code of the key to add key the key to add value the value to add
Parameters: proposedCapacity the proposed capacity
Returns: the normalized new capacity
Parameters: newCapacity the new capacity factor the load factor
Returns: the new resize threshold
This implementation uses the threshold to check if the map needs enlarging
To implement clone()
, a subclass must implement the
Cloneable
interface and make this method public.
Returns: a shallow clone
Parameters: key the key to search for
Returns: true if the map contains the key
Parameters: value the value to search for
Returns: true if the map contains the value
The reverse conversion can be changed, if required, by overriding the getKey() method in the hash entry.
Parameters: key the key convert
Returns: the converted key
This implementation creates a new HashEntry instance. Subclasses can override this to return a different storage class, or implement caching.
Parameters: next the next entry in sequence hashCode the hash code to use key the key to store value the value to store
Returns: the newly created entry
Returns: the entrySet iterator
Returns: the keySet iterator
Returns: the values iterator
This implementation prepares the HashEntry for garbage collection. Subclasses can override this to implement caching (override clear as well).
Parameters: entry the entry to destroy
put()
is used.
Serialization is not one of the JDK's nicest topics. Normal serialization will
initialise the superclass before the subclass. Sometimes however, this isn't
what you want, as in this case the put()
method on read can be
affected by subclass state.
The solution adopted here is to deserialize the state data of this class in
this protected method. This method must be called by the
readObject()
of the first serializable subclass.
Subclasses may override if the subclass has a specific field that must be present
before put()
or calculateThreshold()
will work correctly.
Parameters: in the input stream
put()
is used.
Serialization is not one of the JDK's nicest topics. Normal serialization will
initialise the superclass before the subclass. Sometimes however, this isn't
what you want, as in this case the put()
method on read can be
affected by subclass state.
The solution adopted here is to serialize the state data of this class in
this protected method. This method must be called by the
writeObject()
of the first serializable subclass.
Subclasses may override if they have a specific field that must be present on read before this implementation will work. Generally, the read determines what must be serialized here, if anything.
Parameters: out the output stream
Parameters: newCapacity the new capacity of the array (a power of two, less or equal to max)
hashCode
field from a HashEntry
.
Used in subclasses that have no visibility of the field.
Parameters: entry the entry to query, must not be null
Returns: the hashCode
field of the entry
Throws: NullPointerException if the entry is null
Since: Commons Collections 3.1
key
field from a HashEntry
.
Used in subclasses that have no visibility of the field.
Parameters: entry the entry to query, must not be null
Returns: the key
field of the entry
Throws: NullPointerException if the entry is null
Since: Commons Collections 3.1
next
field from a HashEntry
.
Used in subclasses that have no visibility of the field.
Parameters: entry the entry to query, must not be null
Returns: the next
field of the entry
Throws: NullPointerException if the entry is null
Since: Commons Collections 3.1
Returns: the entrySet view
value
field from a HashEntry
.
Used in subclasses that have no visibility of the field.
Parameters: entry the entry to query, must not be null
Returns: the value
field of the entry
Throws: NullPointerException if the entry is null
Since: Commons Collections 3.1
Parameters: obj the object to compare to
Returns: true if equal
Parameters: key the key
Returns: the mapped value, null if no match
This method exists for subclasses that may need to perform a multi-step process accessing the entry. The public methods in this class don't use this method to gain a small performance boost.
Parameters: key the key
Returns: the entry, null if no match
Parameters: key the key to get a hash code for
Returns: the hash code
Returns: the hash code defined in the Map interface
Parameters: hashCode the hash code to use dataSize the size of the data to pick a bucket from
Returns: the bucket index
Returns: true if the map is currently size zero
Parameters: key1 the first key to compare passed in from outside key2 the second key extracted from the entry via entry.key
Returns: true if equal
Parameters: value1 the first value to compare passed in from outside value2 the second value extracted from the entry via getValue()
Returns: true if equal
Returns: the keySet view
A MapIterator returns the keys in the map. It also provides convenient methods to get the key and value, and set the value. It avoids the need to create an entrySet/keySet/values object. It also avoids creating the Map.Entry object.
Returns: the map iterator
Parameters: key the key to add value the value to add
Returns: the value previously mapped to this key, null if none
This implementation iterates around the specified map and uses AbstractHashedMap.
Parameters: map the map to add
Throws: NullPointerException if the map is null
Parameters: key the mapping to remove
Returns: the value mapped to the removed key, null if key not in map
This implementation removes the entry from the data storage table. The size is not updated. Subclasses could override to handle changes to the map.
Parameters: entry the entry to remove hashIndex the index into the data structure previous the previous entry in the chain
This implementation calls removeEntry()
and destroyEntry()
.
It also handles changes to modCount
and size
.
Subclasses could override to fully control removals from the map.
Parameters: entry the entry to remove hashIndex the index into the data structure previous the previous entry in the chain
This implementation sets all the data fields on the entry. Subclasses could populate additional entry fields.
Parameters: entry the entry to update, not null hashIndex the index in the data array hashCode the hash code of the key to add key the key to add value the value to add
Returns: the size
Returns: a string version of the map
This implementation calls setValue()
on the entry.
Subclasses could override to handle changes to the map.
Parameters: entry the entry to update newValue the new value to store
Returns: the values view