Package io.netty.util.collection
Class ShortObjectHashMap<V>
- java.lang.Object
-
- io.netty.util.collection.ShortObjectHashMap<V>
-
- Type Parameters:
V
- The value type stored in the map.
- All Implemented Interfaces:
ShortObjectMap<V>
,java.util.Map<java.lang.Short,V>
public class ShortObjectHashMap<V> extends java.lang.Object implements ShortObjectMap<V>
A hash map implementation ofShortObjectMap
that uses open addressing for keys. To minimize the memory footprint, this class uses open addressing rather than chaining. Collisions are resolved using linear probing. Deletions implement compaction, so cost of remove can approach O(N) for full maps, which makes a small loadFactor recommended.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private class
ShortObjectHashMap.EntrySet
Set implementation for iterating over the entries of the map.private class
ShortObjectHashMap.KeySet
Set implementation for iterating over the keys.(package private) class
ShortObjectHashMap.MapEntry
A single entry in the map.private class
ShortObjectHashMap.MapIterator
Iterator used by theMap
interface.private class
ShortObjectHashMap.PrimitiveIterator
Iterator over primitive entries.-
Nested classes/interfaces inherited from interface java.util.Map
java.util.Map.Entry<K extends java.lang.Object,V extends java.lang.Object>
-
Nested classes/interfaces inherited from interface io.netty.util.collection.ShortObjectMap
ShortObjectMap.PrimitiveEntry<V>
-
-
Field Summary
Fields Modifier and Type Field Description static int
DEFAULT_CAPACITY
Default initial capacity.static float
DEFAULT_LOAD_FACTOR
Default load factor.private java.lang.Iterable<ShortObjectMap.PrimitiveEntry<V>>
entries
private java.util.Set<java.util.Map.Entry<java.lang.Short,V>>
entrySet
private short[]
keys
private java.util.Set<java.lang.Short>
keySet
private float
loadFactor
The load factor for the map.private int
mask
private int
maxSize
The maximum number of elements allowed without allocating more space.private static java.lang.Object
NULL_VALUE
Placeholder for null values, so we can use the actual null to mean available.private int
size
private V[]
values
-
Constructor Summary
Constructors Constructor Description ShortObjectHashMap()
ShortObjectHashMap(int initialCapacity)
ShortObjectHashMap(int initialCapacity, float loadFactor)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private int
calcMaxSize(int capacity)
Calculates the maximum size allowed before rehashing.void
clear()
boolean
containsKey(short key)
Indicates whether or not this map contains a value for the specified key.boolean
containsKey(java.lang.Object key)
boolean
containsValue(java.lang.Object value)
java.lang.Iterable<ShortObjectMap.PrimitiveEntry<V>>
entries()
Gets an iterable to traverse over the primitive entries contained in this map.java.util.Set<java.util.Map.Entry<java.lang.Short,V>>
entrySet()
boolean
equals(java.lang.Object obj)
V
get(short key)
Gets the value in the map with the specified key.V
get(java.lang.Object key)
private void
growSize()
Grows the map size after an insertion.int
hashCode()
private static int
hashCode(short key)
Returns the hash code for the key.private int
hashIndex(short key)
Returns the hashed index for the given key.private int
indexOf(short key)
Locates the index for the given key.boolean
isEmpty()
java.util.Set<java.lang.Short>
keySet()
protected java.lang.String
keyToString(short key)
Helper method called bytoString()
in order to convert a single map key into a string.private short
objectToKey(java.lang.Object key)
private int
probeNext(int index)
Get the next sequential index afterindex
and wraps if necessary.V
put(short key, V value)
Puts the given entry into the map.V
put(java.lang.Short key, V value)
void
putAll(java.util.Map<? extends java.lang.Short,? extends V> sourceMap)
private void
rehash(int newCapacity)
Rehashes the map for the given capacity.V
remove(short key)
Removes the entry with the specified key.V
remove(java.lang.Object key)
private boolean
removeAt(int index)
Removes entry at the given index position.int
size()
private static <T> T
toExternal(T value)
private static <T> T
toInternal(T value)
java.lang.String
toString()
java.util.Collection<V>
values()
-
-
-
Field Detail
-
DEFAULT_CAPACITY
public static final int DEFAULT_CAPACITY
Default initial capacity. Used if not specified in the constructor- See Also:
- Constant Field Values
-
DEFAULT_LOAD_FACTOR
public static final float DEFAULT_LOAD_FACTOR
Default load factor. Used if not specified in the constructor- See Also:
- Constant Field Values
-
NULL_VALUE
private static final java.lang.Object NULL_VALUE
Placeholder for null values, so we can use the actual null to mean available. (Better than using a placeholder for available: less references for GC processing.)
-
maxSize
private int maxSize
The maximum number of elements allowed without allocating more space.
-
loadFactor
private final float loadFactor
The load factor for the map. Used to calculatemaxSize
.
-
keys
private short[] keys
-
values
private V[] values
-
size
private int size
-
mask
private int mask
-
keySet
private final java.util.Set<java.lang.Short> keySet
-
entrySet
private final java.util.Set<java.util.Map.Entry<java.lang.Short,V>> entrySet
-
entries
private final java.lang.Iterable<ShortObjectMap.PrimitiveEntry<V>> entries
-
-
Method Detail
-
toExternal
private static <T> T toExternal(T value)
-
toInternal
private static <T> T toInternal(T value)
-
get
public V get(short key)
Description copied from interface:ShortObjectMap
Gets the value in the map with the specified key.- Specified by:
get
in interfaceShortObjectMap<V>
- Parameters:
key
- the key whose associated value is to be returned.- Returns:
- the value or
null
if the key was not found in the map.
-
put
public V put(short key, V value)
Description copied from interface:ShortObjectMap
Puts the given entry into the map.- Specified by:
put
in interfaceShortObjectMap<V>
- Parameters:
key
- the key of the entry.value
- the value of the entry.- Returns:
- the previous value for this key or
null
if there was no previous mapping.
-
putAll
public void putAll(java.util.Map<? extends java.lang.Short,? extends V> sourceMap)
- Specified by:
putAll
in interfacejava.util.Map<java.lang.Short,V>
-
remove
public V remove(short key)
Description copied from interface:ShortObjectMap
Removes the entry with the specified key.- Specified by:
remove
in interfaceShortObjectMap<V>
- Parameters:
key
- the key for the entry to be removed from this map.- Returns:
- the previous value for the key, or
null
if there was no mapping.
-
size
public int size()
- Specified by:
size
in interfacejava.util.Map<java.lang.Short,V>
-
isEmpty
public boolean isEmpty()
- Specified by:
isEmpty
in interfacejava.util.Map<java.lang.Short,V>
-
clear
public void clear()
- Specified by:
clear
in interfacejava.util.Map<java.lang.Short,V>
-
containsKey
public boolean containsKey(short key)
Description copied from interface:ShortObjectMap
Indicates whether or not this map contains a value for the specified key.- Specified by:
containsKey
in interfaceShortObjectMap<V>
-
containsValue
public boolean containsValue(java.lang.Object value)
- Specified by:
containsValue
in interfacejava.util.Map<java.lang.Short,V>
-
entries
public java.lang.Iterable<ShortObjectMap.PrimitiveEntry<V>> entries()
Description copied from interface:ShortObjectMap
Gets an iterable to traverse over the primitive entries contained in this map. As an optimization, theShortObjectMap.PrimitiveEntry
s returned by theIterator
may change as theIterator
progresses. The caller should not rely onShortObjectMap.PrimitiveEntry
key/value stability.- Specified by:
entries
in interfaceShortObjectMap<V>
-
values
public java.util.Collection<V> values()
- Specified by:
values
in interfacejava.util.Map<java.lang.Short,V>
-
hashCode
public int hashCode()
- Specified by:
hashCode
in interfacejava.util.Map<java.lang.Short,V>
- Overrides:
hashCode
in classjava.lang.Object
-
equals
public boolean equals(java.lang.Object obj)
- Specified by:
equals
in interfacejava.util.Map<java.lang.Short,V>
- Overrides:
equals
in classjava.lang.Object
-
containsKey
public boolean containsKey(java.lang.Object key)
- Specified by:
containsKey
in interfacejava.util.Map<java.lang.Short,V>
-
get
public V get(java.lang.Object key)
- Specified by:
get
in interfacejava.util.Map<java.lang.Short,V>
-
put
public V put(java.lang.Short key, V value)
- Specified by:
put
in interfacejava.util.Map<java.lang.Short,V>
-
remove
public V remove(java.lang.Object key)
- Specified by:
remove
in interfacejava.util.Map<java.lang.Short,V>
-
keySet
public java.util.Set<java.lang.Short> keySet()
- Specified by:
keySet
in interfacejava.util.Map<java.lang.Short,V>
-
entrySet
public java.util.Set<java.util.Map.Entry<java.lang.Short,V>> entrySet()
- Specified by:
entrySet
in interfacejava.util.Map<java.lang.Short,V>
-
objectToKey
private short objectToKey(java.lang.Object key)
-
indexOf
private int indexOf(short key)
Locates the index for the given key. This method probes using double hashing.- Parameters:
key
- the key for an entry in the map.- Returns:
- the index where the key was found, or
-1
if no entry is found for that key.
-
hashIndex
private int hashIndex(short key)
Returns the hashed index for the given key.
-
hashCode
private static int hashCode(short key)
Returns the hash code for the key.
-
probeNext
private int probeNext(int index)
Get the next sequential index afterindex
and wraps if necessary.
-
growSize
private void growSize()
Grows the map size after an insertion. If necessary, performs a rehash of the map.
-
removeAt
private boolean removeAt(int index)
Removes entry at the given index position. Also performs opportunistic, incremental rehashing if necessary to not break conflict chains.- Parameters:
index
- the index position of the element to remove.- Returns:
true
if the next item was moved back.false
otherwise.
-
calcMaxSize
private int calcMaxSize(int capacity)
Calculates the maximum size allowed before rehashing.
-
rehash
private void rehash(int newCapacity)
Rehashes the map for the given capacity.- Parameters:
newCapacity
- the new capacity for the map.
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
keyToString
protected java.lang.String keyToString(short key)
Helper method called bytoString()
in order to convert a single map key into a string. This is protected to allow subclasses to override the appearance of a given key.
-
-