Class CompactLinkedHashMap<K,V>
- java.lang.Object
-
- java.util.AbstractMap<K,V>
-
- com.google.common.collect.CompactHashMap<K,V>
-
- com.google.common.collect.CompactLinkedHashMap<K,V>
-
- All Implemented Interfaces:
java.io.Serializable
,java.util.Map<K,V>
@GwtIncompatible class CompactLinkedHashMap<K,V> extends CompactHashMap<K,V>
CompactLinkedHashMap is an implementation of a Map with insertion or LRU iteration order, maintained with a doubly linked list through the entries. 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.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
-
-
Field Summary
Fields Modifier and Type Field Description private boolean
accessOrder
private static int
ENDPOINT
private int
firstEntry
Pointer to the first node in the linked list, orENDPOINT
if there are no entries.private int
lastEntry
Pointer to the last node in the linked list, orENDPOINT
if there are no entries.(package private) long[]
links
Contains the link pointers corresponding with the entries, in the range of [0, size()).-
Fields inherited from class com.google.common.collect.CompactHashMap
DEFAULT_SIZE, entries, keys, modCount, UNSET, values
-
-
Constructor Summary
Constructors Constructor Description CompactLinkedHashMap()
CompactLinkedHashMap(int expectedSize)
CompactLinkedHashMap(int expectedSize, boolean accessOrder)
-
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()
static <K,V>
CompactLinkedHashMap<K,V>create()
Creates an emptyCompactLinkedHashMap
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>
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
firstEntryIndex()
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)
Creates a fresh entry with the specified object at the specified position in the entry arrays.(package private) void
moveLastEntry(int dstIndex)
Moves the last entry in the entry array intodstIndex
, and nulls out its old position.(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
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, entrySet, entrySetIterator, forEach, get, isEmpty, keySet, keySetIterator, needsAllocArrays, put, remove, replaceAll, size, trimToSize, values, valuesIterator
-
-
-
-
Field Detail
-
ENDPOINT
private static final int ENDPOINT
- See Also:
- Constant Field Values
-
links
transient long[] links
Contains 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 firstEntry
Pointer to the first node in the linked list, orENDPOINT
if there are no entries.
-
lastEntry
private transient int lastEntry
Pointer to the last node in the linked list, orENDPOINT
if there are no entries.
-
accessOrder
private final boolean accessOrder
-
-
Method Detail
-
create
public static <K,V> CompactLinkedHashMap<K,V> create()
Creates an emptyCompactLinkedHashMap
instance.
-
createWithExpectedSize
public 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.- 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:
java.lang.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
void allocArrays()
Description copied from class:CompactHashMap
Handle lazy allocation of arrays.- Overrides:
allocArrays
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
void insertEntry(int entryIndex, K key, V value, int hash)
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)
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
java.util.Set<java.util.Map.Entry<K,V>> createEntrySet()
- Overrides:
createEntrySet
in classCompactHashMap<K,V>
-
createKeySet
java.util.Set<K> createKeySet()
- Overrides:
createKeySet
in classCompactHashMap<K,V>
-
createValues
java.util.Collection<V> createValues()
- Overrides:
createValues
in classCompactHashMap<K,V>
-
-