javolution37.javolution.util

Class FastMap<K,V>

java.lang.Object

javolution37.javolution.realtime.RealtimeObject

javolution37.javolution.util.FastMap<K,V>

All Implemented Interfaces:

java.io.Serializable, java.util.Map<K,V>, Reusable, Realtime

public class FastMap<K,V>
extends RealtimeObject
implements java.util.Map<K,V>, Reusable, java.io.Serializable

This class represents a hash map with real-time behavior; smooth capacity increase and no rehashing ever performed.

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

FastMap.Entry can quickly be iterated over (forward or backward) without using iterators. For example:

     FastMap<String, Thread> map = new FastMap<String, Thread>();
     for (FastMap.Entry<String, Thread> e = map.head(), end = map.tail(); (e = e.getNext()) != end;) {
          String key = e.getKey(); // No typecast necessary.
          Thread value = e.getValue(); // No typecast necessary.
     }

FastMap may use custom key comparators; the default comparator is either DIRECT or REHASH based upon the current Javolution Configuration. Users may explicitly set the key comparator to DIRECT for optimum performance when the hash codes are well distributed for all run-time platforms (e.g. calculated hash codes).

Custom key comparators are extremely useful for value retrieval when map's keys and argument keys are not of the same class, such as String and Text (LEXICAL) or for identity maps (IDENTITY). For example:

     FastMap identityMap = new FastMap().setKeyComparator(FastComparator.IDENTITY);
     

FastMap marked shared are thread-safe without external synchronization and are often good substitutes for ConcurrentHashMap. For example:

     // Holds the units multiplication lookup table (persistent).
     static final FastMap<Unit, FastMap<Unit, Unit>> MULT_LOOKUP 
          = new FastMap<Unit, FastMap<Unit, Unit>>("mult-unit-lookup").setShared(true);
     
     // Fast and non-blocking (no synchronization necessary).     
     static Unit productOf(Unit left, Unit right) {
          FastMap<Unit, Unit> leftTable = MULT_LOOKUP.get(left);
          if (leftTable == null) return calculateProductOf(left, right);
          Unit result = leftTable.get(right);
          if (result == null) return calculateProductOf(left, right);
          return result; // Returns cache result.
    }

Finally, FastMap are reusable; they maintain an internal pool of Map.Entry objects. When an entry is removed from a map, it is automatically restored to its pool (unless the map is shared in which case the removed entry is candidate for garbage collection as it cannot be safely recycled).

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	FastMap.Entry<K,V> This class represents a FastMap entry.

Nested classes/interfaces inherited from class javolution37.javolution.realtime.RealtimeObject

RealtimeObject.Factory<T extends RealtimeObject>

Nested classes/interfaces inherited from interface javolution37.javolution.realtime.Realtime

Realtime.ObjectSpace

Constructor Summary

Constructors

Constructor and Description
FastMap() Creates a fast map of small initial capacity.
FastMap(int capacity) Creates a map of specified initial capacity; unless the map size reaches the specified capacity, operations on this map will not allocate memory (no lazy object creation).
FastMap(java.util.Map<? extends K,? extends V> map) Creates a map containing the specified entries, in the order they are returned by the map iterator.
FastMap(java.lang.String id) Creates a persistent map associated to the specified unique identifier (convenience method).

Method Summary

Modifier and Type	Method and Description
void	clear() Removes all map's entries.
boolean	containsKey(java.lang.Object key) Indicates if this map contains a mapping for the specified key.
boolean	containsValue(java.lang.Object value) Indicates if this map associates one or more keys to the specified value.
java.util.Set<java.util.Map.Entry<K,V>>	entrySet() Returns a FastCollection view of the mappings contained in this map.
boolean	equals(java.lang.Object obj) Compares the specified object with this map for equality.
V	get(java.lang.Object key) Returns the value to which this map associates the specified key.
FastMap.Entry<K,V>	getEntry(java.lang.Object key) Returns the entry with the specified key.
FastComparator	getKeyComparator() Returns the key comparator for this fast map.
FastComparator	getValueComparator() Returns the value comparator for this fast map.
int	hashCode() Returns the hash code value for this map.
FastMap.Entry<K,V>	head() Returns the head entry of this map.
boolean	isEmpty() Indicates if this map contains no key-value mappings.
boolean	isShared() Indicates if this map supports concurrent operations without synchronization (default unshared).
java.util.Set<K>	keySet() Returns a FastCollection view of the keys contained in this map.
boolean	move(Realtime.ObjectSpace os) Moves this real-time object to the specified object space.
static <K,V> FastMap<K,V>	newInstance() Returns a map allocated from the stack when executing in a PoolContext.
void	printStatistics(java.io.PrintStream out) Prints the current statistics on this map.
V	put(K key, V value) Associates the specified value with the specified key in this map.
void	putAll(java.util.Map<? extends K,? extends V> map) Copies all of the mappings from the specified map to this map.
V	remove(java.lang.Object key) Removes the entry for the specified key if present.
void	reset() Resets the internal state of this object to its default values.
FastMap<K,V>	setKeyComparator(FastComparator keyComparator) Sets the key comparator for this fast map.
FastMap<K,V>	setShared(boolean isShared) Sets the shared status of this map (whether the map is thread-safe or not).
FastMap<K,V>	setValueComparator(FastComparator valueComparator) Sets the value comparator for this map.
int	size() Returns the number of key-value mappings in this FastMap.
FastMap.Entry<K,V>	tail() Returns the tail entry of this map.
Text	toText() Returns the textual representation of this map.
java.util.Map<K,V>	unmodifiable() Returns the unmodifiable view associated to this map.
java.util.Collection<V>	values() Returns a FastCollection view of the values contained in this map.

