Package org.htmlunit.util
Class OrderedFastHashMap<K,V>
- java.lang.Object
-
- org.htmlunit.util.OrderedFastHashMap<K,V>
-
- Type Parameters:
K
- the type of the keyV
- 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 230 and larger than or equal toMath.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 mapV
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 structurevoid
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 markerprivate 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
-
-
-
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.
-
put
private V put(K key, V value, OrderedFastHashMap.Position listPosition)
Adds a key and value to the internal position structure- Parameters:
key
- the keyvalue
- the value to storelistPosition
- 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.
-
size
public int size()
Returns the size of the map, effectively the number of entries.
-
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.
-
clear
public void clear()
Clears the map, reuses the data structure by clearing it out. It won't shrink the underlying arrays!
-
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 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 toMath.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 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:
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
-
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.
-
containsValue
public boolean containsValue(java.lang.Object value)
-
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 failsjava.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
-
orderedListAdd
private void orderedListAdd(OrderedFastHashMap.Position listPosition, int position)
-
orderedListRemove
private void orderedListRemove(int position)
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
-