Guava: Google Core Libraries for Java 32.1.2-jre · com.google.common.collect.CompactLinkedHashMap

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) 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 java.util.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.

Field Summary

Modifier and Type	Field and Description
private final boolean	accessOrder
private static final int	ENDPOINT
private transient int	firstEntry Pointer to the first node in the linked list, or `ENDPOINT` if there are no entries.
private transient int	lastEntry Pointer to the last node in the linked list, or `ENDPOINT` if there are no entries.
pack-priv transient long[]	links Contains the link pointers corresponding with the entries, in the range of [0, size()).

Inherited from com.google.common.collect.CompactHashMap:: entries HASH_FLOODING_FPP keys values

Constructor Summary

Access	Constructor and Description
pack-priv	CompactLinkedHashMap()
pack-priv	CompactLinkedHashMap(int expectedSize)
pack-priv	CompactLinkedHashMap(int expectedSize, boolean accessOrder)

Method Summary

Modifier and Type	Method and Description
pack-priv void	accessEntry(int index) Overrides com.google.common.collect.CompactHashMap.accessEntry. Mark an access of the specified entry.
pack-priv int	adjustAfterRemove(int indexBeforeRemove, int indexRemoved) Overrides com.google.common.collect.CompactHashMap.adjustAfterRemove. 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.
pack-priv int	allocArrays() Overrides com.google.common.collect.CompactHashMap.allocArrays. Handle lazy allocation of arrays.
public void	clear() Overrides com.google.common.collect.CompactHashMap.clear. Implements java.util.Map.clear. Removes all of the mappings from this map (optional operation).
pack-priv Map<K, V>	convertToHashFloodingResistantImplementation() Overrides com.google.common.collect.CompactHashMap.convertToHashFloodingResistantImplementation.
public static <K extends @Nullable Object, V extends @Nullable Object> CompactLinkedHashMap<K, V>	create() Hides com.google.common.collect.CompactHashMap.create. Creates an empty `CompactLinkedHashMap` instance.
pack-priv Set<Map.Entry<K, V>>	createEntrySet() Overrides com.google.common.collect.CompactHashMap.createEntrySet.
pack-priv Map<K, V>	createHashFloodingResistantDelegate(int tableSize) Overrides com.google.common.collect.CompactHashMap.createHashFloodingResistantDelegate.
pack-priv Set<K>	createKeySet() Overrides com.google.common.collect.CompactHashMap.createKeySet.
pack-priv Collection<V>	createValues() Overrides com.google.common.collect.CompactHashMap.createValues.
public static <K extends @Nullable Object, V extends @Nullable Object> CompactLinkedHashMap<K, V>	Returns: a new, empty `CompactLinkedHashMap` with enough capacity to hold `expectedSize` elements without resizing createWithExpectedSize(int the number of elements you expect to add to the returned set expectedSize) Hides com.google.common.collect.CompactHashMap.createWithExpectedSize. Creates a `CompactLinkedHashMap` instance, with a high enough "initial capacity" that it should hold `expectedSize` elements without rebuilding internal data structures.
pack-priv int	firstEntryIndex() Overrides com.google.common.collect.CompactHashMap.firstEntryIndex.
private int	getPredecessor(int entry)
pack-priv int	getSuccessor(int entry) Overrides com.google.common.collect.CompactHashMap.getSuccessor.
pack-priv void	init(int expectedSize) Overrides com.google.common.collect.CompactHashMap.init. Pseudoconstructor for serialization support.
pack-priv void	insertEntry(int entryIndex, K key, V value, int hash, int mask) Overrides com.google.common.collect.CompactHashMap.insertEntry. Creates a fresh entry with the specified object at the specified position in the entry arrays.
private long	link(int i)
pack-priv void	moveLastEntry(int dstIndex, int mask) Overrides com.google.common.collect.CompactHashMap.moveLastEntry. Moves the last entry in the entry array into `dstIndex`, and nulls out its old position.
private long[]	requireLinks()
pack-priv void	resizeEntries(int newCapacity) Overrides com.google.common.collect.CompactHashMap.resizeEntries. 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)

Field Detail

accessOrder	back to summary
private final boolean accessOrder

ENDPOINT	back to summary
private static final int ENDPOINT

firstEntry	back to summary
private transient int firstEntry Pointer to the first node in the linked list, or `ENDPOINT` if there are no entries.

lastEntry	back to summary
private transient int lastEntry Pointer to the last node in the linked list, or `ENDPOINT` if there are no entries.

links back to summary

links	back to summary
pack-priv 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 to `ENDPOINT` is the last node. Annotations @CheckForNull @VisibleForTesting

pack-priv 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 to ENDPOINT is the last node.

Annotations

@CheckForNull
@VisibleForTesting

Constructor Detail

CompactLinkedHashMap	back to summary
pack-priv CompactLinkedHashMap()

CompactLinkedHashMap	back to summary
pack-priv CompactLinkedHashMap(int expectedSize)

