class CompactHashMap<K,V>
extends java.util.AbstractMap<K,V>
implements java.io.Serializable
containsKey(k)
, put(k, v)
and remove(k)
are all (expected and
amortized) constant time operations. Expected in the hashtable sense (depends on the hash
function doing a good job of distributing the elements to the buckets to a distribution not far
from uniform), and amortized since some operations can trigger a hash table resize.
Unlike java.util.HashMap
, iteration is only proportional to the actual size()
,
which is optimal, and not the size of the internal hashtable, which could be much larger
than size()
. Furthermore, this structure places significantly reduced load on the garbage
collector by only using a constant number of internal objects.
If there are no removals, then iteration order for the entrySet()
, keySet()
, and
values
views is the same as insertion order. Any removal invalidates any ordering
guarantees.
This class should not be assumed to be universally superior to java.util.HashMap
.
Generally speaking, this class reduces object allocation and memory consumption at the price of
moderately increased constant factors of CPU. Only use this class when there is a specific reason
to prioritize memory over CPU.
Modifier and Type | Class and Description |
---|---|
(package private) class |
CompactHashMap.EntrySetView |
private class |
CompactHashMap.Itr<T> |
(package private) class |
CompactHashMap.KeySetView |
(package private) class |
CompactHashMap.MapEntry |
(package private) class |
CompactHashMap.ValuesView |
Modifier and Type | Field and Description |
---|---|
(package private) int[] |
entries
Contains the logical entries, in the range of [0, size()).
|
private java.util.Set<java.util.Map.Entry<K,V>> |
entrySetView |
(package private) static double |
HASH_FLOODING_FPP
Maximum allowed false positive probability of detecting a hash flooding attack given random
input.
|
(package private) java.lang.Object[] |
keys
The keys of the entries in the map, in the range of [0, size()).
|
private java.util.Set<K> |
keySetView |
private static int |
MAX_HASH_BUCKET_LENGTH
Maximum allowed length of a hash table bucket before falling back to a j.u.LinkedHashMap-based
implementation.
|
private int |
metadata
Keeps track of metadata like the number of hash table bits and modifications of this data
structure (to make it possible to throw ConcurrentModificationException in the iterator).
|
private static java.lang.Object |
NOT_FOUND |
private int |
size
The number of elements contained in the set.
|
private java.lang.Object |
table
The hashtable object.
|
(package private) java.lang.Object[] |
values
The values of the entries in the map, in the range of [0, size()).
|
private java.util.Collection<V> |
valuesView |
Constructor and Description |
---|
CompactHashMap()
Constructs a new empty instance of
CompactHashMap . |
CompactHashMap(int expectedSize)
Constructs a new instance of
CompactHashMap with the specified capacity. |
Modifier and Type | Method and Description |
---|---|
(package private) void |
accessEntry(int index)
Mark an access of the specified entry.
|
(package private) int |
adjustAfterRemove(int indexBeforeRemove,
int indexRemoved)
Updates the index an iterator is pointing to after a call to remove: returns the index of the
entry that should be looked at after a removal on indexRemoved, with indexBeforeRemove as the
index that *was* the next entry that would be looked at.
|
(package private) int |
allocArrays()
Handle lazy allocation of arrays.
|
void |
clear() |
boolean |
containsKey(java.lang.Object key) |
boolean |
containsValue(java.lang.Object value) |
(package private) java.util.Map<K,V> |
convertToHashFloodingResistantImplementation() |
static <K,V> CompactHashMap<K,V> |
create()
Creates an empty
CompactHashMap instance. |
(package private) java.util.Set<java.util.Map.Entry<K,V>> |
createEntrySet() |
(package private) java.util.Map<K,V> |
createHashFloodingResistantDelegate(int tableSize) |
(package private) java.util.Set<K> |
createKeySet() |
(package private) java.util.Collection<V> |
createValues() |
static <K,V> CompactHashMap<K,V> |
createWithExpectedSize(int expectedSize)
Creates a
CompactHashMap instance, with a high enough "initial capacity" that it
should hold expectedSize elements without growth. |
(package private) java.util.Map<K,V> |
delegateOrNull() |
java.util.Set<java.util.Map.Entry<K,V>> |
entrySet() |
(package private) java.util.Iterator<java.util.Map.Entry<K,V>> |
entrySetIterator() |
(package private) int |
firstEntryIndex() |
void |
forEach(java.util.function.BiConsumer<? super K,? super V> action) |
V |
get(java.lang.Object key) |
(package private) int |
getSuccessor(int entryIndex) |
private int |
hashTableMask()
Gets the hash table mask using the stored number of hash table bits.
|
(package private) void |
incrementModCount() |
private int |
indexOf(java.lang.Object key) |
(package private) void |
init(int expectedSize)
Pseudoconstructor for serialization support.
|
(package private) void |
insertEntry(int entryIndex,
K key,
V value,
int hash,
int mask)
Creates a fresh entry with the specified object at the specified position in the entry arrays.
|
boolean |
isEmpty() |
java.util.Set<K> |
keySet() |
(package private) java.util.Iterator<K> |
keySetIterator() |
(package private) void |
moveLastEntry(int dstIndex,
int mask)
Moves the last entry in the entry array into
dstIndex , and nulls out its old position. |
(package private) boolean |
needsAllocArrays()
Returns whether arrays need to be allocated.
|
V |
put(K key,
V value) |
private void |
readObject(java.io.ObjectInputStream stream) |
V |
remove(java.lang.Object key) |
private java.lang.Object |
removeHelper(java.lang.Object key) |
void |
replaceAll(java.util.function.BiFunction<? super K,? super V,? extends V> function) |
(package private) void |
resizeEntries(int newCapacity)
Resizes the internal entries array to the specified capacity, which may be greater or less than
the current capacity.
|
private void |
resizeMeMaybe(int newSize)
Resizes the entries storage if necessary.
|
private int |
resizeTable(int mask,
int newCapacity,
int targetHash,
int targetEntryIndex) |
private void |
setHashTableMask(int mask)
Stores the hash table mask as the number of bits needed to represent an index.
|
int |
size() |
void |
trimToSize()
Ensures that this
CompactHashMap has the smallest representation in memory, given its
current size. |
java.util.Collection<V> |
values() |
(package private) java.util.Iterator<V> |
valuesIterator() |
private void |
writeObject(java.io.ObjectOutputStream stream) |
private static final java.lang.Object NOT_FOUND
static final double HASH_FLOODING_FPP
private static final int MAX_HASH_BUCKET_LENGTH
private transient java.lang.Object table
transient int[] entries
hash = aaaaaaaa mask = 0000ffff next = 0000bbbb entry = aaaabbbb
The pointers in [size(), entries.length) are all "null" (UNSET).
transient java.lang.Object[] keys
null
.transient java.lang.Object[] values
null
.private transient int metadata
private transient int size
private transient java.util.Set<K> keySetView
private transient java.util.Collection<V> valuesView
CompactHashMap()
CompactHashMap
.CompactHashMap(int expectedSize)
CompactHashMap
with the specified capacity.expectedSize
- the initial capacity of this CompactHashMap
.public static <K,V> CompactHashMap<K,V> create()
CompactHashMap
instance.public static <K,V> CompactHashMap<K,V> createWithExpectedSize(int expectedSize)
CompactHashMap
instance, with a high enough "initial capacity" that it
should hold expectedSize
elements without growth.expectedSize
- the number of elements you expect to add to the returned setCompactHashMap
with enough capacity to hold expectedSize
elements without resizingjava.lang.IllegalArgumentException
- if expectedSize
is negativevoid init(int expectedSize)
boolean needsAllocArrays()
int allocArrays()
java.util.Map<K,V> createHashFloodingResistantDelegate(int tableSize)
java.util.Map<K,V> convertToHashFloodingResistantImplementation()
private void setHashTableMask(int mask)
private int hashTableMask()
void incrementModCount()
void accessEntry(int index)
CompactLinkedHashMap
for LRU
ordering.void insertEntry(int entryIndex, K key, V value, int hash, int mask)
private void resizeMeMaybe(int newSize)
void resizeEntries(int newCapacity)
private int resizeTable(int mask, int newCapacity, int targetHash, int targetEntryIndex)
private int indexOf(java.lang.Object key)
public boolean containsKey(java.lang.Object key)
public V get(java.lang.Object key)
public V remove(java.lang.Object key)
private java.lang.Object removeHelper(java.lang.Object key)
void moveLastEntry(int dstIndex, int mask)
dstIndex
, and nulls out its old position.int firstEntryIndex()
int getSuccessor(int entryIndex)
int adjustAfterRemove(int indexBeforeRemove, int indexRemoved)
public void replaceAll(java.util.function.BiFunction<? super K,? super V,? extends V> function)
public java.util.Set<K> keySet()
java.util.Set<K> createKeySet()
java.util.Iterator<K> keySetIterator()
public int size()
public boolean isEmpty()
public boolean containsValue(java.lang.Object value)
public java.util.Collection<V> values()
java.util.Collection<V> createValues()
java.util.Iterator<V> valuesIterator()
public void trimToSize()
CompactHashMap
has the smallest representation in memory, given its
current size.public void clear()
private void writeObject(java.io.ObjectOutputStream stream) throws java.io.IOException
java.io.IOException
private void readObject(java.io.ObjectInputStream stream) throws java.io.IOException, java.lang.ClassNotFoundException
java.io.IOException
java.lang.ClassNotFoundException