net.walend.collection
Class AbstractHashMap

java.lang.Object
  |
  +--net.walend.collection.AbstractHashMap

All Implemented Interfaces:

java.lang.Cloneable, HasState, Map, java.io.Serializable

Direct Known Subclasses:

HashMap, MutableHashMap, SoftHashMap

public abstract class AbstractHashMap

extends java.lang.Object

implements Map, java.lang.Cloneable, java.io.Serializable

This class is a hash table based implementation of the net.walend.collection.Map interface, based very heavily on the java.util.HashMap class by Josh Bloch and ultimately Arthur van Hoff. Any mistakes I'm sure are my own and not theirs.

This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.

An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the capacity is roughly doubled by calling the rehash method.

As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.

If many mappings are to be stored in a HashMap instance, creating it with a sufficiently large capacity will allow the mappings to be stored more efficiently than letting it perform automatic rehashing as needed to grow the table.

Note that this implementation is not synchronized. If multiple threads access this map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally.

The iterators returned by all of this class's "collection view methods" are fail-fast: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

Since:

20010705

Author:

David Walend

Nested Class Summary

protected static interface	AbstractHashMap.Entry Sublcass this abstract class and override newEntry to use specialized Entries.
private class	AbstractHashMap.EntryIterator
private class	AbstractHashMap.HashIterator General purpose iterator.
private class	AbstractHashMap.KeyIterator
private class	AbstractHashMap.SimpleEntry Entries for the hash map.
private class	AbstractHashMap.ValueIterator

Field Summary

private static int	DEFAULTCAPACITY
private static float	DEFAULTLOADFACTOR
private static java.util.Iterator	emptyIterator Special purpose iterator for empty hash maps.
private Identitor	ident The identitor that controls this Map
private float	loadFactor The load factor for the hash table.
private int	modCount The number of times this AbstractHashMap has been structurally modified Structural modifications are those that change the number of mappings in the AbstractHashMap or otherwise modify its internal structure (e.g., rehash).
private static long	serialVersionUID
private int	size The total number of mappings in the hash table.
private AbstractHashMap.Entry[]	table The hash table data.
private int	threshold The table is rehashed when its size exceeds this threshold.

Fields inherited from interface net.walend.collection.Map

EMPTY

Constructor Summary

protected	AbstractHashMap() Constructs a new, empty map with the DefaultIdentitor, a default capacity and load factor, which is 0.75.
protected	AbstractHashMap(Identitor identitor) Constructs a new, empty map with the specified Identitor, a default capacity and load factor, which is 0.75.
protected	AbstractHashMap(Identitor identitor, int initialCapacity) Constructs a new, empty map with the specified Identitor, initial capacity and default load factor, which is 0.75.
protected	AbstractHashMap(Identitor identitor, int initialCapacity, float loadFactor) Constructs a new, empty map with the specified Identitor, initial capacity and the specified load factor.
protected	AbstractHashMap(int initialCapacity) Constructs a new, empty map with the specified initial capacity, DefaultIdentitor, and default load factor, which is 0.75.
protected	AbstractHashMap(int initialCapacity, float loadFactor) Constructs a new, empty map with a DefaultIdentitor, the specified initial capacity and the specified load factor.
protected	AbstractHashMap(Map t) Constructs a new map with the same Identitor and mappings as the given map.
protected	AbstractHashMap(java.util.Map map) Constructs a new Map with a DefaultIdentitor and the same mappings as the java.util.Map.

Method Summary

