java.lang.Object
- org.htmlunit.util.OrderedFastHashMap<K,V>

Type Parameters:

K - the type of the key

V - the type of the value

All Implemented Interfaces:

java.io.Serializable, java.util.Map<K,V>
```
public class OrderedFastHashMap<K,V>
extends java.lang.Object
implements java.util.Map<K,V>, java.io.Serializable
```
Simple and efficient linked map or better ordered map implementation to replace the default linked list which is heavy. This map does not support null and it is not thread-safe. It implements the map interface but only for compatibility reason in the sense of replacing a regular map. Iterator and streaming methods are either not implemented or less efficient. It goes the extra mile to avoid the overhead of wrapper objects. Because you typically know what you do, we run minimal index checks only and rely on the default exceptions by Java. Why should we do things twice? Important Note: This is meant for small maps because to save on memory allocation and churn, we are not keeping a wrapper for a reference from the map to the list, only from the list to the map. Hence when you remove a key, we have to iterate the entire list. Mostly, half of it most likely, but still expensive enough. When you have something small like 10 to 20 entries, this won't matter that much especially when a remove might be a rare event. This is based on FashHashMap from XLT which is based on a version from: https://github.com/mikvor/hashmapTest/blob/master/src/main/java/map/objobj/ObjObjMap.java No concrete license specified at the source. The project is public domain.

See Also:

Serialized Form

Nested Class Summary

Nested Classes
Modifier and Type	Class	Description
`(package private) static class`	`OrderedFastHashMap.Entry<K,V>`	Well, we need that to satisfy the map implementation concept.
`(package private) static class`	`OrderedFastHashMap.OrderedEntrySet<K,V>`	This set does not support any modifications through its interface.
`(package private) static class`	`OrderedFastHashMap.OrderedKeySet<K,V>`
`private static class`	`OrderedFastHashMap.Position`	Helper for identifying if we need to position our new entry differently.

Field Summary

Fields
Modifier and Type	Field	Description
`private static double`	`FILLFACTOR_`
`private static java.lang.Object`	`FREE_KEY_`
`private java.lang.Object[]`	`mapData_`
`private int`	`mapSize_`
`private int`	`mapThreshold_`
`private int[]`	`orderedList_`
`private int`	`orderedListSize_`
`private static java.lang.Object`	`REMOVED_KEY_`

Constructor Summary

Constructors
Constructor	Description
`OrderedFastHashMap()`	Default constructor which create an ordered map with default size.
`OrderedFastHashMap(int size)`	Custom constructor to get a map with a custom size and fill factor.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method	Description
`V`	`add(K key, V value)`
`V`	`addFirst(K key, V value)`
`V`	`addLast(K key, V value)`
`private static int`	`arraySize(int expected, double f)`	Returns the least power of two smaller than or equal to 2³⁰ and larger than or equal to `Math.ceil( expected / f )`.
`void`	`clear()`	Clears the map, reuses the data structure by clearing it out.
`boolean`	`containsKey(java.lang.Object key)`	Checks of a key is in the map.
`boolean`	`containsValue(java.lang.Object value)`
`java.util.Set<java.util.Map.Entry<K,V>>`	`entrySet()`
`V`	`get(java.lang.Object key)`	Get a value for a key, any key type is permitted due to the nature of the Map interface.
`OrderedFastHashMap.Entry<K,V>`	`getEntry(int index)`	Returns an entry consisting of key and value at a given position.
`V`	`getFirst()`
`K`	`getKey(int index)`	Returns the key at a certain position of the ordered list that keeps the addition order of this map.
`V`	`getLast()`
`private int`	`getStartIndex(java.lang.Object key)`	Get us the start index from where we search or insert into the map
`V`	`getValue(int index)`	Returns the value at a certain position of the ordered list that keeps the addition order of this map.
`boolean`	`isEmpty()`
`java.util.List<K>`	`keys()`	Returns a list of all keys in order of addition.
`java.util.Set<K>`	`keySet()`
`private static long`	`nextPowerOfTwo(long x)`	Return the least power of two greater than or equal to the specified value.
`private void`	`orderedListAdd(OrderedFastHashMap.Position listPosition, int position)`
`private void`	`orderedListRemove(int position)`
`V`	`put(K key, V value)`
`private V`	`put(K key, V value, OrderedFastHashMap.Position listPosition)`	Adds a key and value to the internal position structure
`void`	`putAll(java.util.Map<? extends K,? extends V> src)`
`private void`	`readObject(java.io.ObjectInputStream aInputStream)`	We have to overwrite the export due to the use of static object as marker
`private void`	`rehash(int newCapacity)`	Rehash the map.
`V`	`remove(int index)`	Removes a key and value from this map based on the position in the backing list, rather by key as usual.
`V`	`remove(java.lang.Object key)`	Remove a key from the map.
`V`	`removeFirst()`
`V`	`removeLast()`
`void`	`reverse()`	Just reverses the ordering of the map as created so far.
`int`	`size()`	Returns the size of the map, effectively the number of entries.
`java.lang.String`	`toString()`
`java.util.List<V>`	`values()`	Returns a list of all values ordered by when the key was added.
`private void`	`writeObject(java.io.ObjectOutputStream aOutputStream)`	We have to overwrite the export due to the use of static object as marker

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Map
compute, computeIfAbsent, computeIfPresent, equals, forEach, getOrDefault, hashCode, merge, putIfAbsent, remove, replace, replace, replaceAll

