java.lang.Object
- java.util.AbstractMap<K,V>
- - com.google.common.collect.CompactHashMap<K,V>

All Implemented Interfaces:

java.io.Serializable, java.util.Map<K,V>

Direct Known Subclasses:

CompactLinkedHashMap
```
@GwtIncompatible
class CompactHashMap<K,V>
extends java.util.AbstractMap<K,V>
implements java.io.Serializable
```
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.

Nested Class Summary

Nested Classes
Modifier and Type	Class	Description
`(package private) class`	`CompactHashMap.EntrySetView`
`private class`	`CompactHashMap.Itr<T>`
`(package private) class`	`CompactHashMap.KeySetView`
`(package private) class`	`CompactHashMap.MapEntry`
`(package private) class`	`CompactHashMap.ValuesView`

Nested classes/interfaces inherited from class java.util.AbstractMap
java.util.AbstractMap.SimpleEntry<K extends java.lang.Object,V extends java.lang.Object>, java.util.AbstractMap.SimpleImmutableEntry<K extends java.lang.Object,V extends java.lang.Object>

Nested classes/interfaces inherited from interface java.util.Map
java.util.Map.Entry<K extends java.lang.Object,V extends java.lang.Object>

Field Summary

Fields
Modifier and Type	Field	Description
`(package private) static int`	`DEFAULT_SIZE`
`(package private) long[]`	`entries`	Contains the logical entries, in the range of [0, size()).
`private java.util.Set<java.util.Map.Entry<K,V>>`	`entrySetView`
`private static long`	`HASH_MASK`	Bitmask that selects the high 32 bits.
`(package private) java.lang.Object[]`	`keys`	The keys of the entries in the map, in the range of [0, size()).
`private java.util.Set<K>`	`keySetView`
`private static float`	`LOAD_FACTOR`
`(package private) int`	`modCount`	Keeps track of modifications of this set, to make it possible to throw ConcurrentModificationException in the iterator.
`private static long`	`NEXT_MASK`	Bitmask that selects the low 32 bits.
`private int`	`size`	The number of elements contained in the set.
`private int[]`	`table`	The hashtable.
`(package private) static int`	`UNSET`
`(package private) java.lang.Object[]`	`values`	The values of the entries in the map, in the range of [0, size()).
`private java.util.Collection<V>`	`valuesView`

Constructor Summary