protected int	capacity()
protected void	clear() Removes all mappings from this map.
java.lang.Object	clone() Returns a shallow copy of this AbstractHashMap instance: the keys and values themselves are not cloned.
boolean	containsAll(Map map) Returns true if this collection contains all of the Objects in the specified collection.
boolean	containsKey(java.lang.Object key) Returns true if this map contains a mapping for the specified key.
boolean	containsValue(java.lang.Object value) Returns true if this map maps one or more keys to the specified value.
java.lang.Object	get(java.lang.Object key) Returns the value to which this map maps the specified key.
private AbstractHashMap.Entry	getEntry(java.lang.Object key) Returns the entry associated with the specified key in the AbstractHashMap.
Identitor	getIdentitor() Returns the Identitor for this Map.
java.util.Map	getJavaMap() Return a java.util.Collection of these Objects.
Set	getKeys() Returns a set view of the keys contained in this map.
java.lang.Class	getPrincipleInterface() Returns the class's principle interface for state comparisons.
Collection	getValues() Returns a collection view of the values contained in this map.
boolean	isEmpty() Returns true if this map contains no key-value mappings.
java.util.Iterator	keyIterator() Returns an iterator over the keys.
protected float	loadFactor()
protected AbstractHashMap.Entry	newEntry(int hash, java.lang.Object key, java.lang.Object value, AbstractHashMap.Entry next) Override this method and subclass Entry to create specialized Entries.
private java.util.Iterator	newEntryIterator()
protected java.lang.Object	put(java.lang.Object key, java.lang.Object value) Puts the key,value pair in the map.
protected void	putAll(Map map) Copies all of the mappings from the specified map to this map (optional operation).
private void	readObject(java.io.ObjectInputStream s) Reconstitute the AbstractHashMap instance from a stream (i.e., deserialize it).
private void	rehash() Rehashes the contents of this map into a new AbstractHashMap instance with a larger capacity.
protected java.lang.Object	remove(java.lang.Object key) Removes the key, value pair from this Map.
(package private) void	removeEntry(AbstractHashMap.Entry doomed) Removes the specified entry from this AbstractHashMap (and increments modCount).
private AbstractHashMap.Entry	removeEntryForKey(java.lang.Object key) Removes and returns the entry associated with the specified key in the AbstractHashMap.
private AbstractHashMap.Entry	removeMapping(AbstractHashMap.Entry entry) Returns removed entry, or null if no match.
boolean	sameContentsAs(Map map) Returns true if this Collection's contents are equal to c's.
boolean	sameStateAs(HasState victem) If two HasStates have the same internal state, return true.
int	size() Returns the number of key-value mappings in this map.
java.lang.String	toString()
java.util.Iterator	valueIterator() Returns an iterator over the values.
private void	writeObject(java.io.ObjectOutputStream s) Save the state of the AbstractHashMap instance to a stream (i.e., serialize it).

Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

ident

private Identitor ident

The identitor that controls this Map

table

private transient AbstractHashMap.Entry[] table

The hash table data.

size

private transient int size

The total number of mappings in the hash table.

threshold

private int threshold

The table is rehashed when its size exceeds this threshold. (The value of this field is (int)(capacity * loadFactor).)

loadFactor

private final float loadFactor

The load factor for the hash table.

modCount

private transient int modCount

The number of times this AbstractHashMap has been structurally modified Structural modifications are those that change the number of mappings in the AbstractHashMap or otherwise modify its internal structure (e.g., rehash). This field is used to make iterators on Collection-views of the AbstractHashMap fail-fast. (See ConcurrentModificationException).

DEFAULTLOADFACTOR

private static final float DEFAULTLOADFACTOR

DEFAULTCAPACITY

private static final int DEFAULTCAPACITY

emptyIterator

private static java.util.Iterator emptyIterator