Methods inherited from class javolution37.javolution.realtime.RealtimeObject

export, moveHeap, preserve, toString, unpreserve

Methods inherited from class java.lang.Object

getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Map

compute, computeIfAbsent, computeIfPresent, forEach, getOrDefault, merge, putIfAbsent, remove, replace, replace, replaceAll

Constructor Detail

FastMap

public FastMap()

Creates a fast map of small initial capacity.

FastMap

public FastMap(java.lang.String id)

Creates a persistent map associated to the specified unique identifier (convenience method).

Parameters:

id - the unique identifier for this map.

Throws:

java.lang.IllegalArgumentException - if the identifier is not unique.

See Also:

PersistentReference

FastMap

public FastMap(int capacity)

Creates a map of specified initial capacity; unless the map size reaches the specified capacity, operations on this map will not allocate memory (no lazy object creation).

Parameters:

capacity - the initial capacity.

FastMap

public FastMap(java.util.Map<? extends K,? extends V> map)

Creates a map containing the specified entries, in the order they are returned by the map iterator.

Parameters:

map - the map whose entries are to be placed into this map.

Method Detail

newInstance

public static <K,V> FastMap<K,V> newInstance()

Returns a map allocated from the stack when executing in a PoolContext.

Returns:

a new, pre-allocated or recycled map instance.

head

public final FastMap.Entry<K,V> head()

Returns the head entry of this map.

Returns:

the entry such as head().getNext() holds the first map entry.

tail

public final FastMap.Entry<K,V> tail()

Returns the tail entry of this map.

Returns:

the entry such as tail().getPrevious() holds the last map entry.

size

public final int size()

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

Specified by:

size in interface java.util.Map<K,V>

Returns:

this map's size.

isEmpty

public final boolean isEmpty()

Indicates if this map contains no key-value mappings.

Specified by:

isEmpty in interface java.util.Map<K,V>

Returns:

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

containsKey

public final boolean containsKey(java.lang.Object key)

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

Specified by:

containsKey in interface java.util.Map<K,V>

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:

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

containsValue

public final boolean containsValue(java.lang.Object value)

Indicates if this map associates one or more keys to the specified value.

Specified by:

containsValue in interface java.util.Map<K,V>

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:

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

get

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

Returns the value to which this map associates the specified key.

Specified by:

get in interface java.util.Map<K,V>

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:

java.lang.NullPointerException - if key is null.

getEntry

public final FastMap.Entry<K,V> 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 final V put(K key,
                   V value)

Associates the specified value with the specified key in this map. If this map previously contained a mapping for this key, the old value is replaced. For shared map internal synchronization is automatically performed.

Specified by:

put in interface java.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. A null return can also indicate that the map previously associated null with the specified key.

Throws:

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

putAll

public final void putAll(java.util.Map<? extends K,? extends V> map)

Copies all of the mappings from the specified map to this map.

Specified by:

putAll in interface java.util.Map<K,V>

Parameters:

map - the mappings to be stored in this map.

Throws:

java.lang.NullPointerException - the specified map is null, or the specified map contains null keys.

remove

public final V remove(java.lang.Object key)

Removes the entry for the specified key if present. The entry is recycled if the map is not marked as shared; otherwise the entry is candidate for garbage collection.

