Class OrderedFastHashMap<K,V>

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:
Serializable, Map<K,V>

public class OrderedFastHashMap<K,V> extends Object implements Map<K,V>, 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:
  • Field Details

    • FREE_KEY_

      private static final Object FREE_KEY_
    • REMOVED_KEY_

      private static final Object REMOVED_KEY_
    • FILLFACTOR_

      private static final double FILLFACTOR_
      See Also:
    • mapData_

      private Object[] mapData_
    • mapThreshold_

      private int mapThreshold_
    • mapSize_

      private int mapSize_
    • orderedList_

      private int[] orderedList_
    • orderedListSize_

      private int orderedListSize_
  • Constructor Details

    • 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 Details

    • get

      public V get(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 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(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 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 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 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 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 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 Map<K,V>
    • getStartIndex

      private int getStartIndex(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 262.
      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 230 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:
      IllegalArgumentException - if the necessary size is larger than 230.
    • 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:
      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:
      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:
      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:
      IndexOutOfBoundsException - when the ask for the position is invalid
    • put

      public V put(K key, V value)
      Specified by:
      put in interface 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(Object key)
      Checks of a key is in the map.
      Specified by:
      containsKey in interface Map<K,V>
      Parameters:
      key - the key to check
      Returns:
      true of the key is in the map, false otherwise
    • containsValue

      public boolean containsValue(Object value)
      Specified by:
      containsValue in interface Map<K,V>
    • isEmpty

      public boolean isEmpty()
      Specified by:
      isEmpty in interface Map<K,V>
    • entrySet

      public Set<Map.Entry<K,V>> entrySet()
      Specified by:
      entrySet in interface Map<K,V>
    • keySet

      public Set<K> keySet()
      Specified by:
      keySet in interface Map<K,V>
    • reverse

      public void reverse()
      Just reverses the ordering of the map as created so far.
    • readObject

      private void readObject(ObjectInputStream aInputStream) throws ClassNotFoundException, IOException
      We have to overwrite the export due to the use of static object as marker
      Parameters:
      aInputStream - the inputstream to read from
      Throws:
      IOException - when the reading from the source fails
      ClassNotFoundException - in case we cannot restore a class
    • writeObject

      private void writeObject(ObjectOutputStream aOutputStream) throws IOException
      We have to overwrite the export due to the use of static object as marker
      Parameters:
      aOutputStream - the stream to write to
      Throws:
      IOException - in case we have issue writing our data to the stream
    • putAll

      public void putAll(Map<? extends K,? extends V> src)
      Specified by:
      putAll in interface Map<K,V>
    • orderedListAdd

      private void orderedListAdd(OrderedFastHashMap.Position listPosition, int position)
    • orderedListRemove

      private void orderedListRemove(int position)
    • toString

      public String toString()
      Overrides:
      toString in class Object