CompactLinkedHashMap	back to summary
pack-priv CompactLinkedHashMap(int expectedSize, boolean accessOrder)

Method Detail

accessEntry back to summary

accessEntry	back to summary
pack-priv void accessEntry(int index) Overrides com.google.common.collect.CompactHashMap.accessEntry. Doc from com.google.common.collect.CompactHashMap.accessEntry. Mark an access of the specified entry. Used only in `CompactLinkedHashMap` for LRU ordering. Annotations @Override

pack-priv void accessEntry(int index)

Overrides com.google.common.collect.CompactHashMap.accessEntry.

Doc from com.google.common.collect.CompactHashMap.accessEntry.

Mark an access of the specified entry. Used only in CompactLinkedHashMap for LRU ordering.

Annotations

@Override

adjustAfterRemove	back to summary
pack-priv int adjustAfterRemove(int indexBeforeRemove, int indexRemoved) Overrides com.google.common.collect.CompactHashMap.adjustAfterRemove. Doc from com.google.common.collect.CompactHashMap.adjustAfterRemove. 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. Annotations @Override

adjustAfterRemove

back to summary

pack-priv int adjustAfterRemove(int indexBeforeRemove, int indexRemoved)

Overrides com.google.common.collect.CompactHashMap.adjustAfterRemove.

Doc from com.google.common.collect.CompactHashMap.adjustAfterRemove.

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.

Annotations

@Override

allocArrays	back to summary
pack-priv int allocArrays() Overrides com.google.common.collect.CompactHashMap.allocArrays. Doc from com.google.common.collect.CompactHashMap.allocArrays. Handle lazy allocation of arrays. Annotations @Override

allocArrays

back to summary

pack-priv int allocArrays()

Overrides com.google.common.collect.CompactHashMap.allocArrays.

Doc from com.google.common.collect.CompactHashMap.allocArrays.

Handle lazy allocation of arrays.

Annotations

@Override

clear	back to summary
public void clear() Overrides com.google.common.collect.CompactHashMap.clear. Implements java.util.Map.clear. Doc from java.util.AbstractMap.clear. Removes all of the mappings from this map (optional operation). The map will be empty after this call returns. Annotations @Override

clear

back to summary

public void clear()

Overrides com.google.common.collect.CompactHashMap.clear.

Implements java.util.Map.clear.

Doc from java.util.AbstractMap.clear.

Removes all of the mappings from this map (optional operation). The map will be empty after this call returns.

Annotations

@Override

convertToHashFloodingResistantImplementation	back to summary
pack-priv Map<K, V> convertToHashFloodingResistantImplementation() Overrides com.google.common.collect.CompactHashMap.convertToHashFloodingResistantImplementation. Annotations @Override @CanIgnoreReturnValue

convertToHashFloodingResistantImplementation

back to summary

pack-priv Map<K, V> convertToHashFloodingResistantImplementation()

Overrides com.google.common.collect.CompactHashMap.convertToHashFloodingResistantImplementation.

Annotations

@Override
@CanIgnoreReturnValue

create back to summary

create	back to summary
public static <K extends @Nullable Object, V extends @Nullable Object> CompactLinkedHashMap<K, V> create() Hides com.google.common.collect.CompactHashMap.create. Creates an empty `CompactLinkedHashMap` instance.

public static <K extends @Nullable Object, V extends @Nullable Object> CompactLinkedHashMap<K, V> create()

Hides com.google.common.collect.CompactHashMap.create.

Creates an empty CompactLinkedHashMap instance.

createEntrySet	back to summary
pack-priv Set<Map.Entry<K, V>> createEntrySet() Overrides com.google.common.collect.CompactHashMap.createEntrySet. Annotations @Override

createEntrySet

back to summary

pack-priv Set<Map.Entry<K, V>> createEntrySet()

Overrides com.google.common.collect.CompactHashMap.createEntrySet.

Annotations

@Override

createHashFloodingResistantDelegate	back to summary
pack-priv Map<K, V> createHashFloodingResistantDelegate(int tableSize) Overrides com.google.common.collect.CompactHashMap.createHashFloodingResistantDelegate. Annotations @Override

createHashFloodingResistantDelegate

back to summary

pack-priv Map<K, V> createHashFloodingResistantDelegate(int tableSize)

Overrides com.google.common.collect.CompactHashMap.createHashFloodingResistantDelegate.

Annotations

@Override

createKeySet	back to summary
pack-priv Set<K> createKeySet() Overrides com.google.common.collect.CompactHashMap.createKeySet. Annotations @Override

createKeySet

back to summary

pack-priv Set<K> createKeySet()

Overrides com.google.common.collect.CompactHashMap.createKeySet.

Annotations

@Override

createValues	back to summary
pack-priv Collection<V> createValues() Overrides com.google.common.collect.CompactHashMap.createValues. Annotations @Override

createValues

back to summary

pack-priv Collection<V> createValues()

Overrides com.google.common.collect.CompactHashMap.createValues.

Annotations

@Override

createWithExpectedSize back to summary

