@GwtIncompatible class CompactHashMap<K,V> extends java.util.AbstractMap<K,V> implements java.io.Serializable
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 |
---|---|
(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 |
Modifier and Type | Field and Description |
---|---|
(package private) static float |
DEFAULT_LOAD_FACTOR |
(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 |
(package private) float |
loadFactor
The load factor.
|
private static int |
MAXIMUM_CAPACITY |
(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.
|
private int |
threshold
When we have this many elements, resize 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 and Description |
---|
CompactHashMap()
Constructs a new empty instance of
CompactHashMap . |
CompactHashMap(int capacity)
Constructs a new instance of
CompactHashMap with the specified capacity. |
CompactHashMap(int expectedSize,
float loadFactor) |
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() |
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,
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.
|
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. |
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)
Returns currentSize + 1, after resizing 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)
The serial form currently mimics Android's java.util.HashMap version, e.g.
|
private static final int MAXIMUM_CAPACITY
static final float DEFAULT_LOAD_FACTOR
private static final long NEXT_MASK
private static final long HASH_MASK
static final int DEFAULT_SIZE
static final int UNSET
private transient int[] table
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.
transient long[] entries
transient java.lang.Object[] keys
null
.transient java.lang.Object[] values
null
.transient float loadFactor
transient int modCount
private transient int threshold
private transient int size
private transient java.util.Set<K> keySetView
private transient java.util.Collection<V> valuesView
CompactHashMap()
CompactHashMap
.CompactHashMap(int capacity)
CompactHashMap
with the specified capacity.capacity
- the initial capacity of this CompactHashMap
.CompactHashMap(int expectedSize, float loadFactor)
public static <K,V> CompactHashMap<K,V> create()
CompactHashMap
instance.public static <K,V> CompactHashMap<K,V> createWithExpectedSize(int expectedSize)
CompactHashMap
instance, with a high enough "initial capacity" that it
should hold expectedSize
elements without growth.expectedSize
- the number of elements you expect to add to the returned setCompactHashMap
with enough capacity to hold expectedSize
elements without resizingjava.lang.IllegalArgumentException
- if expectedSize
is negativevoid init(int expectedSize, float loadFactor)
private static int[] newTable(int size)
private static long[] newEntries(int size)
private int hashTableMask()
private static int getHash(long entry)
private static int getNext(long entry)
private static long swapNext(long entry, int newNext)
void accessEntry(int index)
CompactLinkedHashMap
for LRU
ordering.void insertEntry(int entryIndex, K key, V value, int hash)
private void resizeMeMaybe(int newSize)
void resizeEntries(int newCapacity)
private void resizeTable(int newCapacity)
private int indexOf(java.lang.Object key)
public boolean containsKey(java.lang.Object key)
public V get(java.lang.Object key)
public V remove(java.lang.Object key)
private V remove(java.lang.Object key, int hash)
private V removeEntry(int entryIndex)
void moveLastEntry(int dstIndex)
dstIndex
, and nulls out its old position.int firstEntryIndex()
int getSuccessor(int entryIndex)
int adjustAfterRemove(int indexBeforeRemove, int indexRemoved)
public void replaceAll(java.util.function.BiFunction<? super K,? super V,? extends V> function)
public java.util.Set<K> keySet()
java.util.Set<K> createKeySet()
java.util.Iterator<K> keySetIterator()
public int size()
public boolean isEmpty()
public boolean containsValue(java.lang.Object value)
public java.util.Collection<V> values()
java.util.Collection<V> createValues()
java.util.Iterator<V> valuesIterator()
public void trimToSize()
CompactHashMap
has the smallest representation in memory, given its
current size.public void clear()
private void writeObject(java.io.ObjectOutputStream stream) throws java.io.IOException
java.io.IOException
private void readObject(java.io.ObjectInputStream stream) throws java.io.IOException, java.lang.ClassNotFoundException
java.io.IOException
java.lang.ClassNotFoundException