{@code containsKey(k)}, {@code put(k, v)} and {@code 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 {@code java.util.HashMap}, iteration is only proportional to the actual {@code size()}, * which is optimal, and not the size of the internal hashtable, which could be much larger * than {@code 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 {@link #entrySet}, {@link #keySet()}, * and {@link #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 {@code 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.
*
* @author Louis Wasserman
*/
public class CompactHashMap 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.
*/
private transient int[] table;
/**
* 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).
*/
private transient long[] entries;
/**
* The keys of the entries in the map, in the range of [0, size()). The keys in [size(),
* keys.length) are all {@code null}.
*/
private transient Object[] keys;
/**
* The values of the entries in the map, in the range of [0, size()). The values in [size(),
* values.length) are all {@code null}.
*/
private transient Object[] values;
/**
* 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.
*/
private transient int modCount;
/** The number of elements contained in the set. */
private transient int size;
/**
* Constructs a new instance of {@code CompactHashMap} with the specified capacity.
*
* @param expectedSize the initial capacity of this {@code CompactHashMap}.
*/
CompactHashMap(int expectedSize) {
Preconditions.checkArgument(expectedSize >= 0, "Expected size must be non-negative");
this.modCount = Math.max(1, expectedSize); // Save expectedSize for use in allocArrays()
}
/** Returns whether arrays need to be allocated. */
private boolean needsAllocArrays() {
return table == null;
}
/** Handle lazy allocation of arrays. */
private void allocArrays() {
checkState(needsAllocArrays(), "Arrays already allocated");
int expectedSize = modCount;
int buckets = closedTableSize(expectedSize);
this.table = newTable(buckets);
this.entries = newEntries(expectedSize);
this.keys = new Object[expectedSize];
this.values = new Object[expectedSize];
}
private static int[] newTable(int size) {
int[] array = new int[size];
Arrays.fill(array, UNSET);
return array;
}
private static long[] newEntries(int size) {
long[] array = new long[size];
Arrays.fill(array, UNSET);
return array;
}
private int hashTableMask() {
return table.length - 1;
}
private static int getHash(long entry) {
return (int) (entry >>> 32);
}
/** Returns the index, or UNSET if the pointer is "null" */
private static int getNext(long entry) {
return (int) entry;
}
/** Returns a new entry value by changing the "next" index of an existing entry */
private static long swapNext(long entry, int newNext) {
return (HASH_MASK & entry) | (NEXT_MASK & newNext);
}
@CanIgnoreReturnValue
@Override
@Nullable
public V put(@Nullable K key, @Nullable V value) {
if (needsAllocArrays()) {
allocArrays();
}
long[] entries = this.entries;
Object[] keys = this.keys;
Object[] values = this.values;
int hash = smearedHash(key);
int tableIndex = hash & hashTableMask();
int newEntryIndex = this.size; // current size, and pointer to the entry to be appended
int next = table[tableIndex];
if (next == UNSET) { // uninitialized bucket
table[tableIndex] = newEntryIndex;
} else {
int last;
long entry;
do {
last = next;
entry = entries[next];
if (getHash(entry) == hash && Objects.equal(key, keys[next])) {
@SuppressWarnings("unchecked") // known to be a V
@Nullable
V oldValue = (V) values[next];
values[next] = value;
return oldValue;
}
next = getNext(entry);
} while (next != UNSET);
entries[last] = swapNext(entry, newEntryIndex);
}
if (newEntryIndex == Integer.MAX_VALUE) {
throw new IllegalStateException("Cannot contain more than Integer.MAX_VALUE elements!");
}
int newSize = newEntryIndex + 1;
resizeMeMaybe(newSize);
insertEntry(newEntryIndex, key, value, hash);
this.size = newSize;
int oldCapacity = table.length;
if (needsResizing(newEntryIndex, oldCapacity)) {
resizeTable(2 * oldCapacity);
}
modCount++;
return null;
}
/**
* Creates a fresh entry with the specified object at the specified position in the entry arrays.
*/
private void insertEntry(int entryIndex, @Nullable K key, @Nullable V value, int hash) {
this.entries[entryIndex] = ((long) hash << 32) | (NEXT_MASK & UNSET);
this.keys[entryIndex] = key;
this.values[entryIndex] = value;
}
/** Resizes the entries storage if necessary. */
private void resizeMeMaybe(int newSize) {
int entriesSize = entries.length;
if (newSize > entriesSize) {
int newCapacity = entriesSize + Math.max(1, entriesSize >>> 1);
if (newCapacity < 0) {
newCapacity = Integer.MAX_VALUE;
}
if (newCapacity != entriesSize) {
resizeEntries(newCapacity);
}
}
}
/**
* Resizes the internal entries array to the specified capacity, which may be greater or less than
* the current capacity.
*/
private void resizeEntries(int newCapacity) {
this.keys = Arrays.copyOf(keys, newCapacity);
this.values = Arrays.copyOf(values, newCapacity);
long[] entries = this.entries;
int oldCapacity = entries.length;
entries = Arrays.copyOf(entries, newCapacity);
if (newCapacity > oldCapacity) {
Arrays.fill(entries, oldCapacity, newCapacity, UNSET);
}
this.entries = entries;
}
private void resizeTable(int newCapacity) { // newCapacity always a power of two
int[] newTable = newTable(newCapacity);
long[] entries = this.entries;
int mask = newTable.length - 1;
for (int i = 0; i < size; i++) {
long oldEntry = entries[i];
int hash = getHash(oldEntry);
int tableIndex = hash & mask;
int next = newTable[tableIndex];
newTable[tableIndex] = i;
entries[i] = ((long) hash << 32) | (NEXT_MASK & next);
}
this.table = newTable;
}
private int indexOf(@Nullable Object key) {
if (needsAllocArrays()) {
return -1;
}
int hash = smearedHash(key);
int next = table[hash & hashTableMask()];
while (next != UNSET) {
long entry = entries[next];
if (getHash(entry) == hash && Objects.equal(key, keys[next])) {
return next;
}
next = getNext(entry);
}
return -1;
}
@Override
public boolean containsKey(@Nullable Object key) {
return indexOf(key) != -1;
}
@Nullable
@SuppressWarnings("unchecked") // values only contains Vs
@Override
public V get(@Nullable Object key) {
int index = indexOf(key);
return (index == -1) ? null : (V) values[index];
}
@CanIgnoreReturnValue
@Override
@Nullable
public V remove(@Nullable Object key) {
if (needsAllocArrays()) {
return null;
}
return remove(key, smearedHash(key));
}
@Nullable
private V remove(@Nullable Object key, int hash) {
int tableIndex = hash & hashTableMask();
int next = table[tableIndex];
if (next == UNSET) { // empty bucket
return null;
}
int last = UNSET;
do {
if (getHash(entries[next]) == hash && Objects.equal(key, keys[next])) {
@SuppressWarnings("unchecked") // values only contains Vs
@Nullable
V oldValue = (V) values[next];
if (last == UNSET) {
// we need to update the root link from table[]
table[tableIndex] = getNext(entries[next]);
} else {
// we need to update the link from the chain
entries[last] = swapNext(entries[last], getNext(entries[next]));
}
moveLastEntry(next);
size--;
modCount++;
return oldValue;
}
last = next;
next = getNext(entries[next]);
} while (next != UNSET);
return null;
}
@CanIgnoreReturnValue
private V removeEntry(int entryIndex) {
return remove(keys[entryIndex], getHash(entries[entryIndex]));
}
/**
* Moves the last entry in the entry array into {@code dstIndex}, and nulls out its old position.
*/
private void moveLastEntry(int dstIndex) {
int srcIndex = size() - 1;
if (dstIndex < srcIndex) {
// move last entry to deleted spot
keys[dstIndex] = keys[srcIndex];
values[dstIndex] = values[srcIndex];
keys[srcIndex] = null;
values[srcIndex] = null;
// move the last entry to the removed spot, just like we moved the element
long lastEntry = entries[srcIndex];
entries[dstIndex] = lastEntry;
entries[srcIndex] = UNSET;
// also need to update whoever's "next" pointer was pointing to the last entry place
// reusing "tableIndex" and "next"; these variables were no longer needed
int tableIndex = getHash(lastEntry) & hashTableMask();
int lastNext = table[tableIndex];
if (lastNext == srcIndex) {
// we need to update the root pointer
table[tableIndex] = dstIndex;
} else {
// we need to update a pointer in an entry
int previous;
long entry;
do {
previous = lastNext;
lastNext = getNext(entry = entries[lastNext]);
} while (lastNext != srcIndex);
// here, entries[previous] points to the old entry location; update it
entries[previous] = swapNext(entry, dstIndex);
}
} else {
keys[dstIndex] = null;
values[dstIndex] = null;
entries[dstIndex] = UNSET;
}
}
private int firstEntryIndex() {
return isEmpty() ? -1 : 0;
}
private int getSuccessor(int entryIndex) {
return (entryIndex + 1 < size) ? entryIndex + 1 : -1;
}
/**
* 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.
*/
private static int adjustAfterRemove(int indexBeforeRemove) {
return indexBeforeRemove - 1;
}
private abstract class Itr