Guava: Google Core Libraries for Java 33.1.0-jre · com.google.common.collect.CompactHashMap

CompactHashMap is an implementation of a Map. 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.

Unlike java.util.HashMap, iteration is only proportional to the actual size(), which is optimal, and not the size of the internal hashtable, which could be much larger than size(). Furthermore, this structure places significantly reduced load on the garbage collector by only using a constant number of internal objects.

If there are no removals, then iteration order for the entrySet, keySet, and values views is the same as insertion order. Any removal invalidates any ordering guarantees.

This class should not be assumed to be universally superior to java.util.HashMap. 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.

Modifier and Type	Class and Description
pack-priv class	CompactHashMap.EntrySetView
private abstract class	CompactHashMap.Itr<T extends @Nullable Object>
pack-priv class	CompactHashMap.KeySetView
pack-priv class	CompactHashMap.MapEntry
pack-priv class	CompactHashMap.ValuesView

Modifier and Type	Field and Description
pack-priv transient int[]	entries Contains the logical entries, in the range of [0, size()).
private transient Set<Map.Entry<K, V>>	entrySetView
pack-priv static final double	HASH_FLOODING_FPP Maximum allowed false positive probability of detecting a hash flooding attack given random input.
pack-priv transient @Nullable Object[]	keys The keys of the entries in the map, in the range of [0, size()).
private transient Set<K>	keySetView
private static final int	MAX_HASH_BUCKET_LENGTH Maximum allowed length of a hash table bucket before falling back to a j.u.LinkedHashMap-based implementation.
private transient int	metadata Keeps track of metadata like the number of hash table bits and modifications of this data structure (to make it possible to throw ConcurrentModificationException in the iterator).
private static final Object	NOT_FOUND
private transient int	size The number of elements contained in the set.
private transient Object	table The hashtable object.
pack-priv transient @Nullable Object[]	values Hides java.util.AbstractMap.values. The values of the entries in the map, in the range of [0, size()).
private transient Collection<V>	valuesView

Access	Constructor and Description
pack-priv	CompactHashMap() Constructs a new empty instance of `CompactHashMap`.
pack-priv	CompactHashMap(int the initial capacity of this `CompactHashMap`. expectedSize) Constructs a new instance of `CompactHashMap` with the specified capacity.

Method Summary

Modifier and Type	Method and Description
pack-priv void	accessEntry(int index) Mark an access of the specified entry.
pack-priv 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.
pack-priv int	allocArrays() Handle lazy allocation of arrays.
public void	clear() Overrides java.util.AbstractMap.clear. Implements java.util.Map.clear. Removes all of the mappings from this map (optional operation).
public boolean	containsKey(Object key whose presence in this map is to be tested key) Overrides java.util.AbstractMap.containsKey. Implements java.util.Map.containsKey. Returns `true` if this map contains a mapping for the specified key.
public boolean	containsValue(Object value whose presence in this map is to be tested value) Overrides java.util.AbstractMap.containsValue. Implements java.util.Map.containsValue. Returns `true` if this map maps one or more keys to the specified value.
pack-priv Map<K, V>	convertToHashFloodingResistantImplementation()
public static <K extends @Nullable Object, V extends @Nullable Object> CompactHashMap<K, V>	create() Creates an empty `CompactHashMap` instance.
pack-priv Set<Map.Entry<K, V>>	createEntrySet()
pack-priv Map<K, V>	createHashFloodingResistantDelegate(int tableSize)
pack-priv Set<K>	createKeySet()
pack-priv Collection<V>	createValues()
public static <K extends @Nullable Object, V extends @Nullable Object> CompactHashMap<K, V>	Returns: a new, empty `CompactHashMap` with enough capacity to hold `expectedSize` elements without resizing createWithExpectedSize(int the number of elements you expect to add to the returned set expectedSize) Creates a `CompactHashMap` instance, with a high enough "initial capacity" that it should hold `expectedSize` elements without growth.
pack-priv Map<K, V>	delegateOrNull()
private int	entry(int i)
public Set<Map.Entry<K, V>>	entrySet() Implements abstract java.util.AbstractMap.entrySet. Implements java.util.Map.entrySet. Returns a `Set` view of the mappings contained in this map.
pack-priv Iterator<Map.Entry<K, V>>	entrySetIterator()
pack-priv int	firstEntryIndex()
public void	forEach(BiConsumer<? super K, ? super V> The action to be performed for each entry action) Overrides default java.util.Map.forEach. Performs the given action for each entry in this map until all entries have been processed or the action throws an exception.
public V	get(Object the key whose associated value is to be returned key) Overrides java.util.AbstractMap.get. Implements java.util.Map.get. Returns the value to which the specified key is mapped, or `null` if this map contains no mapping for the key.
pack-priv int	getSuccessor(int entryIndex)
private int	hashTableMask() Gets the hash table mask using the stored number of hash table bits.
pack-priv void	incrementModCount()
private int	indexOf(Object key)
pack-priv void	init(int expectedSize) Pseudoconstructor for serialization support.
pack-priv 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.
public boolean	isEmpty() Overrides java.util.AbstractMap.isEmpty. Implements java.util.Map.isEmpty. Returns `true` if this map contains no key-value mappings.
private K	key(int i)
public Set<K>	keySet() Overrides java.util.AbstractMap.keySet. Implements java.util.Map.keySet. Returns a `Set` view of the keys contained in this map.
pack-priv Iterator<K>	keySetIterator()
pack-priv void	moveLastEntry(int dstIndex, int mask) Moves the last entry in the entry array into `dstIndex`, and nulls out its old position.
pack-priv boolean	needsAllocArrays() Returns whether arrays need to be allocated.
public V	put(K key with which the specified value is to be associated key, V value to be associated with the specified key value) Overrides java.util.AbstractMap.put. Implements java.util.Map.put. Associates the specified value with the specified key in this map (optional operation).
private void	readObject(ObjectInputStream stream)
public V	remove(Object key whose mapping is to be removed from the map key) Overrides java.util.AbstractMap.remove. Implements java.util.Map.remove. Removes the mapping for a key from this map if it is present (optional operation).
private @Nullable Object	removeHelper(Object key)
public void	replaceAll(BiFunction<? super K, ? super V, ? extends V> the function to apply to each entry function) Overrides default java.util.Map.replaceAll. Replaces each entry's value with the result of invoking the given function on that entry until all entries have been processed or the function throws an exception (optional operation).
private int[]	requireEntries()
private @Nullable Object[]	requireKeys()
private Object	requireTable()
private @Nullable Object[]	requireValues()
pack-priv 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	resizeMeMaybe(int newSize) Resizes the entries storage if necessary.
private int	resizeTable(int oldMask, int newCapacity, int targetHash, int targetEntryIndex)
private void	setEntry(int i, int value)
private void	setHashTableMask(int mask) Stores the hash table mask as the number of bits needed to represent an index.
private void	setKey(int i, K key)
private void	setValue(int i, V value)
public int	size() Overrides java.util.AbstractMap.size. Implements java.util.Map.size. Returns the number of key-value mappings in this map.
public void	trimToSize() Ensures that this `CompactHashMap` has the smallest representation in memory, given its current size.
private V	value(int i)
public Collection<V>	values() Overrides java.util.AbstractMap.values. Implements java.util.Map.values. Returns a `Collection` view of the values contained in this map.
pack-priv Iterator<V>	valuesIterator()
private void	writeObject(ObjectOutputStream stream)

Inherited from java.util.AbstractMap:: clone equals hashCode putAll toString

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

Nested and Inner Type Summary

Field Summary

Constructor Summary

Method Summary