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
@GwtIncompatible 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) static int
DEFAULT_SIZE
(package private) long[]
entries
Contains the logical entries, in the range of [0, size()).private java.util.Set<java.util.Map.Entry<K,V>>
entrySetView
private static long
HASH_MASK
Bitmask that selects the high 32 bits.(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 float
LOAD_FACTOR
(package private) int
modCount
Keeps track of modifications of this set, to make it possible to throw ConcurrentModificationException in the iterator.private static long
NEXT_MASK
Bitmask that selects the low 32 bits.private int
size
The number of elements contained in the set.private int[]
table
The hashtable.(package private) static int
UNSET
(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) void
allocArrays()
Handle lazy allocation of arrays.void
clear()
boolean
containsKey(java.lang.Object key)
boolean
containsValue(java.lang.Object value)
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.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.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)
private static int
getHash(long entry)
private static int
getNext(long entry)
Returns the index, or UNSET if the pointer is "null"(package private) int
getSuccessor(int entryIndex)
private int
hashTableMask()
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)
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)
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.private static long[]
newEntries(int size)
private static int[]
newTable(int size)
V
put(K key, V value)
private void
readObject(java.io.ObjectInputStream stream)
V
remove(java.lang.Object key)
private V
remove(java.lang.Object key, int hash)
private V
removeEntry(int entryIndex)
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 void
resizeTable(int newCapacity)
int
size()
private static long
swapNext(long entry, int newNext)
Returns a new entry value by changing the "next" index of an existing entryvoid
trimToSize()
Ensures that thisCompactHashMap
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)
-
-
-
Field Detail
-
LOAD_FACTOR
private static final float LOAD_FACTOR
- See Also:
- Constant Field Values
-
NEXT_MASK
private static final long NEXT_MASK
Bitmask that selects the low 32 bits.- See Also:
- Constant Field Values
-
HASH_MASK
private static final long HASH_MASK
Bitmask that selects the high 32 bits.- See Also:
- Constant Field Values
-
DEFAULT_SIZE
static final int DEFAULT_SIZE
- See Also:
- Constant Field Values
-
UNSET
static final int UNSET
- See Also:
- Constant Field Values
-
table
private transient int[] table
The hashtable. Its values are indexes to the keys, values, and entries arrays.Currently, the UNSET value means "null pointer", and any non negative value x is the actual index.
Its size must be a power of two.
-
entries
transient long[] entries
Contains the logical entries, in the range of [0, size()). The high 32 bits of each long is the smeared hash of the element, whereas the low 32 bits is the "next" pointer (pointing to the next entry in the bucket chain). The pointers in [size(), entries.length) are all "null" (UNSET).
-
keys
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
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
.
-
modCount
transient int modCount
Keeps track of modifications of this set, 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.
-
size
private transient int size
The number of elements contained in the set.
-
keySetView
private transient java.util.Set<K> keySetView
-
valuesView
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
void allocArrays()
Handle lazy allocation of arrays.
-
newTable
private static int[] newTable(int size)
-
newEntries
private static long[] newEntries(int size)
-
hashTableMask
private int hashTableMask()
-
getHash
private static int getHash(long entry)
-
getNext
private static int getNext(long entry)
Returns the index, or UNSET if the pointer is "null"
-
swapNext
private static long swapNext(long entry, int newNext)
Returns a new entry value by changing the "next" index of an existing entry
-
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)
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 void resizeTable(int newCapacity)
-
indexOf
private int indexOf(java.lang.Object key)
-
containsKey
public boolean containsKey(java.lang.Object key)
-
get
public V get(java.lang.Object key)
-
remove
public V remove(java.lang.Object key)
-
remove
private V remove(java.lang.Object key, int hash)
-
removeEntry
private V removeEntry(int entryIndex)
-
moveLastEntry
void moveLastEntry(int dstIndex)
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(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
-
-