- Field Detail
  - FREE_KEY_
```
private static final java.lang.Object FREE_KEY_
```
  - REMOVED_KEY_
```
private static final java.lang.Object REMOVED_KEY_
```
  - FILLFACTOR_
```
private static final double FILLFACTOR_
```
    See Also:
    
    Constant Field Values
  - mapData_
```
private java.lang.Object[] mapData_
```
  - mapThreshold_
```
private int mapThreshold_
```
  - mapSize_
```
private int mapSize_
```
  - orderedList_
```
private int[] orderedList_
```
  - orderedListSize_
```
private int orderedListSize_
```
- Constructor Detail
  - OrderedFastHashMap
```
public OrderedFastHashMap()
```
    Default constructor which create an ordered map with default size.
  - OrderedFastHashMap
```
public OrderedFastHashMap(int size)
```
    Custom constructor to get a map with a custom size and fill factor. We are not spending time on range checks, rather use a default if things are wrong.
    
    Parameters:
    
    size - the size to use, must 0 or positive, negative values default to 0
- Method Detail
  - get
```
public V get(java.lang.Object key)
```
    Get a value for a key, any key type is permitted due to the nature of the Map interface.
    
    Specified by:
    
    get in interface java.util.Map<K,V>
    
    Parameters:
    
    key - the key
    
    Returns:
    
    the value or null, if the key does not exist
  - put
```
private V put(K key,
              V value,
              OrderedFastHashMap.Position listPosition)
```
    Adds a key and value to the internal position structure
    
    Parameters:
    
    key - the key
    
    value - the value to store
    
    listPosition - defines where to add the new key/value pair
    
    Returns:
    
    the old value or null if they key was not known before
  - remove
```
public V remove(java.lang.Object key)
```
    Remove a key from the map. Returns the stored value or null of the key is not known.
    
    Specified by:
    
    remove in interface java.util.Map<K,V>
    
    Parameters:
    
    key - the key to remove
    
    Returns:
    
    the stored value or null if the key does not exist
  - size
```
public int size()
```
    Returns the size of the map, effectively the number of entries.
    
    Specified by:
    
    size in interface java.util.Map<K,V>
    
    Returns:
    
    the size of the map
  - rehash
```
private void rehash(int newCapacity)
```
    Rehash the map.
    
    Parameters:
    
    newCapacity - the new size of the map
  - keys
```
public java.util.List<K> keys()
```
    Returns a list of all keys in order of addition. This is an expensive operation, because we get a static list back that is not backed by the implementation. Changes to the returned list are not reflected in the map.
    
    Returns:
    
    a list of keys as inserted into the map
  - values
```
public java.util.List<V> values()
```
    Returns a list of all values ordered by when the key was added. This is an expensive operation, because we get a static list back that is not backed by the implementation. Changes to the returned list are not reflected in the map.
    
    Specified by:
    
    values in interface java.util.Map<K,V>
    
    Returns:
    
    a list of values
  - clear
```
public void clear()
```
    Clears the map, reuses the data structure by clearing it out. It won't shrink the underlying arrays!
    
    Specified by:
    
    clear in interface java.util.Map<K,V>
  - getStartIndex
```
private int getStartIndex(java.lang.Object key)
```
    Get us the start index from where we search or insert into the map
    
    Parameters:
    
    key - the key to calculate the position for
    
    Returns:
    
    the start position
  - nextPowerOfTwo
```
private static long nextPowerOfTwo(long x)
```
    Return the least power of two greater than or equal to the specified value.
    Note that this function will return 1 when the argument is 0.
    
    Parameters:
    
    x - a long integer smaller than or equal to 2⁶².
    
    Returns:
    
    the least power of two greater than or equal to the specified value.
  - arraySize
```
private static int arraySize(int expected,
                             double f)
```
    Returns the least power of two smaller than or equal to 2³⁰ and larger than or equal to Math.ceil( expected / f ).
    
    Parameters:
    
    expected - the expected number of elements in a hash table.
    
    f - the load factor.
    
    Returns:
    
    the minimum possible size for a backing array.
    
    Throws:
    
    java.lang.IllegalArgumentException - if the necessary size is larger than 2³⁰.
  - getEntry
