com.google.common.collect

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) 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

java.util.AbstractMap.SimpleEntry<K,V>, java.util.AbstractMap.SimpleImmutableEntry<K,V>

Nested classes/interfaces inherited from interface java.util.Map

java.util.Map.Entry<K,V>

Field Summary

Fields

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()).

Fields inherited from class com.google.common.collect.CompactHashMap

DEFAULT_LOAD_FACTOR, DEFAULT_SIZE, entries, keys, loadFactor, modCount, UNSET, values

Constructor Summary

Constructors

Constructor and Description
CompactLinkedHashMap()
CompactLinkedHashMap(int expectedSize)
CompactLinkedHashMap(int expectedSize, float loadFactor, boolean accessOrder)

Method Summary

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.
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 growth.
(package private) int	firstEntryIndex()
void	forEach(java.util.function.BiConsumer<? super K,? super V> action)
private int	getPredecessor(int entry)
(package private) int	getSuccessor(int entry)
(package private) void	init(int expectedSize, float loadFactor) 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)

Methods inherited from class com.google.common.collect.CompactHashMap

containsKey, containsValue, entrySet, entrySetIterator, get, isEmpty, keySet, keySetIterator, put, remove, replaceAll, size, trimToSize, values, valuesIterator

Methods inherited from class java.util.AbstractMap

clone, equals, hashCode, putAll, toString

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

firstEntry

private transient int firstEntry

Pointer to the first node in the linked list, or ENDPOINT if there are no entries.

lastEntry

private transient int lastEntry

Pointer to the last node in the linked list, or ENDPOINT if there are no entries.

accessOrder

private final boolean accessOrder

Constructor Detail

CompactLinkedHashMap

CompactLinkedHashMap()

CompactLinkedHashMap

CompactLinkedHashMap(int expectedSize)

CompactLinkedHashMap

CompactLinkedHashMap(int expectedSize,
                     float loadFactor,
                     boolean accessOrder)

Method Detail

create

public static <K,V> CompactLinkedHashMap<K,V> create()

Creates an empty CompactLinkedHashMap instance.

createWithExpectedSize

public 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 growth.

Parameters:

expectedSize - the number of elements you expect to add to the returned set

Returns:

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

Throws:

java.lang.IllegalArgumentException - if expectedSize is negative

init

void init(int expectedSize,
          float loadFactor)

Description copied from class: CompactHashMap

Pseudoconstructor for serialization support.

Overrides:

init in class CompactHashMap<K,V>

getPredecessor

private int getPredecessor(int entry)

getSuccessor

int getSuccessor(int entry)

Overrides:

getSuccessor in class CompactHashMap<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 class CompactHashMap<K,V>

accessEntry

void accessEntry(int index)

Description copied from class: CompactHashMap

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

Overrides:

accessEntry in class CompactHashMap<K,V>

moveLastEntry

void moveLastEntry(int dstIndex)

Description copied from class: CompactHashMap

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

Overrides:

moveLastEntry in class CompactHashMap<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 class CompactHashMap<K,V>

firstEntryIndex

int firstEntryIndex()

Overrides:

firstEntryIndex in class CompactHashMap<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 class CompactHashMap<K,V>

forEach

public void forEach(java.util.function.BiConsumer<? super K,? super V> action)

Specified by:

forEach in interface java.util.Map<K,V>

Overrides:

forEach in class CompactHashMap<K,V>

createEntrySet

java.util.Set<java.util.Map.Entry<K,V>> createEntrySet()

Overrides:

createEntrySet in class CompactHashMap<K,V>

createKeySet

java.util.Set<K> createKeySet()

Overrides:

createKeySet in class CompactHashMap<K,V>

createValues

java.util.Collection<V> createValues()

Overrides:

createValues in class CompactHashMap<K,V>

clear

public void clear()

Specified by:

clear in interface java.util.Map<K,V>

Overrides:

clear in class CompactHashMap<K,V>