Package io.netty.util.collection
Class ByteObjectHashMap<V>
java.lang.Object
io.netty.util.collection.ByteObjectHashMap<V>
- Type Parameters:
V
- The value type stored in the map.
- All Implemented Interfaces:
ByteObjectMap<V>
,Map<Byte,
V>
A hash map implementation of
ByteObjectMap
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 ClassesModifier and TypeClassDescriptionprivate final class
Set implementation for iterating over the entries of the map.private final class
Set implementation for iterating over the keys.(package private) final class
A single entry in the map.private final class
Iterator used by theMap
interface.private final class
Iterator over primitive entries.Nested classes/interfaces inherited from interface io.netty.util.collection.ByteObjectMap
ByteObjectMap.PrimitiveEntry<V>
-
Field Summary
FieldsModifier and TypeFieldDescriptionstatic final int
Default initial capacity.static final float
Default load factor.private final Iterable
<ByteObjectMap.PrimitiveEntry<V>> private byte[]
private final float
The load factor for the map.private int
private int
The maximum number of elements allowed without allocating more space.private static final Object
Placeholder for null values, so we can use the actual null to mean available.private int
private V[]
-
Constructor Summary
ConstructorsConstructorDescriptionByteObjectHashMap
(int initialCapacity) ByteObjectHashMap
(int initialCapacity, float loadFactor) -
Method Summary
Modifier and TypeMethodDescriptionprivate int
calcMaxSize
(int capacity) Calculates the maximum size allowed before rehashing.void
clear()
boolean
containsKey
(byte key) Indicates whether or not this map contains a value for the specified key.boolean
containsKey
(Object key) boolean
containsValue
(Object value) entries()
Gets an iterable to traverse over the primitive entries contained in this map.entrySet()
boolean
get
(byte key) Gets the value in the map with the specified key.private void
growSize()
Grows the map size after an insertion.int
hashCode()
private static int
hashCode
(byte key) Returns the hash code for the key.private int
hashIndex
(byte key) Returns the hashed index for the given key.private int
indexOf
(byte key) Locates the index for the given key.boolean
isEmpty()
keySet()
protected String
keyToString
(byte key) Helper method called bytoString()
in order to convert a single map key into a string.private byte
objectToKey
(Object key) private int
probeNext
(int index) Get the next sequential index afterindex
and wraps if necessary.Puts the given entry into the map.void
private void
rehash
(int newCapacity) Rehashes the map for the given capacity.remove
(byte key) Removes the entry with the specified 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) toString()
values()
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
Methods inherited from interface java.util.Map
compute, computeIfAbsent, computeIfPresent, forEach, getOrDefault, merge, putIfAbsent, remove, replace, replace, replaceAll
-
Field Details
-
DEFAULT_CAPACITY
public static final int DEFAULT_CAPACITYDefault initial capacity. Used if not specified in the constructor- See Also:
-
DEFAULT_LOAD_FACTOR
public static final float DEFAULT_LOAD_FACTORDefault load factor. Used if not specified in the constructor- See Also:
-
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 maxSizeThe maximum number of elements allowed without allocating more space. -
loadFactor
private final float loadFactorThe load factor for the map. Used to calculatemaxSize
. -
keys
private byte[] keys -
values
-
size
private int size -
mask
private int mask -
keySet
-
entrySet
-
entries
-
-
Constructor Details
-
ByteObjectHashMap
public ByteObjectHashMap() -
ByteObjectHashMap
public ByteObjectHashMap(int initialCapacity) -
ByteObjectHashMap
public ByteObjectHashMap(int initialCapacity, float loadFactor)
-
-
Method Details
-
toExternal
private static <T> T toExternal(T value) -
toInternal
private static <T> T toInternal(T value) -
get
Description copied from interface:ByteObjectMap
Gets the value in the map with the specified key.- Specified by:
get
in interfaceByteObjectMap<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
Description copied from interface:ByteObjectMap
Puts the given entry into the map.- Specified by:
put
in interfaceByteObjectMap<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
-
remove
Description copied from interface:ByteObjectMap
Removes the entry with the specified key.- Specified by:
remove
in interfaceByteObjectMap<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() -
isEmpty
public boolean isEmpty() -
clear
public void clear() -
containsKey
public boolean containsKey(byte key) Description copied from interface:ByteObjectMap
Indicates whether or not this map contains a value for the specified key.- Specified by:
containsKey
in interfaceByteObjectMap<V>
-
containsValue
- Specified by:
containsValue
in interfaceMap<Byte,
V>
-
entries
Description copied from interface:ByteObjectMap
Gets an iterable to traverse over the primitive entries contained in this map. As an optimization, theByteObjectMap.PrimitiveEntry
s returned by theinvalid reference
Iterator
invalid reference
Iterator
ByteObjectMap.PrimitiveEntry
key/value stability.- Specified by:
entries
in interfaceByteObjectMap<V>
-
values
-
hashCode
public int hashCode() -
equals
-
containsKey
- Specified by:
containsKey
in interfaceMap<Byte,
V>
-
get
-
put
-
remove
-
keySet
-
entrySet
-
objectToKey
-
indexOf
private int indexOf(byte 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(byte key) Returns the hashed index for the given key. -
hashCode
private static int hashCode(byte 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
-
keyToString
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.
-