@GwtIncompatible class CompactLinkedHashMap<K,V> extends CompactHashMap<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.
CompactHashMap.EntrySetView, CompactHashMap.KeySetView, CompactHashMap.MapEntry, CompactHashMap.ValuesView
Modifier and Type | Field and Description |
---|---|
private boolean |
accessOrder |
private static int |
ENDPOINT |
private int |
firstEntry
Pointer to the first node in the linked list, or
ENDPOINT if there are no entries. |
private int |
lastEntry
Pointer to the last node in the linked list, or
ENDPOINT if there are no entries. |
(package private) long[] |
links
Contains the link pointers corresponding with the entries, in the range of [0, size()).
|
DEFAULT_SIZE, entries, keys, modCount, UNSET, values
Constructor and Description |
---|
CompactLinkedHashMap() |
CompactLinkedHashMap(int expectedSize) |
CompactLinkedHashMap(int expectedSize,
boolean accessOrder) |
Modifier and Type | Method and 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 empty
CompactLinkedHashMap 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 a
CompactLinkedHashMap instance, with a high enough "initial capacity" that it
should hold expectedSize 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 into
dstIndex , 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) |
containsKey, containsValue, entrySet, entrySetIterator, forEach, get, isEmpty, keySet, keySetIterator, needsAllocArrays, put, remove, replaceAll, size, trimToSize, values, valuesIterator
private static final int ENDPOINT
transient long[] links
A node with "prev" pointer equal to ENDPOINT
is the first node in the linked list,
and a node with "next" pointer equal to ENDPOINT
is the last node.
private transient int firstEntry
ENDPOINT
if there are no entries.private transient int lastEntry
ENDPOINT
if there are no entries.private final boolean accessOrder
CompactLinkedHashMap()
CompactLinkedHashMap(int expectedSize)
CompactLinkedHashMap(int expectedSize, boolean accessOrder)
public static <K,V> CompactLinkedHashMap<K,V> create()
CompactLinkedHashMap
instance.public static <K,V> CompactLinkedHashMap<K,V> createWithExpectedSize(int expectedSize)
CompactLinkedHashMap
instance, with a high enough "initial capacity" that it
should hold expectedSize
elements without rebuilding internal data structures.expectedSize
- the number of elements you expect to add to the returned setCompactLinkedHashMap
with enough capacity to hold expectedSize
elements without resizingjava.lang.IllegalArgumentException
- if expectedSize
is negativevoid init(int expectedSize)
CompactHashMap
init
in class CompactHashMap<K,V>
void allocArrays()
CompactHashMap
allocArrays
in class CompactHashMap<K,V>
private int getPredecessor(int entry)
int getSuccessor(int entry)
getSuccessor
in class CompactHashMap<K,V>
private void setSuccessor(int entry, int succ)
private void setPredecessor(int entry, int pred)
private void setSucceeds(int pred, int succ)
void insertEntry(int entryIndex, K key, V value, int hash)
CompactHashMap
insertEntry
in class CompactHashMap<K,V>
void accessEntry(int index)
CompactHashMap
CompactLinkedHashMap
for LRU
ordering.accessEntry
in class CompactHashMap<K,V>
void moveLastEntry(int dstIndex)
CompactHashMap
dstIndex
, and nulls out its old position.moveLastEntry
in class CompactHashMap<K,V>
void resizeEntries(int newCapacity)
CompactHashMap
resizeEntries
in class CompactHashMap<K,V>
int firstEntryIndex()
firstEntryIndex
in class CompactHashMap<K,V>
int adjustAfterRemove(int indexBeforeRemove, int indexRemoved)
CompactHashMap
adjustAfterRemove
in class CompactHashMap<K,V>
java.util.Set<java.util.Map.Entry<K,V>> createEntrySet()
createEntrySet
in class CompactHashMap<K,V>
java.util.Set<K> createKeySet()
createKeySet
in class CompactHashMap<K,V>
java.util.Collection<V> createValues()
createValues
in class CompactHashMap<K,V>