XByteLinkedHashMap (Rumi 4.0.595 API)

java.lang.Object
- com.neeve.lang.XByteLinkedHashMap<V>

All Implemented Interfaces:

XByteMap<V>
```
public class XByteLinkedHashMap<V>
extends Object
implements XByteMap<V>
```
This class represents a hash map that avoid creation of garbage; smooth capacity increase and thread-safe without external synchronization when shared.

XByteLinkedHashMap 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 not the whole map. For example:[code] XLinkedHashMap sparseVector = new XLinkedHashMap().shared() ... // Put synchronized(index) { // 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. }[/code]

XByteLinkedHashMap.Entry can quickly be iterated over (forward or backward) without using iterators. For example:[code] XLinkedHashMap map = ...; for (XLinkedHashMap.Entry e = map.head(), end = map.tail(); (e = e.getNext()) != end;) { String key = e.getKey(); // No typecast necessary. Thread value = e.getValue(); // No typecast necessary. }[/code]

Alternatively The map can be iterated over using reuseableEntryIterator(), reuseableKeyIterator(), or reuseableValueIterator(). Utilization of these iterators does not introduce garbage because they are created once. However, these iterators may not be used concurrently by multiple threads as they are single instance by nature.
Custom map implementations may override the newEntry() method in order to return their own XByteLinkedHashMap.Entry implementation (with additional fields for example).

Shared maps do not use internal synchronization, except in case of concurrent modifications of the map structure (entries being 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). They can be used as very efficient lookup tables. For example:[code] public class Unit { static XLinkedHashMap labels = new XLinkedHashMap().shared(); ... public String toString() { String label = labels.get(this); // No synchronization. if (label != null) return label; label = makeLabel(); labels.put(this, label); return label; } }[/code]

Implementation Note: To maintain time-determinism, rehash/resize is performed only when the map's size is small. For large maps (size > 512), the map 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).

This class was based on collections code from http://javolution.org, but modified for use outside of realtime jvms.

Nested Class Summary

Nested Classes
Modifier and Type Class and Description

static class XByteLinkedHashMap.Entry<V>
This class represents a XByteLinkedHashMap entry.

Nested Classes
Modifier and Type	Class and Description
`static class`	`XByteLinkedHashMap.Entry<V>` This class represents a `XByteLinkedHashMap` entry.

Constructor Summary

Constructors
Constructor and Description
`XByteLinkedHashMap()` Creates a map whose capacity increment smoothly without large resize operations.
`XByteLinkedHashMap(int capacity)` Creates a map of specified maximum size (a full resize may occur if the specififed capacity is exceeded).
`XByteLinkedHashMap(XByteMap<? extends V> map)` Creates a map containing the specified entries, in the order they are returned by the map iterator.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`void`	`clear()` Removes all map's entries.
`boolean`	`containsKey(byte key)` Indicates if this map contains a mapping for the specified key.
`boolean`	`containsValue(Object value)` Indicates if this map associates one or more keys to the specified value.
`Set<XByteMap.Entry<V>>`	`entrySet()` Returns a `XCollection` view of the mappings contained in this map.
`boolean`	`equals(Object obj)` Compares the specified object with this map for equality.
`V`	`get(byte key)` Returns the value to which this map associates the specified key.
`XByteLinkedHashMap.Entry<V>`	`getEntry(byte key)` Returns the entry with the specified key.
`int`	`hashCode()` Returns the hash code value for this map.
`XByteLinkedHashMap.Entry<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).
`XByteSet`	`keySet()` Returns a `XCollection` view of the keys contained in this map.
`static <V> XByteLinkedHashMap<V>`	`newInstance()` Creates a new XLinkedHashMap.
`void`	`printStatistics(PrintStream out)` Prints the current statistics on this map.
`V`	`put(byte key, V value)` Associates the specified value with the specified key in this map.
`void`	`putAll(XByteMap<? extends V> map)` Copies all of the mappings from the specified map to this map.
`XByteLinkedHashMap.Entry<V>`	`putEntry(byte key, V value)` Associates the specified value with the specified key in this map and returns the corresponding entry.
`V`	`putIfAbsent(byte key, V value)` Associates the specified value only if the specified key is not already associated.
`V`	`remove(byte key)` Removes the entry for the specified key if present.
`XIterator<XByteMap.Entry<V>>`	`reuseableEntryIterator()` Returns a reusable value iterator.
`XByteIterator`	`reuseableKeyIterator()` Returns a reusable key iterator.
`XIterator<V>`	`reuseableValueIterator()` Returns a reusable value iterator.
`void`	`setSupportsIteratorModifications(boolean allowed)` Can be called to change whether or not iterators support iterator modifications.
`XByteLinkedHashMap<V>`	`shared()` Sets the shared status of this map (whether the map is thread-safe or not).
`int`	`size()` Returns the number of key-value mappings in this `XByteLinkedHashMap`.
`XByteLinkedHashMap.Entry<V>`	`tail()` Returns the tail entry of this map.
`String`	`toString()` Returns a string representation of this map.
`XByteMap<V>`	`unmodifiable()` Returns the unmodifiable view associated to this map.
`Collection<V>`	`values()` Returns a `XCollection` view of the values contained in this map.

Methods inherited from class java.lang.Object
getClass, notify, notifyAll, wait, wait, wait

- Constructor Detail
  - XByteLinkedHashMap
```
public XByteLinkedHashMap()
```
    Creates a map whose capacity increment smoothly without large resize operations.
  - XByteLinkedHashMap
```
public XByteLinkedHashMap(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.
  - XByteLinkedHashMap
```
public XByteLinkedHashMap(XByteMap<? 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
  - setSupportsIteratorModifications
```
public void setSupportsIteratorModifications(boolean allowed)
```
    Can be called to change whether or not iterators support iterator modifications.
    
    Parameters:
    
    allowed - True if iterators should allow modifications.
  - newInstance
```
public static <V> XByteLinkedHashMap<V> newInstance()
```
    Creates a new XLinkedHashMap.
    
    Returns:
    
    a new, preallocated or recycled map instance.
  - head
```
public final XByteLinkedHashMap.Entry<V> head()
```
    Returns the head entry of this map.
    
    Returns:
    
    the entry such as head().getNext() holds the first map entry.
  - tail
```
public final XByteLinkedHashMap.Entry<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 XByteLinkedHashMap.
    Note: If concurrent updates are performed, application should not rely upon the size during iterations.
    
    Specified by:
    
    size in interface XByteMap<V>
    
    Returns:
    
    this map's size.
    
    See Also:
    
    Map.size()
  - isEmpty
```
public final boolean isEmpty()
```
    Indicates if this map contains no key-value mappings.
    
    Specified by:
    
    isEmpty in interface XByteMap<V>
    
    Returns:
    
    true if this map contains no key-value mappings; false otherwise.
    
    See Also:
    
    Map.isEmpty()
  - containsKey
```
public final boolean containsKey(byte key)
```
    Indicates if this map contains a mapping for the specified key.
    
    Specified by:
    
    containsKey in interface XByteMap<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:
    
    NullPointerException - if the key is null.
    
    See Also:
    
    Map.containsKey(Object)
  - containsValue
```
public final boolean containsValue(Object value)
```
    Indicates if this map associates one or more keys to the specified value.
    
    Specified by:
    
    containsValue in interface XByteMap<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:
    
    NullPointerException - if the key is null.
    
    See Also:
    
    Map.containsValue(Object)
  - get
```
public final V get(byte 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 XByteMap<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:
    
    NullPointerException - if key is null.
    
    See Also:
    
    Map.get(Object)
  - getEntry
```
public final XByteLinkedHashMap.Entry<V> getEntry(byte 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(byte 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 XByteMap<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:
    
    NullPointerException - if the key is null.
    
    See Also:
    
    Map.put(Object, Object)
  - putEntry
```
public final XByteLinkedHashMap.Entry<V> putEntry(byte 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:
    
    NullPointerException - if the key is null.
  - putAll
```
public final void putAll(XByteMap<? extends V> map)
```
    Copies all of the mappings from the specified map to this map.
    
    Specified by:
    
    putAll in interface XByteMap<V>
    
    Parameters:
    
    map - the mappings to be stored in this map.
    
    Throws:
    
    NullPointerException - the specified map is null, or the specified map contains null keys.
  - putIfAbsent
```
public final V putIfAbsent(byte key,
                           V value)
```
    Associates the specified value only if the specified key is not already associated. This is equivalent to:[code] if (!map.containsKey(key)) return map.put(key, value); else return map.get(key);[/code] 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:
    
    NullPointerException - if the key is null.
  - remove
```
public final V remove(byte 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 XByteMap<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:
    
    NullPointerException - if the key is null.
  - shared
```
public XByteLinkedHashMap<V> shared()
```
    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).
    
    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.
  - 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 XByteMap<V>
  - equals
```
public boolean equals(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 XByteMap<V>
    
    Overrides:
    
    equals in class 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 XByteMap<V>
    
    Overrides:
    
    hashCode in class Object
    
    Returns:
    
    the hash code value for this map.
  - toString
```
public String toString()
```
    Returns a string representation of this map. The string representation consists of a list of key-value mappings in the order returned by the map's entrySet view's iterator, enclosed in braces ("{}"). Adjacent mappings are separated by the characters ", " (comma and space). Each key-value mapping is rendered as the key followed by an equals sign ("=") followed by the associated value. Keys and values are converted to strings as by String.valueOf(Object).
    
    Overrides:
    
    toString in class Object
    
    Returns:
    
    a string representation of this map
  - printStatistics
```
public void printStatistics(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 Collection<V> values()
```
    Returns a XCollection 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 XByteMap<V>
    
    Returns:
    
    a collection view of the values contained in this map (instance of XCollection).
  - entrySet
```
public final Set<XByteMap.Entry<V>> entrySet()
```
    Returns a XCollection view of the mappings contained in this map. Each element in the returned collection is a XLinkedHashMap.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 XByteMap<V>
    
    Returns:
    
    a collection view of the mappings contained in this map (instance of XCollection).
  - keySet
```
public final XByteSet keySet()
```
    Returns a XCollection 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 XByteMap<V> Returns: a set view of the keys contained in this map (instance of XCollection).
  reuseableKeyIterator public XByteIterator reuseableKeyIterator() Returns a reusable key iterator. This iterator may only be used by a single thread at a time. Prior to returning the iterator XCollectionIterator.toFirst() is called by this method to reset it to the beginning. Specified by: reuseableKeyIterator in interface XByteMap<V> Returns: The shared key iterator. reuseableValueIterator public XIterator<V> reuseableValueIterator() Returns a reusable value iterator. This iterator may only be used by a single thread at a time. Prior to returning the iterator XCollectionIterator.toFirst() is called by this method to reset it to the beginning. Specified by: reuseableValueIterator in interface XByteMap<V> Returns: The shared key iterator. reuseableEntryIterator public XIterator<XByteMap.Entry<V>> reuseableEntryIterator() Returns a reusable value iterator. This iterator may only be used by a single thread at a time. Prior to returning the iterator XCollectionIterator.toFirst() is called by this method to reset it to the beginning. Specified by: reuseableEntryIterator in interface XByteMap<V> Returns: The shared key iterator. unmodifiable public final XByteMap<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 XCollection views of this map keys and values are nonetheless obtainable (e.g. unmodifiable().keySet(), unmodifiable().values()). Returns: an unmodifiable view of this map.

Class XByteLinkedHashMap<V>

Nested Class Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

XByteLinkedHashMap

XByteLinkedHashMap

XByteLinkedHashMap

Method Detail

setSupportsIteratorModifications

newInstance

head

tail

size

isEmpty

containsKey

containsValue

get

getEntry

put

putEntry

putAll

putIfAbsent

remove

shared

isShared

clear

equals

hashCode

toString

printStatistics

values

entrySet

keySet

reuseableKeyIterator

reuseableValueIterator

reuseableEntryIterator

unmodifiable