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.ValuesView
Nested classes/interfaces inherited from class java.util.AbstractMap
AbstractMap.SimpleEntry<K,
V>, AbstractMap.SimpleImmutableEntry<K, V> -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate final boolean
private static final int
private int
Pointer to the first node in the linked list, orENDPOINT
if there are no entries.private int
Pointer to the last node in the linked list, orENDPOINT
if 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) 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
Handle lazy allocation of arrays.void
clear()
static <K,
V> CompactLinkedHashMap <K, V> create()
Creates an emptyCompactLinkedHashMap
instance.createHashFloodingResistantDelegate
(int tableSize) (package private) Collection
<V> static <K,
V> CompactLinkedHashMap <K, V> createWithExpectedSize
(int expectedSize) Creates aCompactLinkedHashMap
instance, with a high enough "initial capacity" that it should holdexpectedSize
elements without rebuilding internal data structures.(package private) int
private int
getPredecessor
(int entry) (package private) int
getSuccessor
(int entry) (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.private long
link
(int i) (package private) void
moveLastEntry
(int dstIndex, int mask) Moves the last entry in the entry array intodstIndex
, and nulls out its old position.private long[]
(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
setLink
(int i, long value) private void
setPredecessor
(int entry, int pred) private void
setSucceeds
(int pred, int succ) private void
setSuccessor
(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, valuesIterator
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
Methods 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
ENDPOINT
is the first node in the linked list, and a node with "next" pointer equal toENDPOINT
is the last node. -
firstEntry
private transient int firstEntryPointer to the first node in the linked list, orENDPOINT
if there are no entries. -
lastEntry
private transient int lastEntryPointer to the last node in the linked list, orENDPOINT
if 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 emptyCompactLinkedHashMap
instance. -
createWithExpectedSize
Creates aCompactLinkedHashMap
instance, with a high enough "initial capacity" that it should holdexpectedSize
elements without rebuilding internal data structures.- Parameters:
expectedSize
- the number of elements you expect to add to the returned set- Returns:
- a new, empty
CompactLinkedHashMap
with enough capacity to holdexpectedSize
elements without resizing - Throws:
IllegalArgumentException
- ifexpectedSize
is negative
-
init
void init(int expectedSize) Description copied from class:CompactHashMap
Pseudoconstructor for serialization support.- Overrides:
init
in classCompactHashMap<K,
V>
-
allocArrays
int allocArrays()Description copied from class:CompactHashMap
Handle lazy allocation of arrays.- Overrides:
allocArrays
in classCompactHashMap<K,
V>
-
createHashFloodingResistantDelegate
- Overrides:
createHashFloodingResistantDelegate
in classCompactHashMap<K,
V>
-
convertToHashFloodingResistantImplementation
- Overrides:
convertToHashFloodingResistantImplementation
in classCompactHashMap<K,
V>
-
getPredecessor
private int getPredecessor(int entry) -
getSuccessor
int getSuccessor(int entry) - Overrides:
getSuccessor
in 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:CompactHashMap
Creates a fresh entry with the specified object at the specified position in the entry arrays.- Overrides:
insertEntry
in classCompactHashMap<K,
V>
-
accessEntry
void accessEntry(int index) Description copied from class:CompactHashMap
Mark an access of the specified entry. Used only inCompactLinkedHashMap
for LRU ordering.- Overrides:
accessEntry
in classCompactHashMap<K,
V>
-
moveLastEntry
void moveLastEntry(int dstIndex, int mask) Description copied from class:CompactHashMap
Moves the last entry in the entry array intodstIndex
, and nulls out its old position.- Overrides:
moveLastEntry
in classCompactHashMap<K,
V>
-
resizeEntries
void resizeEntries(int newCapacity) Description copied from class:CompactHashMap
Resizes the internal entries array to the specified capacity, which may be greater or less than the current capacity.- Overrides:
resizeEntries
in classCompactHashMap<K,
V>
-
firstEntryIndex
int firstEntryIndex()- Overrides:
firstEntryIndex
in classCompactHashMap<K,
V>
-
adjustAfterRemove
int adjustAfterRemove(int indexBeforeRemove, int indexRemoved) Description copied from class:CompactHashMap
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.- Overrides:
adjustAfterRemove
in classCompactHashMap<K,
V>
-
createEntrySet
- Overrides:
createEntrySet
in classCompactHashMap<K,
V>
-
createKeySet
- Overrides:
createKeySet
in classCompactHashMap<K,
V>
-
createValues
Collection<V> createValues()- Overrides:
createValues
in 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)
-