Special purpose iterator for empty hash maps. (Saves the cost of traversing all the buckets.

serialVersionUID

private static final long serialVersionUID

Constructor Detail

AbstractHashMap

protected AbstractHashMap(Identitor identitor,
                          int initialCapacity,
                          float loadFactor)

Constructs a new, empty map with the specified Identitor, initial capacity and the specified load factor.

Parameters:

identitor - the Identitor for this Map

initialCapacity - the initial capacity of the AbstractHashMap.

loadFactor - the load factor of the AbstractHashMap

Throws:

java.lang.IllegalArgumentException - if the initial capacity is less than zero, or if the load factor is nonpositive.

AbstractHashMap

protected AbstractHashMap(int initialCapacity,
                          float loadFactor)

Constructs a new, empty map with a DefaultIdentitor, the specified initial capacity and the specified load factor.

Parameters:

initialCapacity - the initial capacity of the AbstractHashMap.

loadFactor - the load factor of the AbstractHashMap

Throws:

java.lang.IllegalArgumentException - if the initial capacity is less than zero, or if the load factor is nonpositive.

AbstractHashMap

protected AbstractHashMap(Identitor identitor,
                          int initialCapacity)

Constructs a new, empty map with the specified Identitor, initial capacity and default load factor, which is 0.75.

Parameters:

identitor - the Identitor for this Mao

initialCapacity - the initial capacity of the AbstractHashMap.

Throws:

java.lang.IllegalArgumentException - if the initial capacity is less than zero.

AbstractHashMap

protected AbstractHashMap(int initialCapacity)

Constructs a new, empty map with the specified initial capacity, DefaultIdentitor, and default load factor, which is 0.75.

Parameters:

initialCapacity - the initial capacity of the AbstractHashMap.

Throws:

java.lang.IllegalArgumentException - if the initial capacity is less than zero.

AbstractHashMap

protected AbstractHashMap(Identitor identitor)

Constructs a new, empty map with the specified Identitor, a default capacity and load factor, which is 0.75.

AbstractHashMap

protected AbstractHashMap()

Constructs a new, empty map with the DefaultIdentitor, a default capacity and load factor, which is 0.75.

AbstractHashMap

protected AbstractHashMap(Map t)

Constructs a new map with the same Identitor and mappings as the given map. The map is created with a capacity of twice the number of mappings in the given map or DEFAULTCAPACITY (whichever is greater), and a default load factor, which is 0.75.

Parameters:

t - the map whose mappings are to be placed in this map.

AbstractHashMap

protected AbstractHashMap(java.util.Map map)

Constructs a new Map with a DefaultIdentitor and the same mappings as the java.util.Map.

Method Detail

getIdentitor

public Identitor getIdentitor()

Returns the Identitor for this Map.

Specified by:

getIdentitor in interface Map

size

public int size()

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

Specified by:

size in interface Map

Returns:

the number of key-value mappings in this map.

isEmpty

public boolean isEmpty()

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

Specified by:

isEmpty in interface Map

Returns:

true if this map contains no key-value mappings.

containsKey

public boolean containsKey(java.lang.Object key)

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

Specified by:

containsKey in interface Map

Parameters:

key - key whose presence in this Map is to be tested.

Returns:

true if this map contains a mapping for the specified key.

Throws:

java.lang.NullPointerException - if key is null.

containsValue

public boolean containsValue(java.lang.Object value)

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

Specified by:

containsValue in interface Map

Parameters:

value - 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:

java.lang.NullPointerException - if value is null.

get

public java.lang.Object get(java.lang.Object key)

Returns the value to which this map maps the specified key. Returns null if the map contains no mapping for this key. A return value of null does indicate that the map contains no mapping for the key.

Specified by:

get in interface Map

Parameters:

key - key whose associated value is to be returned.

Returns:

the value to which this map maps the specified key.

Throws:

java.lang.NullPointerException - if the key is null.

getKeys

public Set getKeys()

Returns a set view of the keys contained in this map. The set is a shallow copy of the keys.

Specified by:

getKeys in interface Map

Returns:

a set view of the keys contained in this map.

getValues

public Collection getValues()

Returns a collection view of the values contained in this map. 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.

Specified by:

getValues in interface Map

Returns:

a collection view of the values contained in this map.

Throws:

java.lang.UnsupportedOperationException - for now

keyIterator

public java.util.Iterator keyIterator()

Returns an iterator over the keys.

Specified by:

keyIterator in interface Map

valueIterator

public java.util.Iterator valueIterator()

Returns an iterator over the values.

Specified by:

valueIterator in interface Map

containsAll

public boolean containsAll(Map map)

Returns true if this collection contains all of the Objects in the specified collection. This method uses the contains() and get() methods.

Specified by:

containsAll in interface Map

sameContentsAs

public boolean sameContentsAs(Map map)

Returns true if this Collection's contents are equal to c's.

Specified by:

sameContentsAs in interface Map

getJavaMap

public java.util.Map getJavaMap()

Return a java.util.Collection of these Objects.

Specified by:

getJavaMap in interface Map

getEntry

private AbstractHashMap.Entry getEntry(java.lang.Object key)

Returns the entry associated with the specified key in the AbstractHashMap. Returns null if the AbstractHashMap contains no mapping for this key.

put

protected java.lang.Object put(java.lang.Object key,
                               java.lang.Object value)

Puts the key,value pair in the map. Returns the previous value associated with key. If no value was associated, returns null.

Throws:

java.lang.NullPointerException - if the key or value is null.

remove

protected java.lang.Object remove(java.lang.Object key)

Removes the key, value pair from this Map. Returns the value associated with key, or null if no value was associated.

Throws:

java.lang.NullPointerException - if the key is null.

removeEntryForKey

private AbstractHashMap.Entry removeEntryForKey(java.lang.Object key)

Removes and returns the entry associated with the specified key in the AbstractHashMap. Returns null if the AbstractHashMap contains no mapping for this key.

removeEntry

void removeEntry(AbstractHashMap.Entry doomed)

Removes the specified entry from this AbstractHashMap (and increments modCount).

Throws:

java.util.ConcurrentModificationException - if the entry is not in the Map

removeMapping

private AbstractHashMap.Entry removeMapping(AbstractHashMap.Entry entry)

Returns removed entry, or null if no match. Subclass can override to modify entrySet().remove(Object) behavior.

clear

protected void clear()

Removes all mappings from this map.

rehash

private void rehash()

Rehashes the contents of this map into a new AbstractHashMap instance with a larger capacity. This method is called automatically when the number of keys in this map exceeds its capacity and load factor.

clone

public java.lang.Object clone()

Returns a shallow copy of this AbstractHashMap instance: the keys and values themselves are not cloned.

Overrides:

clone in class java.lang.Object

Returns:

a shallow copy of this map.

newEntry

protected AbstractHashMap.Entry newEntry(int hash,
                                         java.lang.Object key,
                                         java.lang.Object value,
                                         AbstractHashMap.Entry next)

Override this method and subclass Entry to create specialized Entries.

newEntryIterator

private java.util.Iterator newEntryIterator()

writeObject

private void writeObject(java.io.ObjectOutputStream s)
                  throws java.io.IOException

Save the state of the AbstractHashMap instance to a stream (i.e., serialize it).

Throws:

java.io.IOException

readObject

private void readObject(java.io.ObjectInputStream s)
                 throws java.io.IOException,
                        java.lang.ClassNotFoundException

Reconstitute the AbstractHashMap instance from a stream (i.e., deserialize it).

Throws:

java.io.IOException

java.lang.ClassNotFoundException

capacity

protected int capacity()

loadFactor

protected float loadFactor()

putAll

protected void putAll(Map map)

Copies all of the mappings from the specified map to this map (optional operation). These mappings will replace any mappings that this map had for any of the keys currently in the specified map.

This implementation iterates over the specified map's entrySet() collection, and calls this map's put operation once for each entry returned by the iteration.

Parameters:

map - mappings to be stored in this map.

Throws:

java.lang.UnsupportedOperationException - if the putAll operation is not supported by this map.

java.lang.ClassCastException - if the class of a key or value in the specified map prevents it from being stored in this map.

java.lang.IllegalArgumentException - if some aspect of a key or value in the specified map prevents it from being stored in this map.

java.lang.NullPointerException - this map does not permit null keys or values, and the specified key or value is null.

getPrincipleInterface

public java.lang.Class getPrincipleInterface()

Returns the class's principle interface for state comparisons. If two objects have different principle interfaces, they never have the same state.

Specified by:

getPrincipleInterface in interface HasState

sameStateAs

public boolean sameStateAs(HasState victem)

If two HasStates have the same internal state, return true.

For objects with subobjects, Generally this method should only return true if the internal objects are equal. Implement a contentsHaveSameState() method to determine if the contents have the same state.

Specified by:

sameStateAs in interface HasState

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object