Constructors
Constructor	Description
`CompactHashMap()`	Constructs a new empty instance of `CompactHashMap`.
`CompactHashMap(int expectedSize)`	Constructs a new instance of `CompactHashMap` with the specified capacity.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method	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()`
`boolean`	`containsKey(java.lang.Object key)`
`boolean`	`containsValue(java.lang.Object value)`
`static <K,V> CompactHashMap<K,V>`	`create()`	Creates an empty `CompactHashMap` 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> CompactHashMap<K,V>`	`createWithExpectedSize(int expectedSize)`	Creates a `CompactHashMap` instance, with a high enough "initial capacity" that it should hold `expectedSize` elements without growth.
`java.util.Set<java.util.Map.Entry<K,V>>`	`entrySet()`
`(package private) java.util.Iterator<java.util.Map.Entry<K,V>>`	`entrySetIterator()`
`(package private) int`	`firstEntryIndex()`
`void`	`forEach(java.util.function.BiConsumer<? super K,? super V> action)`
`V`	`get(java.lang.Object key)`
`private static int`	`getHash(long entry)`
`private static int`	`getNext(long entry)`	Returns the index, or UNSET if the pointer is "null"
`(package private) int`	`getSuccessor(int entryIndex)`
`private int`	`hashTableMask()`
`private int`	`indexOf(java.lang.Object key)`
`(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.
`boolean`	`isEmpty()`
`java.util.Set<K>`	`keySet()`
`(package private) java.util.Iterator<K>`	`keySetIterator()`
`(package private) void`	`moveLastEntry(int dstIndex)`	Moves the last entry in the entry array into `dstIndex`, and nulls out its old position.
`(package private) boolean`	`needsAllocArrays()`	Returns whether arrays need to be allocated.
`private static long[]`	`newEntries(int size)`
`private static int[]`	`newTable(int size)`
`V`	`put(K key, V value)`
`private void`	`readObject(java.io.ObjectInputStream stream)`
`V`	`remove(java.lang.Object key)`
`private V`	`remove(java.lang.Object key, int hash)`
`private V`	`removeEntry(int entryIndex)`
`void`	`replaceAll(java.util.function.BiFunction<? super K,? super V,? extends V> function)`
`(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`	`resizeMeMaybe(int newSize)`	Resizes the entries storage if necessary.
`private void`	`resizeTable(int newCapacity)`
`int`	`size()`
`private static long`	`swapNext(long entry, int newNext)`	Returns a new entry value by changing the "next" index of an existing entry
`void`	`trimToSize()`	Ensures that this `CompactHashMap` has the smallest representation in memory, given its current size.
`java.util.Collection<V>`	`values()`
`(package private) java.util.Iterator<V>`	`valuesIterator()`
`private void`	`writeObject(java.io.ObjectOutputStream stream)`

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
  - LOAD_FACTOR
```
private static final float LOAD_FACTOR
```
    See Also:
    
    Constant Field Values
  - NEXT_MASK
```
private static final long NEXT_MASK
```
    Bitmask that selects the low 32 bits.
    
    See Also:
    
    Constant Field Values
  - HASH_MASK
```
private static final long HASH_MASK
```
    Bitmask that selects the high 32 bits.
    
    See Also:
    
    Constant Field Values
  - DEFAULT_SIZE
```
static final int DEFAULT_SIZE
```
    See Also:
    
    Constant Field Values
  - UNSET
```
static final int UNSET
```
    See Also:
    
    Constant Field Values
  - table
```
private transient int[] table
```
    The hashtable. Its values are indexes to the keys, values, and entries arrays.
    Currently, the UNSET value means "null pointer", and any non negative value x is the actual index.
    Its size must be a power of two.
  - entries
```
transient long[] entries
```
    Contains the logical entries, in the range of [0, size()). The high 32 bits of each long is the smeared hash of the element, whereas the low 32 bits is the "next" pointer (pointing to the next entry in the bucket chain). The pointers in [size(), entries.length) are all "null" (UNSET).
  - keys
```
transient java.lang.Object[] keys
```
    The keys of the entries in the map, in the range of [0, size()). The keys in [size(), keys.length) are all null.
  - values
```
transient java.lang.Object[] values
```
    The values of the entries in the map, in the range of [0, size()). The values in [size(), values.length) are all null.
  - modCount
```
transient int modCount
```
    Keeps track of modifications of this set, to make it possible to throw ConcurrentModificationException in the iterator. Note that we choose not to make this volatile, so we do less of a "best effort" to track such errors, for better performance.
  - size
```
private transient int size
```
    The number of elements contained in the set.
  - keySetView
```
private transient java.util.Set<K> keySetView
```
  - entrySetView
```
private transient java.util.Set<java.util.Map.Entry<K,V>> entrySetView
```
  - valuesView
```
private transient java.util.Collection<V> valuesView
```
- Constructor Detail
  - CompactHashMap
```
CompactHashMap()
```
    Constructs a new empty instance of CompactHashMap.
  - CompactHashMap
```
CompactHashMap(int expectedSize)
```
    Constructs a new instance of CompactHashMap with the specified capacity.
    
    Parameters:
    
    expectedSize - the initial capacity of this CompactHashMap.
- Method Detail
  - create
```
public static <K,V> CompactHashMap<K,V> create()
```
    Creates an empty CompactHashMap instance.
  - createWithExpectedSize
```
public static <K,V> CompactHashMap<K,V> createWithExpectedSize(int expectedSize)
```
    Creates a CompactHashMap 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 CompactHashMap with enough capacity to hold expectedSize elements without resizing
    
    Throws:
    
    java.lang.IllegalArgumentException - if expectedSize is negative
  - init
```
void init(int expectedSize)
```
    Pseudoconstructor for serialization support.
  - needsAllocArrays
```
boolean needsAllocArrays()
```
    Returns whether arrays need to be allocated.
  - allocArrays
```
void allocArrays()
```
    Handle lazy allocation of arrays.
  - newTable
```
private static int[] newTable(int size)
```
  - newEntries
```
private static long[] newEntries(int size)
```
  - hashTableMask
```
private int hashTableMask()
```
  - getHash
```
private static int getHash(long entry)
```
  - getNext
```
private static int getNext(long entry)
```
    Returns the index, or UNSET if the pointer is "null"
  - swapNext
```
private static long swapNext(long entry,
                             int newNext)
```
    Returns a new entry value by changing the "next" index of an existing entry
  - accessEntry
```
void accessEntry(int index)
```
    Mark an access of the specified entry. Used only in CompactLinkedHashMap for LRU ordering.
  - put
```
public V put(K key,
             V value)
```
    Specified by:
    
    put in interface java.util.Map<K,V>
    
    Overrides:
    
    put in class java.util.AbstractMap<K,V>
  - insertEntry
```
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.
  - resizeMeMaybe
```
private void resizeMeMaybe(int newSize)
```
    Resizes the entries storage if necessary.
  - resizeEntries
```
void resizeEntries(int newCapacity)
```
    Resizes the internal entries array to the specified capacity, which may be greater or less than the current capacity.
  - resizeTable
```
private void resizeTable(int newCapacity)
```
  - indexOf
```
private int indexOf(java.lang.Object key)
```
  - containsKey
```
public boolean containsKey(java.lang.Object key)
```
    Specified by:
    
    containsKey in interface java.util.Map<K,V>
    
    Overrides:
    
    containsKey in class java.util.AbstractMap<K,V>
  - get
```
public V get(java.lang.Object key)
```
    Specified by:
    
    get in interface java.util.Map<K,V>
    
    Overrides:
    
    get in class java.util.AbstractMap<K,V>
  - remove
```
public V remove(java.lang.Object key)
```
    Specified by:
    
    remove in interface java.util.Map<K,V>
    
    Overrides:
    
    remove in class java.util.AbstractMap<K,V>
  - remove
```
private V remove(java.lang.Object key,
                 int hash)
```
  - removeEntry
```
private V removeEntry(int entryIndex)
```
  - moveLastEntry
```
void moveLastEntry(int dstIndex)
```
    Moves the last entry in the entry array into dstIndex, and nulls out its old position.
  - firstEntryIndex
```
int firstEntryIndex()
```
  - getSuccessor
```
int getSuccessor(int entryIndex)
```
  - adjustAfterRemove
```
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.
  - replaceAll
```
public void replaceAll(java.util.function.BiFunction<? super K,? super V,? extends V> function)
```
    Specified by:
    
    replaceAll in interface java.util.Map<K,V>
  - keySet
```
public java.util.Set<K> keySet()
```
    Specified by:
    
    keySet in interface java.util.Map<K,V>
    
    Overrides:
    
    keySet in class java.util.AbstractMap<K,V>
  - createKeySet
```
java.util.Set<K> createKeySet()
```
  - keySetIterator
```
java.util.Iterator<K> keySetIterator()
```
  - forEach
```
public void forEach(java.util.function.BiConsumer<? super K,? super V> action)
```
    Specified by:
    
    forEach in interface java.util.Map<K,V>
  - entrySet
```
public java.util.Set<java.util.Map.Entry<K,V>> entrySet()
```
    Specified by:
    
    entrySet in interface java.util.Map<K,V>
    
    Specified by:
    
    entrySet in class java.util.AbstractMap<K,V>
  - createEntrySet
```
java.util.Set<java.util.Map.Entry<K,V>> createEntrySet()
```
  - entrySetIterator
```
java.util.Iterator<java.util.Map.Entry<K,V>> entrySetIterator()
```
  - size
```
public int size()
```
    Specified by:
    
    size in interface java.util.Map<K,V>
    
    Overrides:
    
    size in class java.util.AbstractMap<K,V>
  - isEmpty
```
public boolean isEmpty()
```
    Specified by:
    
    isEmpty in interface java.util.Map<K,V>
    
    Overrides:
    
    isEmpty in class java.util.AbstractMap<K,V>
  - containsValue
```
public boolean containsValue(java.lang.Object value)
```
    Specified by:
    
    containsValue in interface java.util.Map<K,V>
    
    Overrides:
    
    containsValue in class java.util.AbstractMap<K,V>
  - values
```
public java.util.Collection<V> values()
```
    Specified by:
    
    values in interface java.util.Map<K,V>
    
    Overrides:
    
    values in class java.util.AbstractMap<K,V>
  - createValues
```
java.util.Collection<V> createValues()
```
  - valuesIterator
```
java.util.Iterator<V> valuesIterator()
```
  - trimToSize
```
public void trimToSize()
```
    Ensures that this CompactHashMap has the smallest representation in memory, given its current size.
  - clear
```
public void clear()
```
    Specified by:
    
    clear in interface java.util.Map<K,V>
    
    Overrides:
    
    clear in class java.util.AbstractMap<K,V>
  - writeObject
```
private void writeObject(java.io.ObjectOutputStream stream)
                  throws java.io.IOException
```
    Throws:
    
    java.io.IOException
  - readObject
```
private void readObject(java.io.ObjectInputStream stream)
                 throws java.io.IOException,
                        java.lang.ClassNotFoundException
```
    Throws:
    
    java.io.IOException
    
    java.lang.ClassNotFoundException

Class CompactHashMap<K,​V>

Nested Class Summary

Nested classes/interfaces inherited from class java.util.AbstractMap

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

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.util.AbstractMap

Methods inherited from class java.lang.Object

Methods inherited from interface java.util.Map

Field Detail

LOAD_FACTOR

NEXT_MASK

HASH_MASK

DEFAULT_SIZE

UNSET

table

entries

keys

values

modCount

size

keySetView

entrySetView

valuesView

Constructor Detail

CompactHashMap

CompactHashMap

Method Detail

create

createWithExpectedSize

init

needsAllocArrays

allocArrays

newTable

newEntries

hashTableMask

getHash

getNext

swapNext

accessEntry

put

insertEntry

resizeMeMaybe

resizeEntries

resizeTable

indexOf

containsKey

get

remove

remove

removeEntry

moveLastEntry

firstEntryIndex

getSuccessor

adjustAfterRemove

replaceAll

keySet

createKeySet

keySetIterator

forEach

entrySet

createEntrySet

entrySetIterator

size

isEmpty

containsValue

values

createValues

valuesIterator

trimToSize

clear

writeObject

readObject

Class CompactHashMap<K,V>