createWithExpectedSize	back to summary
public static <K extends @Nullable Object, V extends @Nullable Object> CompactLinkedHashMap<K, V> createWithExpectedSize(int expectedSize) Hides com.google.common.collect.CompactHashMap.createWithExpectedSize. Creates a `CompactLinkedHashMap` instance, with a high enough "initial capacity" that it should hold `expectedSize` elements without rebuilding internal data structures. Parameters expectedSize:int the number of elements you expect to add to the returned set Returns:CompactLinkedHashMap<K, V> a new, empty `CompactLinkedHashMap` with enough capacity to hold `expectedSize` elements without resizing Exceptions IllegalArgumentException: if `expectedSize` is negative

public static <K extends @Nullable Object, V extends @Nullable Object> CompactLinkedHashMap<K, V> createWithExpectedSize(int expectedSize)

Hides com.google.common.collect.CompactHashMap.createWithExpectedSize.

Creates a CompactLinkedHashMap instance, with a high enough "initial capacity" that it should hold expectedSize elements without rebuilding internal data structures.

Parameters

expectedSize:int: the number of elements you expect to add to the returned set

Returns:CompactLinkedHashMap<K, V>

a new, empty CompactLinkedHashMap with enough capacity to hold expectedSize elements without resizing

Exceptions

IllegalArgumentException:: if expectedSize is negative

firstEntryIndex	back to summary
pack-priv int firstEntryIndex() Overrides com.google.common.collect.CompactHashMap.firstEntryIndex. Annotations @Override

firstEntryIndex

back to summary

pack-priv int firstEntryIndex()

Overrides com.google.common.collect.CompactHashMap.firstEntryIndex.

Annotations

@Override

getPredecessor	back to summary
private int getPredecessor(int entry)

getSuccessor	back to summary
pack-priv int getSuccessor(int entry) Overrides com.google.common.collect.CompactHashMap.getSuccessor. Annotations @Override

getSuccessor

back to summary

pack-priv int getSuccessor(int entry)

Overrides com.google.common.collect.CompactHashMap.getSuccessor.

Annotations

@Override

init	back to summary
pack-priv void init(int expectedSize) Overrides com.google.common.collect.CompactHashMap.init. Doc from com.google.common.collect.CompactHashMap.init. Pseudoconstructor for serialization support. Annotations @Override

init

back to summary

pack-priv void init(int expectedSize)

Overrides com.google.common.collect.CompactHashMap.init.

Doc from com.google.common.collect.CompactHashMap.init.

Pseudoconstructor for serialization support.

Annotations

@Override

insertEntry	back to summary
pack-priv void insertEntry(int entryIndex, K key, V value, int hash, int mask) Overrides com.google.common.collect.CompactHashMap.insertEntry. Doc from com.google.common.collect.CompactHashMap.insertEntry. Creates a fresh entry with the specified object at the specified position in the entry arrays. Annotations @Override

insertEntry

back to summary

pack-priv void insertEntry(int entryIndex, K key, V value, int hash, int mask)

Overrides com.google.common.collect.CompactHashMap.insertEntry.

Doc from com.google.common.collect.CompactHashMap.insertEntry.

Creates a fresh entry with the specified object at the specified position in the entry arrays.

Annotations

@Override

link	back to summary
private long link(int i)

moveLastEntry back to summary

moveLastEntry	back to summary
pack-priv void moveLastEntry(int dstIndex, int mask) Overrides com.google.common.collect.CompactHashMap.moveLastEntry. Doc from com.google.common.collect.CompactHashMap.moveLastEntry. Moves the last entry in the entry array into `dstIndex`, and nulls out its old position. Annotations @Override

pack-priv void moveLastEntry(int dstIndex, int mask)

Overrides com.google.common.collect.CompactHashMap.moveLastEntry.

Doc from com.google.common.collect.CompactHashMap.moveLastEntry.

Moves the last entry in the entry array into dstIndex, and nulls out its old position.

Annotations

@Override

requireLinks	back to summary
private long[] requireLinks()

resizeEntries	back to summary
pack-priv void resizeEntries(int newCapacity) Overrides com.google.common.collect.CompactHashMap.resizeEntries. Doc from com.google.common.collect.CompactHashMap.resizeEntries. Resizes the internal entries array to the specified capacity, which may be greater or less than the current capacity. Annotations @Override

resizeEntries

back to summary

pack-priv void resizeEntries(int newCapacity)

Overrides com.google.common.collect.CompactHashMap.resizeEntries.

Doc from com.google.common.collect.CompactHashMap.resizeEntries.

Resizes the internal entries array to the specified capacity, which may be greater or less than the current capacity.

Annotations

@Override

setLink	back to summary
private void setLink(int i, long value)

setPredecessor	back to summary
private void setPredecessor(int entry, int pred)

setSucceeds	back to summary
private void setSucceeds(int pred, int succ)

setSuccessor	back to summary
private void setSuccessor(int entry, int succ)

pack-priv Class CompactLinkedHashMap<K extends @Nullable Object, V extends @Nullable Object>

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail