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()).
|
entries, HASH_FLOODING_FPP, keys, 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) int |
allocArrays()
Handle lazy allocation of arrays.
|
void |
clear() |
(package private) java.util.Map<K,V> |
convertToHashFloodingResistantImplementation() |
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.Map<K,V> |
createHashFloodingResistantDelegate(int tableSize) |
(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,
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 into
dstIndex, and nulls out its old position. |
private long[] |
requireLinks() |
(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) |
containsKey, containsValue, delegateOrNull, entrySet, entrySetIterator, forEach, get, incrementModCount, isEmpty, keySet, keySetIterator, needsAllocArrays, put, remove, replaceAll, size, trimToSize, values, valuesIteratorprivate static final int ENDPOINT
@CheckForNull 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)
CompactHashMapinit in class CompactHashMap<K,V>int allocArrays()
CompactHashMapallocArrays in class CompactHashMap<K,V>java.util.Map<K,V> createHashFloodingResistantDelegate(int tableSize)
createHashFloodingResistantDelegate in class CompactHashMap<K,V>java.util.Map<K,V> convertToHashFloodingResistantImplementation()
convertToHashFloodingResistantImplementation 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,
int mask)
CompactHashMapinsertEntry in class CompactHashMap<K,V>void accessEntry(int index)
CompactHashMapCompactLinkedHashMap for LRU
ordering.accessEntry in class CompactHashMap<K,V>void moveLastEntry(int dstIndex,
int mask)
CompactHashMapdstIndex, and nulls out its old position.moveLastEntry in class CompactHashMap<K,V>void resizeEntries(int newCapacity)
CompactHashMapresizeEntries in class CompactHashMap<K,V>int firstEntryIndex()
firstEntryIndex in class CompactHashMap<K,V>int adjustAfterRemove(int indexBeforeRemove,
int indexRemoved)
CompactHashMapadjustAfterRemove 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>public void clear()
private long[] requireLinks()
private long link(int i)
private void setLink(int i,
long value)