Note: Shared maps in ImmortalMemory (e.g. static) should not remove their entries as it could cause a memory leak (ImmortalMemory is never garbage collected), instead they should set their entry values to null.

Specified by:

remove in interface java.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. A null return can also indicate that the map previously associated null with the specified key.

Throws:

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

setShared

public FastMap<K,V> setShared(boolean isShared)

Sets the shared status of this map (whether the map is thread-safe or not). Shared maps are typically used for lookup table (e.g. static instances in ImmortalMemory). They support concurrent access (e.g. iterations) without synchronization, the maps updates themselves are synchronized internally.

Unlike ConcurrentHashMap access to a shared map never blocks. Retrieval reflects the map state not older than the last time the accessing thread has been synchronized (for multi-processors systems synchronizing ensures that the CPU internal cache is not stale).

Parameters:

isShared - true if this map is shared and thread-safe; false otherwise.

Returns:

this

isShared

public boolean isShared()

Indicates if this map supports concurrent operations without synchronization (default unshared).

Returns:

true if this map is thread-safe; false otherwise.

setKeyComparator

public FastMap<K,V> setKeyComparator(FastComparator keyComparator)

Sets the key comparator for this fast map.

Parameters:

keyComparator - the key comparator.

Returns:

this

getKeyComparator

public FastComparator getKeyComparator()

Returns the key comparator for this fast map.

Returns:

the key comparator.

setValueComparator

public FastMap<K,V> setValueComparator(FastComparator valueComparator)

Sets the value comparator for this map.

Parameters:

valueComparator - the value comparator.

Returns:

this

getValueComparator

public FastComparator getValueComparator()

Returns the value comparator for this fast map.

Returns:

the value comparator.

clear

public final void clear()

Removes all map's entries. The entries are removed and recycled; unless this map is shared in which case the entries are candidate for garbage collection.

Note: Shared maps in ImmortalMemory (e.g. static) should not remove their entries as it could cause a memory leak (ImmortalMemory is never garbage collected), instead they should set their entry values to null.

Specified by:

clear in interface java.util.Map<K,V>

equals

public boolean equals(java.lang.Object obj)

Compares the specified object with this map 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).

Specified by:

equals in interface java.util.Map<K,V>

Overrides:

equals in class java.lang.Object

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.

hashCode

public int hashCode()

Returns the hash code value for this map.

Specified by:

hashCode in interface java.util.Map<K,V>

Overrides:

hashCode in class java.lang.Object

Returns:

the hash code value for this map.

toText

public Text toText()

Returns the textual representation of this map.

Specified by:

toText in interface Realtime

Overrides:

toText in class RealtimeObject

Returns:

the textual representation of the entry set.

printStatistics

public void printStatistics(java.io.PrintStream out)

Prints the current statistics on this map. This method may help identify poorly defined hash functions. An average collision of less than 50% is typically acceptable.

Parameters:

out - the stream to use for output (e.g. System.out)

values

public final java.util.Collection<V> values()

Returns a FastCollection 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:

values in interface java.util.Map<K,V>

Returns:

a collection view of the values contained in this map (instance of FastCollection).

entrySet

public final java.util.Set<java.util.Map.Entry<K,V>> entrySet()

Returns a FastCollection view of the mappings contained in this map. Each element in the returned collection is a FastMap.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.

Specified by:

entrySet in interface java.util.Map<K,V>

Returns:

a collection view of the mappings contained in this map (instance of FastCollection).

keySet

public final java.util.Set<K> keySet()

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

Specified by:

keySet in interface java.util.Map<K,V>

Returns:

a set view of the keys contained in this map (instance of FastCollection).

unmodifiable

public final java.util.Map<K,V> unmodifiable()

Returns the unmodifiable view associated to this map. Attempts to modify the returned map or to directly access its (modifiable) map entries (e.g. unmodifiable().entrySet()) result in an UnsupportedOperationException being thrown. Unmodifiable FastCollection views of this map keys and values are nonetheless obtainable (e.g. unmodifiable().keySet(), unmodifiable().values()).

Returns:

an unmodifiable view of this map.

move

public boolean move(Realtime.ObjectSpace os)

Description copied from interface: Realtime

Moves this real-time object to the specified object space.

Specified by:

move in interface Realtime

Overrides:

move in class RealtimeObject

Parameters:

os - the object space to move this real-time object to.

Returns:

true if the move has to be propagated to external real-time references; false otherwise.

reset

public void reset()

Description copied from interface: Reusable

Resets the internal state of this object to its default values.

Specified by:

reset in interface Reusable