```
public OrderedFastHashMap.Entry<K,V> getEntry(int index)
```
    Returns an entry consisting of key and value at a given position. This position relates to the ordered key list that maintain the addition order for this map.
    
    Parameters:
    
    index - the position to fetch
    
    Returns:
    
    an entry of key and value
    
    Throws:
    
    java.lang.IndexOutOfBoundsException - when the ask for the position is invalid
  - getKey
```
public K getKey(int index)
```
    Returns the key at a certain position of the ordered list that keeps the addition order of this map.
    
    Parameters:
    
    index - the position to fetch
    
    Returns:
    
    the key at this position
    
    Throws:
    
    java.lang.IndexOutOfBoundsException - when the ask for the position is invalid
  - getValue
```
public V getValue(int index)
```
    Returns the value at a certain position of the ordered list that keeps the addition order of this map.
    
    Parameters:
    
    index - the position to fetch
    
    Returns:
    
    the value at this position
    
    Throws:
    
    java.lang.IndexOutOfBoundsException - when the ask for the position is invalid
  - remove
```
public V remove(int index)
```
    Removes a key and value from this map based on the position in the backing list, rather by key as usual.
    
    Parameters:
    
    index - the position to remove the data from
    
    Returns:
    
    the value stored
    
    Throws:
    
    java.lang.IndexOutOfBoundsException - when the ask for the position is invalid
  - put
```
public V put(K key,
             V value)
```
    Specified by:
    
    put in interface java.util.Map<K,V>
  - addFirst
```
public V addFirst(K key,
                  V value)
```
  - add
```
public V add(K key,
             V value)
```
  - addLast
```
public V addLast(K key,
                 V value)
```
  - getFirst
```
public V getFirst()
```
  - getLast
```
public V getLast()
```
  - removeFirst
```
public V removeFirst()
```
  - removeLast
```
public V removeLast()
```
  - containsKey
```
public boolean containsKey(java.lang.Object key)
```
    Checks of a key is in the map.
    
    Specified by:
    
    containsKey in interface java.util.Map<K,V>
    
    Parameters:
    
    key - the key to check
    
    Returns:
    
    true of the key is in the map, false otherwise
  - containsValue
```
public boolean containsValue(java.lang.Object value)
```
    Specified by:
    
    containsValue in interface java.util.Map<K,V>
  - isEmpty
```
public boolean isEmpty()
```
    Specified by:
    
    isEmpty in interface java.util.Map<K,V>
  - entrySet
```
public java.util.Set<java.util.Map.Entry<K,V>> entrySet()
```
    Specified by:
    
    entrySet in interface java.util.Map<K,V>
  - keySet
```
public java.util.Set<K> keySet()
```
    Specified by:
    
    keySet in interface java.util.Map<K,V>
  - reverse
```
public void reverse()
```
    Just reverses the ordering of the map as created so far.
  - readObject
```
private void readObject(java.io.ObjectInputStream aInputStream)
                 throws java.lang.ClassNotFoundException,
                        java.io.IOException
```
    We have to overwrite the export due to the use of static object as marker
    
    Parameters:
    
    aInputStream - the inputstream to read from
    
    Throws:
    
    java.io.IOException - when the reading from the source fails
    
    java.lang.ClassNotFoundException - in case we cannot restore a class
  - writeObject
```
private void writeObject(java.io.ObjectOutputStream aOutputStream)
                  throws java.io.IOException
```
    We have to overwrite the export due to the use of static object as marker
    
    Parameters:
    
    aOutputStream - the stream to write to
    
    Throws:
    
    java.io.IOException - in case we have issue writing our data to the stream
  - putAll
```
public void putAll(java.util.Map<? extends K,? extends V> src)
```
    Specified by:
    
    putAll in interface java.util.Map<K,V>
  - orderedListAdd
```
private void orderedListAdd(OrderedFastHashMap.Position listPosition,
                            int position)
```
  - orderedListRemove
```
private void orderedListRemove(int position)
```
  - toString
```
public java.lang.String toString()
```
    Overrides:
    
    toString in class java.lang.Object

Class OrderedFastHashMap<K,​V>

Nested Class Summary

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Methods inherited from interface java.util.Map

Field Detail

FREE_KEY_

REMOVED_KEY_

FILLFACTOR_

mapData_

mapThreshold_

mapSize_

orderedList_

orderedListSize_

Constructor Detail

OrderedFastHashMap

OrderedFastHashMap

Method Detail

get

put

remove

size

rehash

keys

values

clear

getStartIndex

nextPowerOfTwo

arraySize

getEntry

getKey

getValue

remove

put

addFirst

add

addLast

getFirst

getLast

removeFirst

removeLast

containsKey

containsValue

isEmpty

entrySet

keySet

reverse

readObject

writeObject

putAll

orderedListAdd

orderedListRemove

toString

Class OrderedFastHashMap<K,V>