Overview | Package | Class | Tree | Deprecated | Index | Help
| J avolution v5.3 (J2SE 1.5+)
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## javolution.util
Class FastMap<K,V>

    java.lang.Object
      javolution.util.FastMap<K,V>

All Implemented Interfaces:
  java.io.Serializable, java.util.Map<K,V>, Realtime, Reusable, XMLSerializable

    public class FastMap<K,V>

extends java.lang.Object
implements java.util.Map<K,V>, Reusable, XMLSerializable, Realtime

This class represents a hash map with real-time behavior; smooth capacity increase and thread-safe without external synchronization when `shared`.

`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). If the map is marked `shared` then all operations are thread-safe including iterations over the map's collections. Unlike `ConcurrentHashMap`, `access` never blocks; retrieval reflects the map state not older than the last time the accessing threads have been synchronized (for multi-processors systems synchronizing ensures that the CPU internal cache is not stale). In most application it is not a problem because thread synchronization is done at high level (e.g. scheduler) and threads run freely (and quickly) until the next synchronization point. In some cases the "happen before" guarantee is necessary (e.g. to ensure unicity) and threads have to be synchronized explicitly. Whenever possible such synchronization should be performed on the key object itself and the not the whole map. For example:``

         FastMap<Index, Object> sparseVector = new FastMap<Index, Object>().setShared(true)
         ... // Put
         synchronized(index) { // javolution.util.Index instances are unique.
             sparseVector.put(index, value);
         }
         ... // Get
         synchronized(index) { // Blocking only when accessing the same index.
             value = sparseVector.get(index); // Latest value guaranteed.
         }

`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`)), to substitute more efficient hash code calculations (`STRING`) or for identity maps (`IDENTITY`):``

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

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

         FastMap<String, Thread> map = ...;
         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.
         }

Custom map implementations may override the `newEntry()` method in order to return their own `FastMap.Entry` implementation (with additional fields for example).

`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).

Shared maps do not use internal synchronization, except in case of concurrent modifications of the map structure (entry added/deleted). Reads and iterations are never synchronized and never blocking. With regards to the memory model, shared maps are equivalent to shared non-volatile variables (no "happen before" guarantee). There are typically used as lookup tables. For example:``

         public class Unit {
             static FastMap<Unit, String> labels = new FastMap().setShared(true);
             ...
             public String toString() {
                 String label = labels.get(this); // No synchronization.
                 return label != null ? label : makeLabel();
             }
        }

Implementation Note: To maintain time-determinism, rehash/resize is performed only when the map's size is small (see chart). For large maps (size > 512), the collection is divided recursively into (64) smaller sub-maps. The cost of the dispatching (based upon hashcode value) has been measured to be at most 20% of the access time (and most often way less).

Version:
  5.2, September 11, 2007
Author:
  Jean-Marie Dautelle
See Also:
  Serialized Form

Nested Class Summary
`static class` | `FastMap.Entry<K,V>` This class represents a `FastMap` entry.

Constructor Summary
`FastMap()` Creates a map whose capacity increment smoothly without large resize operations.
`FastMap(int capacity)` Creates a map of specified maximum size (a full resize may occur if the specififed capacity is exceeded).
`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
`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<? super K>` | `getKeyComparator()` Returns the key comparator for this fast map.
`FastComparator<? super V>` | `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.
`protected FastMap.Entry<K,V>` | `newEntry()` Returns a new entry for this map; this method can be overriden by custom map implementations.
`static
`<K,V> FastMap<K,V>`
` | `newInstance()` Returns a potentially `recycled` map instance.
`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.
`FastMap.Entry<K,V>` | `putEntry(K key, V value)` Associates the specified value with the specified key in this map and returns the corresponding entry.
`V` | `putIfAbsent(K key, V value)` Associates the specified value only if the specified key is not already associated.
`static void` | `recycle(FastMap instance)` Recycles the specified map instance.
`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<V,K>` | `reverse()` Returns the reverse mapping of this map (for which the keys are this map's values and the values are this map's keys).
`FastMap<K,V>` | `setKeyComparator(FastComparator<? super K> 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<? super V> 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.
`java.lang.String` | `toString()` Returns the `String` representation of this `FastMap`.
`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 java.lang.Object
`clone, finalize, getClass, notify, notifyAll, wait, wait, wait`

Constructor Detail

### FastMap

    public FastMap()

  Creates a map whose capacity increment smoothly without large resize operations.

### 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:
    `PersistentContext.Reference`

### FastMap

    public FastMap(int capacity)

  Creates a map of specified maximum size (a full resize may occur if the specififed capacity is exceeded).

  Parameters:
    `capacity` - the maximum 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 potentially `recycled` map instance.

  Returns:
    a new, preallocated or recycled map instance.

### recycle

    public static void recycle(FastMap instance)

  Recycles the specified map instance.

  Parameters:
    `instance` - the map instance to recycle.

### reverse

    public final FastMap<V,K> reverse()

  Returns the reverse mapping of this map (for which the keys are this map's values and the values are this map's keys).

  Returns:
    the map having for keys this map values and for values this map's key.

### 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`.

  Note: If concurrent updates are performed, application should not rely upon the size during iterations.

  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. This method is always thread-safe regardless whether or not the map is marked `shared`.

  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. This method is always thread-safe without synchronization.

  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 performed only when new entries are created.

  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`.

### putEntry

    public final FastMap.Entry<K,V> putEntry(K key,
                                             V value)

  Associates the specified value with the specified key in this map and returns the corresponding entry.

  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 entry being added.
  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.

### putIfAbsent

    public final V putIfAbsent(K key,
                               V value)

  Associates the specified value only if the specified key is not already associated. This is equivalent to:`

         if (!map.containsKey(key))
             return map.put(key, value);
         else
             return map.get(key);

  ` except that for shared maps the action is performed atomically. For shared maps, this method guarantees that if two threads try to put the same key concurrently only one of them will succeed.

  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`.

### 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<? super K> keyComparator)

  Sets the key comparator for this fast map.

  Parameters:
    `keyComparator` - the key comparator.
  Returns:
    `this`

### getKeyComparator

    public FastComparator<? super K> getKeyComparator()

  Returns the key comparator for this fast map.

  Returns:
    the key comparator.

### setValueComparator

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

  Sets the value comparator for this map.

  Parameters:
    `valueComparator` - the value comparator.
  Returns:
    `this`

### getValueComparator

    public FastComparator<? super V> 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`
  Returns:
    the textual representation of the entry set.

### toString

    public final java.lang.String toString()

  Returns the `String` representation of this `FastMap`.

  Overrides:
    `toString` in class `java.lang.Object`
  Returns:
    `toText().toString()`

### newEntry

    protected FastMap.Entry<K,V> newEntry()

  Returns a new entry for this map; this method can be overriden by custom map implementations.

  Returns:
    a new entry.

### printStatistics

    public void printStatistics(java.io.PrintStream out)

  Prints the current statistics on this map. This method may help identify poorly defined hash functions. The average distance should be less than 20% (most of the entries are in their slots or close).

  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.

### 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`

Overview | Package | Class | Tree | Deprecated | Index | Help
| J avolution v5.3 (J2SE 1.5+)
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

Copyright © 2005 - 2009 Javolution.