Class CompactLinkedHashMap<K,V>
- All Implemented Interfaces:
Serializable,Map<K,V>
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.
As compared with LinkedHashMap, this structure places significantly reduced
load on the garbage collector by only using a constant number of internal objects.
This class should not be assumed to be universally superior to
java.util.LinkedHashMap. 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/interfaces inherited from class com.google.common.collect.CompactHashMap
CompactHashMap.EntrySetView, CompactHashMap.KeySetView, CompactHashMap.MapEntry, CompactHashMap.ValuesViewNested classes/interfaces inherited from class java.util.AbstractMap
AbstractMap.SimpleEntry<K,V>, AbstractMap.SimpleImmutableEntry<K, V> -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate final booleanprivate static final intprivate intPointer to the first node in the linked list, orENDPOINTif there are no entries.private intPointer to the last node in the linked list, orENDPOINTif there are no entries.(package private) long[]Contains the link pointers corresponding with the entries, in the range of [0, size()).Fields inherited from class com.google.common.collect.CompactHashMap
entries, HASH_FLOODING_FPP, keys, values -
Constructor Summary
ConstructorsConstructorDescriptionCompactLinkedHashMap(int expectedSize) CompactLinkedHashMap(int expectedSize, boolean accessOrder) -
Method Summary
Modifier and TypeMethodDescription(package private) voidaccessEntry(int index) Mark an access of the specified entry.(package private) intadjustAfterRemove(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) intHandle lazy allocation of arrays.voidclear()static <K,V> CompactLinkedHashMap <K, V> create()Creates an emptyCompactLinkedHashMapinstance.createHashFloodingResistantDelegate(int tableSize) (package private) Collection<V> static <K,V> CompactLinkedHashMap <K, V> createWithExpectedSize(int expectedSize) Creates aCompactLinkedHashMapinstance, with a high enough "initial capacity" that it should holdexpectedSizeelements without rebuilding internal data structures.(package private) intprivate intgetPredecessor(int entry) (package private) intgetSuccessor(int entry) (package private) voidinit(int expectedSize) Pseudoconstructor for serialization support.(package private) voidinsertEntry(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.private longlink(int i) (package private) voidmoveLastEntry(int dstIndex, int mask) Moves the last entry in the entry array intodstIndex, and nulls out its old position.private long[](package private) voidresizeEntries(int newCapacity) Resizes the internal entries array to the specified capacity, which may be greater or less than the current capacity.private voidsetLink(int i, long value) private voidsetPredecessor(int entry, int pred) private voidsetSucceeds(int pred, int succ) private voidsetSuccessor(int entry, int succ) Methods inherited from class com.google.common.collect.CompactHashMap
containsKey, containsValue, delegateOrNull, entrySet, entrySetIterator, forEach, get, incrementModCount, isEmpty, keySet, keySetIterator, needsAllocArrays, put, remove, replaceAll, size, trimToSize, values, valuesIteratorMethods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, waitMethods inherited from interface java.util.Map
compute, computeIfAbsent, computeIfPresent, getOrDefault, merge, putIfAbsent, remove, replace, replace
-
Field Details
-
ENDPOINT
private static final int ENDPOINT- See Also:
-
links
@CheckForNull transient long[] linksContains the link pointers corresponding with the entries, in the range of [0, size()). The high 32 bits of each long is the "prev" pointer, whereas the low 32 bits is the "succ" pointer (pointing to the next entry in the linked list). The pointers in [size(), entries.length) are all "null" (UNSET).A node with "prev" pointer equal to
ENDPOINTis the first node in the linked list, and a node with "next" pointer equal toENDPOINTis the last node. -
firstEntry
private transient int firstEntryPointer to the first node in the linked list, orENDPOINTif there are no entries. -
lastEntry
private transient int lastEntryPointer to the last node in the linked list, orENDPOINTif there are no entries. -
accessOrder
private final boolean accessOrder
-
-
Constructor Details
-
CompactLinkedHashMap
CompactLinkedHashMap() -
CompactLinkedHashMap
CompactLinkedHashMap(int expectedSize) -
CompactLinkedHashMap
CompactLinkedHashMap(int expectedSize, boolean accessOrder)
-
-
Method Details
-
create
Creates an emptyCompactLinkedHashMapinstance. -
createWithExpectedSize
Creates aCompactLinkedHashMapinstance, with a high enough "initial capacity" that it should holdexpectedSizeelements without rebuilding internal data structures.- Parameters:
expectedSize- the number of elements you expect to add to the returned set- Returns:
- a new, empty
CompactLinkedHashMapwith enough capacity to holdexpectedSizeelements without resizing - Throws:
IllegalArgumentException- ifexpectedSizeis negative
-
init
void init(int expectedSize) Description copied from class:CompactHashMapPseudoconstructor for serialization support.- Overrides:
initin classCompactHashMap<K,V>
-
allocArrays
int allocArrays()Description copied from class:CompactHashMapHandle lazy allocation of arrays.- Overrides:
allocArraysin classCompactHashMap<K,V>
-
createHashFloodingResistantDelegate
- Overrides:
createHashFloodingResistantDelegatein classCompactHashMap<K,V>
-
convertToHashFloodingResistantImplementation
- Overrides:
convertToHashFloodingResistantImplementationin classCompactHashMap<K,V>
-
getPredecessor
private int getPredecessor(int entry) -
getSuccessor
int getSuccessor(int entry) - Overrides:
getSuccessorin classCompactHashMap<K,V>
-
setSuccessor
private void setSuccessor(int entry, int succ) -
setPredecessor
private void setPredecessor(int entry, int pred) -
setSucceeds
private void setSucceeds(int pred, int succ) -
insertEntry
Description copied from class:CompactHashMapCreates a fresh entry with the specified object at the specified position in the entry arrays.- Overrides:
insertEntryin classCompactHashMap<K,V>
-
accessEntry
void accessEntry(int index) Description copied from class:CompactHashMapMark an access of the specified entry. Used only inCompactLinkedHashMapfor LRU ordering.- Overrides:
accessEntryin classCompactHashMap<K,V>
-
moveLastEntry
void moveLastEntry(int dstIndex, int mask) Description copied from class:CompactHashMapMoves the last entry in the entry array intodstIndex, and nulls out its old position.- Overrides:
moveLastEntryin classCompactHashMap<K,V>
-
resizeEntries
void resizeEntries(int newCapacity) Description copied from class:CompactHashMapResizes the internal entries array to the specified capacity, which may be greater or less than the current capacity.- Overrides:
resizeEntriesin classCompactHashMap<K,V>
-
firstEntryIndex
int firstEntryIndex()- Overrides:
firstEntryIndexin classCompactHashMap<K,V>
-
adjustAfterRemove
int adjustAfterRemove(int indexBeforeRemove, int indexRemoved) Description copied from class:CompactHashMapUpdates 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.- Overrides:
adjustAfterRemovein classCompactHashMap<K,V>
-
createEntrySet
- Overrides:
createEntrySetin classCompactHashMap<K,V>
-
createKeySet
- Overrides:
createKeySetin classCompactHashMap<K,V>
-
createValues
Collection<V> createValues()- Overrides:
createValuesin classCompactHashMap<K,V>
-
clear
public void clear() -
requireLinks
private long[] requireLinks() -
link
private long link(int i) -
setLink
private void setLink(int i, long value)
-