Class CompactHashMap<K,V>
- java.lang.Object
-
- java.util.AbstractMap<K,V>
-
- com.google.common.collect.CompactHashMap<K,V>
-
- All Implemented Interfaces:
java.io.Serializable
,java.util.Map<K,V>
- Direct Known Subclasses:
CompactLinkedHashMap
class CompactHashMap<K,V> extends java.util.AbstractMap<K,V> implements java.io.Serializable
CompactHashMap is an implementation of a Map. All optional operations (put and remove) are supported. Null keys and values are supported.containsKey(k)
,put(k, v)
andremove(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 actualsize()
, which is optimal, and not the size of the internal hashtable, which could be much larger thansize()
. 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()
, andvalues
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.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class 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
-
Field Summary
Fields Modifier and Type Field 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 Summary
Constructors Constructor Description CompactHashMap()
Constructs a new empty instance ofCompactHashMap
.CompactHashMap(int expectedSize)
Constructs a new instance ofCompactHashMap
with the specified capacity.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method 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 emptyCompactHashMap
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 aCompactHashMap
instance, with a high enough "initial capacity" that it should holdexpectedSize
elements without growth.(package private) java.util.Map<K,V>
delegateOrNull()
private int
entry(int i)
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()
private K
key(int i)
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 intodstIndex
, 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)
private int[]
requireEntries()
private java.lang.Object[]
requireKeys()
private java.lang.Object
requireTable()
private java.lang.Object[]
requireValues()
(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 oldMask, int newCapacity, int targetHash, int targetEntryIndex)
private void
setEntry(int i, int value)
private void
setHashTableMask(int mask)
Stores the hash table mask as the number of bits needed to represent an index.private void
setKey(int i, K key)
private void
setValue(int i, V value)
int
size()
void
trimToSize()
Ensures that thisCompactHashMap
has the smallest representation in memory, given its current size.private V
value(int i)
java.util.Collection<V>
values()
(package private) java.util.Iterator<V>
valuesIterator()
private void
writeObject(java.io.ObjectOutputStream stream)
-
-
-
Field Detail
-
NOT_FOUND
private static final java.lang.Object NOT_FOUND
-
HASH_FLOODING_FPP
static final double HASH_FLOODING_FPP
Maximum allowed false positive probability of detecting a hash flooding attack given random input.- See Also:
- Constant Field Values
-
MAX_HASH_BUCKET_LENGTH
private static final int MAX_HASH_BUCKET_LENGTH
Maximum allowed length of a hash table bucket before falling back to a j.u.LinkedHashMap-based implementation. Experimentally determined.- See Also:
- Constant Field Values
-
table
@CheckForNull private transient java.lang.Object table
The hashtable object. This can be either:- a byte[], short[], or int[], with size a power of two, created by
CompactHashing.createTable, whose values are either
- UNSET, meaning "null pointer"
- one plus an index into the keys, values, and entries arrays
- another java.util.Map delegate implementation. In most modern JDKs, normal java.util hash collections intelligently fall back to a binary search tree if hash table collisions are detected. Rather than going to all the trouble of reimplementing this ourselves, we simply switch over to use the JDK implementation wholesale if probable hash flooding is detected, sacrificing the compactness guarantee in very rare cases in exchange for much more reliable worst-case behavior.
- null, if no entries have yet been added to the map
- a byte[], short[], or int[], with size a power of two, created by
CompactHashing.createTable, whose values are either
-
entries
@CheckForNull transient int[] entries
Contains the logical entries, in the range of [0, size()). The high bits of each int are the part of the smeared hash of the key not covered by the hashtable mask, whereas the low bits are the "next" pointer (pointing to the next entry in the bucket chain), which will always be less than or equal to the hashtable mask.hash = aaaaaaaa mask = 00000fff next = 00000bbb entry = aaaaabbb
The pointers in [size(), entries.length) are all "null" (UNSET).
-
keys
@CheckForNull transient java.lang.Object[] keys
The keys of the entries in the map, in the range of [0, size()). The keys in [size(), keys.length) are allnull
.
-
values
@CheckForNull transient java.lang.Object[] values
The values of the entries in the map, in the range of [0, size()). The values in [size(), values.length) are allnull
.
-
metadata
private transient 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). Note that we choose not to make this volatile, so we do less of a "best effort" to track such errors, for better performance.For a new instance, where the arrays above have not yet been allocated, the value of
metadata
is the size that the arrays should be allocated with. Once the arrays have been allocated, the value ofmetadata
combines the number of bits in the "short hash", in its bottom 5 bits, with a modification count in the remaining bits that is used to detect concurrent modification during iteration.
-
size
private transient int size
The number of elements contained in the set.
-
keySetView
@CheckForNull private transient java.util.Set<K> keySetView
-
valuesView
@CheckForNull private transient java.util.Collection<V> valuesView
-
-
Method Detail
-
create
public static <K,V> CompactHashMap<K,V> create()
Creates an emptyCompactHashMap
instance.
-
createWithExpectedSize
public static <K,V> CompactHashMap<K,V> createWithExpectedSize(int expectedSize)
Creates aCompactHashMap
instance, with a high enough "initial capacity" that it should holdexpectedSize
elements without growth.- Parameters:
expectedSize
- the number of elements you expect to add to the returned set- Returns:
- a new, empty
CompactHashMap
with enough capacity to holdexpectedSize
elements without resizing - Throws:
java.lang.IllegalArgumentException
- ifexpectedSize
is negative
-
init
void init(int expectedSize)
Pseudoconstructor for serialization support.
-
needsAllocArrays
boolean needsAllocArrays()
Returns whether arrays need to be allocated.
-
allocArrays
int allocArrays()
Handle lazy allocation of arrays.
-
createHashFloodingResistantDelegate
java.util.Map<K,V> createHashFloodingResistantDelegate(int tableSize)
-
convertToHashFloodingResistantImplementation
java.util.Map<K,V> convertToHashFloodingResistantImplementation()
-
setHashTableMask
private void setHashTableMask(int mask)
Stores the hash table mask as the number of bits needed to represent an index.
-
hashTableMask
private int hashTableMask()
Gets the hash table mask using the stored number of hash table bits.
-
incrementModCount
void incrementModCount()
-
accessEntry
void accessEntry(int index)
Mark an access of the specified entry. Used only inCompactLinkedHashMap
for LRU ordering.
-
insertEntry
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.
-
resizeMeMaybe
private void resizeMeMaybe(int newSize)
Resizes the entries storage if necessary.
-
resizeEntries
void resizeEntries(int newCapacity)
Resizes the internal entries array to the specified capacity, which may be greater or less than the current capacity.
-
resizeTable
private int resizeTable(int oldMask, int newCapacity, int targetHash, int targetEntryIndex)
-
indexOf
private int indexOf(@CheckForNull java.lang.Object key)
-
containsKey
public boolean containsKey(@CheckForNull java.lang.Object key)
-
get
@CheckForNull public V get(@CheckForNull java.lang.Object key)
-
remove
@CheckForNull public V remove(@CheckForNull java.lang.Object key)
-
removeHelper
private java.lang.Object removeHelper(@CheckForNull java.lang.Object key)
-
moveLastEntry
void moveLastEntry(int dstIndex, int mask)
Moves the last entry in the entry array intodstIndex
, and nulls out its old position.
-
firstEntryIndex
int firstEntryIndex()
-
getSuccessor
int getSuccessor(int entryIndex)
-
adjustAfterRemove
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.
-
replaceAll
public void replaceAll(java.util.function.BiFunction<? super K,? super V,? extends V> function)
-
keySet
public java.util.Set<K> keySet()
-
createKeySet
java.util.Set<K> createKeySet()
-
keySetIterator
java.util.Iterator<K> keySetIterator()
-
size
public int size()
-
isEmpty
public boolean isEmpty()
-
containsValue
public boolean containsValue(@CheckForNull java.lang.Object value)
-
values
public java.util.Collection<V> values()
-
createValues
java.util.Collection<V> createValues()
-
valuesIterator
java.util.Iterator<V> valuesIterator()
-
trimToSize
public void trimToSize()
Ensures that thisCompactHashMap
has the smallest representation in memory, given its current size.
-
clear
public void clear()
-
writeObject
private void writeObject(java.io.ObjectOutputStream stream) throws java.io.IOException
- Throws:
java.io.IOException
-
readObject
private void readObject(java.io.ObjectInputStream stream) throws java.io.IOException, java.lang.ClassNotFoundException
- Throws:
java.io.IOException
java.lang.ClassNotFoundException
-
requireTable
private java.lang.Object requireTable()
-
requireEntries
private int[] requireEntries()
-
requireKeys
private java.lang.Object[] requireKeys()
-
requireValues
private java.lang.Object[] requireValues()
-
key
private K key(int i)
-
value
private V value(int i)
-
entry
private int entry(int i)
-
setKey
private void setKey(int i, K key)
-
setValue
private void setValue(int i, V value)
-
setEntry
private void setEntry(int i, int value)
-
-