1 /*
2 * Copyright (C) 2012 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.google.common.collect;
18
19 import static com.google.common.base.Preconditions.checkNotNull;
20 import static com.google.common.collect.CollectPreconditions.checkRemove;
21 import static com.google.common.collect.CompactHashing.UNSET;
22 import static com.google.common.collect.Hashing.smearedHash;
23
24 import com.google.common.annotations.GwtIncompatible;
25 import com.google.common.annotations.VisibleForTesting;
26 import com.google.common.base.Objects;
27 import com.google.common.base.Preconditions;
28 import com.google.common.primitives.Ints;
29 import com.google.errorprone.annotations.CanIgnoreReturnValue;
30 import com.google.j2objc.annotations.WeakOuter;
31 import java.io.IOException;
32 import java.io.InvalidObjectException;
33 import java.io.ObjectInputStream;
34 import java.io.ObjectOutputStream;
35 import java.io.Serializable;
36 import java.util.AbstractMap;
37 import java.util.Arrays;
38 import java.util.Collection;
39 import java.util.ConcurrentModificationException;
40 import java.util.Iterator;
41 import java.util.LinkedHashMap;
42 import java.util.Map;
43 import java.util.NoSuchElementException;
44 import java.util.Set;
45 import java.util.Spliterator;
46 import java.util.Spliterators;
47 import java.util.function.BiConsumer;
48 import java.util.function.BiFunction;
49 import java.util.function.Consumer;
50 import org.checkerframework.checker.nullness.qual.Nullable;
51
52 /**
53 * CompactHashMap is an implementation of a Map. All optional operations (put and remove) are
54 * supported. Null keys and values are supported.
55 *
56 * <p>{@code containsKey(k)}, {@code put(k, v)} and {@code remove(k)} are all (expected and
57 * amortized) constant time operations. Expected in the hashtable sense (depends on the hash
58 * function doing a good job of distributing the elements to the buckets to a distribution not far
59 * from uniform), and amortized since some operations can trigger a hash table resize.
60 *
61 * <p>Unlike {@code java.util.HashMap}, iteration is only proportional to the actual {@code size()},
62 * which is optimal, and <i>not</i> the size of the internal hashtable, which could be much larger
63 * than {@code size()}. Furthermore, this structure places significantly reduced load on the garbage
64 * collector by only using a constant number of internal objects.
65 *
66 * <p>If there are no removals, then iteration order for the {@link #entrySet}, {@link #keySet}, and
67 * {@link #values} views is the same as insertion order. Any removal invalidates any ordering
68 * guarantees.
69 *
70 * <p>This class should not be assumed to be universally superior to {@code java.util.HashMap}.
71 * Generally speaking, this class reduces object allocation and memory consumption at the price of
72 * moderately increased constant factors of CPU. Only use this class when there is a specific reason
73 * to prioritize memory over CPU.
74 *
75 * @author Louis Wasserman
76 * @author Jon Noack
77 */
78 @GwtIncompatible // not worth using in GWT for now
79 class CompactHashMap<K, V> extends AbstractMap<K, V> implements Serializable {
80 /*
81 * TODO: Make this a drop-in replacement for j.u. versions, actually drop them in, and test the
82 * world. Figure out what sort of space-time tradeoff we're actually going to get here with the
83 * *Map variants. This class is particularly hard to benchmark, because the benefit is not only in
84 * less allocation, but also having the GC do less work to scan the heap because of fewer
85 * references, which is particularly hard to quantify.
86 */
87
88 /** Creates an empty {@code CompactHashMap} instance. */
89 public static <K, V> CompactHashMap<K, V> create() {
90 return new CompactHashMap<>();
91 }
92
93 /**
94 * Creates a {@code CompactHashMap} instance, with a high enough "initial capacity" that it
95 * <i>should</i> hold {@code expectedSize} elements without growth.
96 *
97 * @param expectedSize the number of elements you expect to add to the returned set
98 * @return a new, empty {@code CompactHashMap} with enough capacity to hold {@code expectedSize}
99 * elements without resizing
100 * @throws IllegalArgumentException if {@code expectedSize} is negative
101 */
102 public static <K, V> CompactHashMap<K, V> createWithExpectedSize(int expectedSize) {
103 return new CompactHashMap<>(expectedSize);
104 }
105
106 private static final Object NOT_FOUND = new Object();
107
108 /**
109 * Maximum allowed false positive probability of detecting a hash flooding attack given random
110 * input.
111 */
112 @VisibleForTesting(
113 )
114 static final double HASH_FLOODING_FPP = 0.001;
115
116 /**
117 * Maximum allowed length of a hash table bucket before falling back to a j.u.LinkedHashMap-based
118 * implementation. Experimentally determined.
119 */
120 private static final int MAX_HASH_BUCKET_LENGTH = 9;
121
122 /**
123 * The hashtable object. This can be either:
124 *
125 * <ul>
126 * <li>a byte[], short[], or int[], with size a power of two, created by
127 * CompactHashing.createTable, whose values are either
128 * <ul>
129 * <li>UNSET, meaning "null pointer"
130 * <li>one plus an index into the keys, values, and entries arrays
131 * </ul>
132 * <li>another java.util.Map delegate implementation. In most modern JDKs, normal java.util hash
133 * collections intelligently fall back to a binary search tree if hash table collisions are
134 * detected. Rather than going to all the trouble of reimplementing this ourselves, we
135 * simply switch over to use the JDK implementation wholesale if probable hash flooding is
136 * detected, sacrificing the compactness guarantee in very rare cases in exchange for much
137 * more reliable worst-case behavior.
138 * <li>null, if no entries have yet been added to the map
139 * </ul>
140 */
141 @Nullable private transient Object table;
142
143 /**
144 * Contains the logical entries, in the range of [0, size()). The high bits of each int are the
145 * part of the smeared hash of the key not covered by the hashtable mask, whereas the low bits are
146 * the "next" pointer (pointing to the next entry in the bucket chain), which will always be less
147 * than or equal to the hashtable mask.
148 *
149 * <pre>
150 * hash = aaaaaaaa
151 * mask = 0000ffff
152 * next = 0000bbbb
153 * entry = aaaabbbb
154 * </pre>
155 *
156 * <p>The pointers in [size(), entries.length) are all "null" (UNSET).
157 */
158 @VisibleForTesting transient int @Nullable [] entries;
159
160 /**
161 * The keys of the entries in the map, in the range of [0, size()). The keys in [size(),
162 * keys.length) are all {@code null}.
163 */
164 @VisibleForTesting transient Object @Nullable [] keys;
165
166 /**
167 * The values of the entries in the map, in the range of [0, size()). The values in [size(),
168 * values.length) are all {@code null}.
169 */
170 @VisibleForTesting transient Object @Nullable [] values;
171
172 /**
173 * Keeps track of metadata like the number of hash table bits and modifications of this data
174 * structure (to make it possible to throw ConcurrentModificationException in the iterator). Note
175 * that we choose not to make this volatile, so we do less of a "best effort" to track such
176 * errors, for better performance.
177 */
178 private transient int metadata;
179
180 /** The number of elements contained in the set. */
181 private transient int size;
182
183 /** Constructs a new empty instance of {@code CompactHashMap}. */
184 CompactHashMap() {
185 init(CompactHashing.DEFAULT_SIZE);
186 }
187
188 /**
189 * Constructs a new instance of {@code CompactHashMap} with the specified capacity.
190 *
191 * @param expectedSize the initial capacity of this {@code CompactHashMap}.
192 */
193 CompactHashMap(int expectedSize) {
194 init(expectedSize);
195 }
196
197 /** Pseudoconstructor for serialization support. */
198 void init(int expectedSize) {
199 Preconditions.checkArgument(expectedSize >= 0, "Expected size must be >= 0");
200
201 // Save expectedSize for use in allocArrays()
202 this.metadata = Ints.constrainToRange(expectedSize, 1, CompactHashing.MAX_SIZE);
203 }
204
205 /** Returns whether arrays need to be allocated. */
206 @VisibleForTesting
207 boolean needsAllocArrays() {
208 return table == null;
209 }
210
211 /** Handle lazy allocation of arrays. */
212 @CanIgnoreReturnValue
213 int allocArrays() {
214 Preconditions.checkState(needsAllocArrays(), "Arrays already allocated");
215
216 int expectedSize = metadata;
217 int buckets = CompactHashing.tableSize(expectedSize);
218 this.table = CompactHashing.createTable(buckets);
219 setHashTableMask(buckets - 1);
220
221 this.entries = new int[expectedSize];
222 this.keys = new Object[expectedSize];
223 this.values = new Object[expectedSize];
224
225 return expectedSize;
226 }
227
228 @SuppressWarnings("unchecked")
229 @VisibleForTesting
230 @Nullable
231 Map<K, V> delegateOrNull() {
232 if (table instanceof Map) {
233 return (Map<K, V>) table;
234 }
235 return null;
236 }
237
238 Map<K, V> createHashFloodingResistantDelegate(int tableSize) {
239 return new LinkedHashMap<>(tableSize, 1.0f);
240 }
241
242 @SuppressWarnings("unchecked")
243 @VisibleForTesting
244 @CanIgnoreReturnValue
245 Map<K, V> convertToHashFloodingResistantImplementation() {
246 Map<K, V> newDelegate = createHashFloodingResistantDelegate(hashTableMask() + 1);
247 for (int i = firstEntryIndex(); i >= 0; i = getSuccessor(i)) {
248 newDelegate.put((K) keys[i], (V) values[i]);
249 }
250 this.table = newDelegate;
251 this.entries = null;
252 this.keys = null;
253 this.values = null;
254 incrementModCount();
255 return newDelegate;
256 }
257
258 /** Stores the hash table mask as the number of bits needed to represent an index. */
259 private void setHashTableMask(int mask) {
260 int hashTableBits = Integer.SIZE - Integer.numberOfLeadingZeros(mask);
261 metadata =
262 CompactHashing.maskCombine(metadata, hashTableBits, CompactHashing.HASH_TABLE_BITS_MASK);
263 }
264
265 /** Gets the hash table mask using the stored number of hash table bits. */
266 private int hashTableMask() {
267 return (1 << (metadata & CompactHashing.HASH_TABLE_BITS_MASK)) - 1;
268 }
269
270 void incrementModCount() {
271 metadata += CompactHashing.MODIFICATION_COUNT_INCREMENT;
272 }
273
274 /**
275 * Mark an access of the specified entry. Used only in {@code CompactLinkedHashMap} for LRU
276 * ordering.
277 */
278 void accessEntry(int index) {
279 // no-op by default
280 }
281
282 @CanIgnoreReturnValue
283 @Override
284 public @Nullable V put(@Nullable K key, @Nullable V value) {
285 if (needsAllocArrays()) {
286 allocArrays();
287 }
288 @Nullable Map<K, V> delegate = delegateOrNull();
289 if (delegate != null) {
290 return delegate.put(key, value);
291 }
292 int[] entries = this.entries;
293 Object[] keys = this.keys;
294 Object[] values = this.values;
295
296 int newEntryIndex = this.size; // current size, and pointer to the entry to be appended
297 int newSize = newEntryIndex + 1;
298 int hash = smearedHash(key);
299 int mask = hashTableMask();
300 int tableIndex = hash & mask;
301 int next = CompactHashing.tableGet(table, tableIndex);
302 if (next == UNSET) { // uninitialized bucket
303 if (newSize > mask) {
304 // Resize and add new entry
305 mask = resizeTable(mask, CompactHashing.newCapacity(mask), hash, newEntryIndex);
306 } else {
307 CompactHashing.tableSet(table, tableIndex, newEntryIndex + 1);
308 }
309 } else {
310 int entryIndex;
311 int entry;
312 int hashPrefix = CompactHashing.getHashPrefix(hash, mask);
313 int bucketLength = 0;
314 do {
315 entryIndex = next - 1;
316 entry = entries[entryIndex];
317 if (CompactHashing.getHashPrefix(entry, mask) == hashPrefix
318 && Objects.equal(key, keys[entryIndex])) {
319 @SuppressWarnings("unchecked") // known to be a V
320 @Nullable
321 V oldValue = (V) values[entryIndex];
322
323 values[entryIndex] = value;
324 accessEntry(entryIndex);
325 return oldValue;
326 }
327 next = CompactHashing.getNext(entry, mask);
328 bucketLength++;
329 } while (next != UNSET);
330
331 if (bucketLength >= MAX_HASH_BUCKET_LENGTH) {
332 return convertToHashFloodingResistantImplementation().put(key, value);
333 }
334
335 if (newSize > mask) {
336 // Resize and add new entry
337 mask = resizeTable(mask, CompactHashing.newCapacity(mask), hash, newEntryIndex);
338 } else {
339 entries[entryIndex] = CompactHashing.maskCombine(entry, newEntryIndex + 1, mask);
340 }
341 }
342 resizeMeMaybe(newSize);
343 insertEntry(newEntryIndex, key, value, hash, mask);
344 this.size = newSize;
345 incrementModCount();
346 return null;
347 }
348
349 /**
350 * Creates a fresh entry with the specified object at the specified position in the entry arrays.
351 */
352 void insertEntry(int entryIndex, @Nullable K key, @Nullable V value, int hash, int mask) {
353 this.entries[entryIndex] = CompactHashing.maskCombine(hash, UNSET, mask);
354 this.keys[entryIndex] = key;
355 this.values[entryIndex] = value;
356 }
357
358 /** Resizes the entries storage if necessary. */
359 private void resizeMeMaybe(int newSize) {
360 int entriesSize = entries.length;
361 if (newSize > entriesSize) {
362 // 1.5x but round up to nearest odd (this is optimal for memory consumption on Android)
363 int newCapacity =
364 Math.min(CompactHashing.MAX_SIZE, (entriesSize + Math.max(1, entriesSize >>> 1)) | 1);
365 if (newCapacity != entriesSize) {
366 resizeEntries(newCapacity);
367 }
368 }
369 }
370
371 /**
372 * Resizes the internal entries array to the specified capacity, which may be greater or less than
373 * the current capacity.
374 */
375 void resizeEntries(int newCapacity) {
376 this.entries = Arrays.copyOf(entries, newCapacity);
377 this.keys = Arrays.copyOf(keys, newCapacity);
378 this.values = Arrays.copyOf(values, newCapacity);
379 }
380
381 @CanIgnoreReturnValue
382 private int resizeTable(int mask, int newCapacity, int targetHash, int targetEntryIndex) {
383 Object newTable = CompactHashing.createTable(newCapacity);
384 int newMask = newCapacity - 1;
385
386 if (targetEntryIndex != UNSET) {
387 // Add target first; it must be last in the chain because its entry hasn't yet been created
388 CompactHashing.tableSet(newTable, targetHash & newMask, targetEntryIndex + 1);
389 }
390
391 Object table = this.table;
392 int[] entries = this.entries;
393
394 // Loop over current hashtable
395 for (int tableIndex = 0; tableIndex <= mask; tableIndex++) {
396 int next = CompactHashing.tableGet(table, tableIndex);
397 while (next != UNSET) {
398 int entryIndex = next - 1;
399 int entry = entries[entryIndex];
400
401 // Rebuild hash using entry hashPrefix and tableIndex ("hashSuffix")
402 int hash = CompactHashing.getHashPrefix(entry, mask) | tableIndex;
403
404 int newTableIndex = hash & newMask;
405 int newNext = CompactHashing.tableGet(newTable, newTableIndex);
406 CompactHashing.tableSet(newTable, newTableIndex, next);
407 entries[entryIndex] = CompactHashing.maskCombine(hash, newNext, newMask);
408
409 next = CompactHashing.getNext(entry, mask);
410 }
411 }
412
413 this.table = newTable;
414 setHashTableMask(newMask);
415 return newMask;
416 }
417
418 private int indexOf(@Nullable Object key) {
419 if (needsAllocArrays()) {
420 return -1;
421 }
422 int hash = smearedHash(key);
423 int mask = hashTableMask();
424 int next = CompactHashing.tableGet(table, hash & mask);
425 if (next == UNSET) {
426 return -1;
427 }
428 int hashPrefix = CompactHashing.getHashPrefix(hash, mask);
429 do {
430 int entryIndex = next - 1;
431 int entry = entries[entryIndex];
432 if (CompactHashing.getHashPrefix(entry, mask) == hashPrefix
433 && Objects.equal(key, keys[entryIndex])) {
434 return entryIndex;
435 }
436 next = CompactHashing.getNext(entry, mask);
437 } while (next != UNSET);
438 return -1;
439 }
440
441 @Override
442 public boolean containsKey(@Nullable Object key) {
443 @Nullable Map<K, V> delegate = delegateOrNull();
444 return (delegate != null) ? delegate.containsKey(key) : indexOf(key) != -1;
445 }
446
447 @SuppressWarnings("unchecked") // known to be a V
448 @Override
449 public V get(@Nullable Object key) {
450 @Nullable Map<K, V> delegate = delegateOrNull();
451 if (delegate != null) {
452 return delegate.get(key);
453 }
454 int index = indexOf(key);
455 if (index == -1) {
456 return null;
457 }
458 accessEntry(index);
459 return (V) values[index];
460 }
461
462 @CanIgnoreReturnValue
463 @SuppressWarnings("unchecked") // known to be a V
464 @Override
465 public @Nullable V remove(@Nullable Object key) {
466 @Nullable Map<K, V> delegate = delegateOrNull();
467 if (delegate != null) {
468 return delegate.remove(key);
469 }
470 Object oldValue = removeHelper(key);
471 return (oldValue == NOT_FOUND) ? null : (V) oldValue;
472 }
473
474 private @Nullable Object removeHelper(@Nullable Object key) {
475 if (needsAllocArrays()) {
476 return NOT_FOUND;
477 }
478 int mask = hashTableMask();
479 int index =
480 CompactHashing.remove(
481 key, /* value= */ null, mask, table, entries, keys, /* values= */ null);
482 if (index == -1) {
483 return NOT_FOUND;
484 }
485
486 @Nullable Object oldValue = values[index];
487
488 moveLastEntry(index, mask);
489 size--;
490 incrementModCount();
491
492 return oldValue;
493 }
494
495 /**
496 * Moves the last entry in the entry array into {@code dstIndex}, and nulls out its old position.
497 */
498 void moveLastEntry(int dstIndex, int mask) {
499 int srcIndex = size() - 1;
500 if (dstIndex < srcIndex) {
501 // move last entry to deleted spot
502 @Nullable Object key = keys[srcIndex];
503 keys[dstIndex] = key;
504 values[dstIndex] = values[srcIndex];
505 keys[srcIndex] = null;
506 values[srcIndex] = null;
507
508 // move the last entry to the removed spot, just like we moved the element
509 entries[dstIndex] = entries[srcIndex];
510 entries[srcIndex] = 0;
511
512 // also need to update whoever's "next" pointer was pointing to the last entry place
513 int tableIndex = smearedHash(key) & mask;
514 int next = CompactHashing.tableGet(table, tableIndex);
515 int srcNext = srcIndex + 1;
516 if (next == srcNext) {
517 // we need to update the root pointer
518 CompactHashing.tableSet(table, tableIndex, dstIndex + 1);
519 } else {
520 // we need to update a pointer in an entry
521 int entryIndex;
522 int entry;
523 do {
524 entryIndex = next - 1;
525 entry = entries[entryIndex];
526 next = CompactHashing.getNext(entry, mask);
527 } while (next != srcNext);
528 // here, entries[entryIndex] points to the old entry location; update it
529 entries[entryIndex] = CompactHashing.maskCombine(entry, dstIndex + 1, mask);
530 }
531 } else {
532 keys[dstIndex] = null;
533 values[dstIndex] = null;
534 entries[dstIndex] = 0;
535 }
536 }
537
538 int firstEntryIndex() {
539 return isEmpty() ? -1 : 0;
540 }
541
542 int getSuccessor(int entryIndex) {
543 return (entryIndex + 1 < size) ? entryIndex + 1 : -1;
544 }
545
546 /**
547 * Updates the index an iterator is pointing to after a call to remove: returns the index of the
548 * entry that should be looked at after a removal on indexRemoved, with indexBeforeRemove as the
549 * index that *was* the next entry that would be looked at.
550 */
551 int adjustAfterRemove(int indexBeforeRemove, @SuppressWarnings("unused") int indexRemoved) {
552 return indexBeforeRemove - 1;
553 }
554
555 private abstract class Itr<T> implements Iterator<T> {
556 int expectedMetadata = metadata;
557 int currentIndex = firstEntryIndex();
558 int indexToRemove = -1;
559
560 @Override
561 public boolean hasNext() {
562 return currentIndex >= 0;
563 }
564
565 abstract T getOutput(int entry);
566
567 @Override
568 public T next() {
569 checkForConcurrentModification();
570 if (!hasNext()) {
571 throw new NoSuchElementException();
572 }
573 indexToRemove = currentIndex;
574 T result = getOutput(currentIndex);
575 currentIndex = getSuccessor(currentIndex);
576 return result;
577 }
578
579 @Override
580 public void remove() {
581 checkForConcurrentModification();
582 checkRemove(indexToRemove >= 0);
583 incrementExpectedModCount();
584 CompactHashMap.this.remove(keys[indexToRemove]);
585 currentIndex = adjustAfterRemove(currentIndex, indexToRemove);
586 indexToRemove = -1;
587 }
588
589 void incrementExpectedModCount() {
590 expectedMetadata += CompactHashing.MODIFICATION_COUNT_INCREMENT;
591 }
592
593 private void checkForConcurrentModification() {
594 if (metadata != expectedMetadata) {
595 throw new ConcurrentModificationException();
596 }
597 }
598 }
599
600 @SuppressWarnings("unchecked") // known to be Ks and Vs
601 @Override
602 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
603 checkNotNull(function);
604 @Nullable Map<K, V> delegate = delegateOrNull();
605 if (delegate != null) {
606 delegate.replaceAll(function);
607 } else {
608 for (int i = 0; i < size; i++) {
609 values[i] = function.apply((K) keys[i], (V) values[i]);
610 }
611 }
612 }
613
614 private transient @Nullable Set<K> keySetView;
615
616 @Override
617 public Set<K> keySet() {
618 return (keySetView == null) ? keySetView = createKeySet() : keySetView;
619 }
620
621 Set<K> createKeySet() {
622 return new KeySetView();
623 }
624
625 @WeakOuter
626 class KeySetView extends Maps.KeySet<K, V> {
627 KeySetView() {
628 super(CompactHashMap.this);
629 }
630
631 @Override
632 public Object[] toArray() {
633 if (needsAllocArrays()) {
634 return new Object[0];
635 }
636 @Nullable Map<K, V> delegate = delegateOrNull();
637 return (delegate != null)
638 ? delegate.keySet().toArray()
639 : ObjectArrays.copyAsObjectArray(keys, 0, size);
640 }
641
642 @Override
643 public <T> T[] toArray(T[] a) {
644 if (needsAllocArrays()) {
645 if (a.length > 0) {
646 a[0] = null;
647 }
648 return a;
649 }
650 @Nullable Map<K, V> delegate = delegateOrNull();
651 return (delegate != null)
652 ? delegate.keySet().toArray(a)
653 : ObjectArrays.toArrayImpl(keys, 0, size, a);
654 }
655
656 @Override
657 public boolean remove(@Nullable Object o) {
658 @Nullable Map<K, V> delegate = delegateOrNull();
659 return (delegate != null)
660 ? delegate.keySet().remove(o)
661 : CompactHashMap.this.removeHelper(o) != NOT_FOUND;
662 }
663
664 @Override
665 public Iterator<K> iterator() {
666 return keySetIterator();
667 }
668
669 @Override
670 public Spliterator<K> spliterator() {
671 if (needsAllocArrays()) {
672 return Spliterators.spliterator(new Object[0], Spliterator.DISTINCT | Spliterator.ORDERED);
673 }
674 @Nullable Map<K, V> delegate = delegateOrNull();
675 return (delegate != null)
676 ? delegate.keySet().spliterator()
677 : Spliterators.spliterator(keys, 0, size, Spliterator.DISTINCT | Spliterator.ORDERED);
678 }
679
680 @SuppressWarnings("unchecked") // known to be Ks
681 @Override
682 public void forEach(Consumer<? super K> action) {
683 checkNotNull(action);
684 @Nullable Map<K, V> delegate = delegateOrNull();
685 if (delegate != null) {
686 delegate.keySet().forEach(action);
687 } else {
688 for (int i = firstEntryIndex(); i >= 0; i = getSuccessor(i)) {
689 action.accept((K) keys[i]);
690 }
691 }
692 }
693 }
694
695 Iterator<K> keySetIterator() {
696 @Nullable Map<K, V> delegate = delegateOrNull();
697 if (delegate != null) {
698 return delegate.keySet().iterator();
699 }
700 return new Itr<K>() {
701 @SuppressWarnings("unchecked") // known to be a K
702 @Override
703 K getOutput(int entry) {
704 return (K) keys[entry];
705 }
706 };
707 }
708
709 @SuppressWarnings("unchecked") // known to be Ks and Vs
710 @Override
711 public void forEach(BiConsumer<? super K, ? super V> action) {
712 checkNotNull(action);
713 @Nullable Map<K, V> delegate = delegateOrNull();
714 if (delegate != null) {
715 delegate.forEach(action);
716 } else {
717 for (int i = firstEntryIndex(); i >= 0; i = getSuccessor(i)) {
718 action.accept((K) keys[i], (V) values[i]);
719 }
720 }
721 }
722
723 private transient @Nullable Set<Entry<K, V>> entrySetView;
724
725 @Override
726 public Set<Entry<K, V>> entrySet() {
727 return (entrySetView == null) ? entrySetView = createEntrySet() : entrySetView;
728 }
729
730 Set<Entry<K, V>> createEntrySet() {
731 return new EntrySetView();
732 }
733
734 @WeakOuter
735 class EntrySetView extends Maps.EntrySet<K, V> {
736 @Override
737 Map<K, V> map() {
738 return CompactHashMap.this;
739 }
740
741 @Override
742 public Iterator<Entry<K, V>> iterator() {
743 return entrySetIterator();
744 }
745
746 @Override
747 public Spliterator<Entry<K, V>> spliterator() {
748 @Nullable Map<K, V> delegate = delegateOrNull();
749 return (delegate != null)
750 ? delegate.entrySet().spliterator()
751 : CollectSpliterators.indexed(
752 size, Spliterator.DISTINCT | Spliterator.ORDERED, MapEntry::new);
753 }
754
755 @Override
756 public boolean contains(@Nullable Object o) {
757 @Nullable Map<K, V> delegate = delegateOrNull();
758 if (delegate != null) {
759 return delegate.entrySet().contains(o);
760 } else if (o instanceof Entry) {
761 Entry<?, ?> entry = (Entry<?, ?>) o;
762 int index = indexOf(entry.getKey());
763 return index != -1 && Objects.equal(values[index], entry.getValue());
764 }
765 return false;
766 }
767
768 @Override
769 public boolean remove(@Nullable Object o) {
770 @Nullable Map<K, V> delegate = delegateOrNull();
771 if (delegate != null) {
772 return delegate.entrySet().remove(o);
773 } else if (o instanceof Entry) {
774 Entry<?, ?> entry = (Entry<?, ?>) o;
775 if (needsAllocArrays()) {
776 return false;
777 }
778 int mask = hashTableMask();
779 int index =
780 CompactHashing.remove(
781 entry.getKey(), entry.getValue(), mask, table, entries, keys, values);
782 if (index == -1) {
783 return false;
784 }
785
786 moveLastEntry(index, mask);
787 size--;
788 incrementModCount();
789
790 return true;
791 }
792 return false;
793 }
794 }
795
796 Iterator<Entry<K, V>> entrySetIterator() {
797 @Nullable Map<K, V> delegate = delegateOrNull();
798 if (delegate != null) {
799 return delegate.entrySet().iterator();
800 }
801 return new Itr<Entry<K, V>>() {
802 @Override
803 Entry<K, V> getOutput(int entry) {
804 return new MapEntry(entry);
805 }
806 };
807 }
808
809 final class MapEntry extends AbstractMapEntry<K, V> {
810 private final @Nullable K key;
811
812 private int lastKnownIndex;
813
814 @SuppressWarnings("unchecked") // known to be a K
815 MapEntry(int index) {
816 this.key = (K) keys[index];
817 this.lastKnownIndex = index;
818 }
819
820 @Nullable
821 @Override
822 public K getKey() {
823 return key;
824 }
825
826 private void updateLastKnownIndex() {
827 if (lastKnownIndex == -1
828 || lastKnownIndex >= size()
829 || !Objects.equal(key, keys[lastKnownIndex])) {
830 lastKnownIndex = indexOf(key);
831 }
832 }
833
834 @SuppressWarnings("unchecked") // known to be a V
835 @Override
836 public @Nullable V getValue() {
837 @Nullable Map<K, V> delegate = delegateOrNull();
838 if (delegate != null) {
839 return delegate.get(key);
840 }
841 updateLastKnownIndex();
842 return (lastKnownIndex == -1) ? null : (V) values[lastKnownIndex];
843 }
844
845 @SuppressWarnings("unchecked") // known to be a V
846 @Override
847 public V setValue(V value) {
848 @Nullable Map<K, V> delegate = delegateOrNull();
849 if (delegate != null) {
850 return delegate.put(key, value);
851 }
852 updateLastKnownIndex();
853 if (lastKnownIndex == -1) {
854 put(key, value);
855 return null;
856 } else {
857 V old = (V) values[lastKnownIndex];
858 values[lastKnownIndex] = value;
859 return old;
860 }
861 }
862 }
863
864 @Override
865 public int size() {
866 @Nullable Map<K, V> delegate = delegateOrNull();
867 return (delegate != null) ? delegate.size() : size;
868 }
869
870 @Override
871 public boolean isEmpty() {
872 return size() == 0;
873 }
874
875 @Override
876 public boolean containsValue(@Nullable Object value) {
877 @Nullable Map<K, V> delegate = delegateOrNull();
878 if (delegate != null) {
879 return delegate.containsValue(value);
880 }
881 for (int i = 0; i < size; i++) {
882 if (Objects.equal(value, values[i])) {
883 return true;
884 }
885 }
886 return false;
887 }
888
889 private transient @Nullable Collection<V> valuesView;
890
891 @Override
892 public Collection<V> values() {
893 return (valuesView == null) ? valuesView = createValues() : valuesView;
894 }
895
896 Collection<V> createValues() {
897 return new ValuesView();
898 }
899
900 @WeakOuter
901 class ValuesView extends Maps.Values<K, V> {
902 ValuesView() {
903 super(CompactHashMap.this);
904 }
905
906 @Override
907 public Iterator<V> iterator() {
908 return valuesIterator();
909 }
910
911 @SuppressWarnings("unchecked") // known to be Vs
912 @Override
913 public void forEach(Consumer<? super V> action) {
914 checkNotNull(action);
915 @Nullable Map<K, V> delegate = delegateOrNull();
916 if (delegate != null) {
917 delegate.values().forEach(action);
918 } else {
919 for (int i = firstEntryIndex(); i >= 0; i = getSuccessor(i)) {
920 action.accept((V) values[i]);
921 }
922 }
923 }
924
925 @Override
926 public Spliterator<V> spliterator() {
927 if (needsAllocArrays()) {
928 return Spliterators.spliterator(new Object[0], Spliterator.ORDERED);
929 }
930 @Nullable Map<K, V> delegate = delegateOrNull();
931 return (delegate != null)
932 ? delegate.values().spliterator()
933 : Spliterators.spliterator(values, 0, size, Spliterator.ORDERED);
934 }
935
936 @Override
937 public Object[] toArray() {
938 if (needsAllocArrays()) {
939 return new Object[0];
940 }
941 @Nullable Map<K, V> delegate = delegateOrNull();
942 return (delegate != null)
943 ? delegate.values().toArray()
944 : ObjectArrays.copyAsObjectArray(values, 0, size);
945 }
946
947 @Override
948 public <T> T[] toArray(T[] a) {
949 if (needsAllocArrays()) {
950 if (a.length > 0) {
951 a[0] = null;
952 }
953 return a;
954 }
955 @Nullable Map<K, V> delegate = delegateOrNull();
956 return (delegate != null)
957 ? delegate.values().toArray(a)
958 : ObjectArrays.toArrayImpl(values, 0, size, a);
959 }
960 }
961
962 Iterator<V> valuesIterator() {
963 @Nullable Map<K, V> delegate = delegateOrNull();
964 if (delegate != null) {
965 return delegate.values().iterator();
966 }
967 return new Itr<V>() {
968 @SuppressWarnings("unchecked") // known to be a V
969 @Override
970 V getOutput(int entry) {
971 return (V) values[entry];
972 }
973 };
974 }
975
976 /**
977 * Ensures that this {@code CompactHashMap} has the smallest representation in memory, given its
978 * current size.
979 */
980 public void trimToSize() {
981 if (needsAllocArrays()) {
982 return;
983 }
984 @Nullable Map<K, V> delegate = delegateOrNull();
985 if (delegate != null) {
986 Map<K, V> newDelegate = createHashFloodingResistantDelegate(size());
987 newDelegate.putAll(delegate);
988 this.table = newDelegate;
989 return;
990 }
991 int size = this.size;
992 if (size < entries.length) {
993 resizeEntries(size);
994 }
995 int minimumTableSize = CompactHashing.tableSize(size);
996 int mask = hashTableMask();
997 if (minimumTableSize < mask) { // smaller table size will always be less than current mask
998 resizeTable(mask, minimumTableSize, UNSET, UNSET);
999 }
1000 }
1001
1002 @Override
1003 public void clear() {
1004 if (needsAllocArrays()) {
1005 return;
1006 }
1007 incrementModCount();
1008 @Nullable Map<K, V> delegate = delegateOrNull();
1009 if (delegate != null) {
1010 metadata =
1011 Ints.constrainToRange(size(), CompactHashing.DEFAULT_SIZE, CompactHashing.MAX_SIZE);
1012 delegate.clear(); // invalidate any iterators left over!
1013 table = null;
1014 size = 0;
1015 } else {
1016 Arrays.fill(keys, 0, size, null);
1017 Arrays.fill(values, 0, size, null);
1018 CompactHashing.tableClear(table);
1019 Arrays.fill(entries, 0, size, 0);
1020 this.size = 0;
1021 }
1022 }
1023
1024 private void writeObject(ObjectOutputStream stream) throws IOException {
1025 stream.defaultWriteObject();
1026 stream.writeInt(size());
1027 Iterator<Entry<K, V>> entryIterator = entrySetIterator();
1028 while (entryIterator.hasNext()) {
1029 Entry<K, V> e = entryIterator.next();
1030 stream.writeObject(e.getKey());
1031 stream.writeObject(e.getValue());
1032 }
1033 }
1034
1035 @SuppressWarnings("unchecked")
1036 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
1037 stream.defaultReadObject();
1038 int elementCount = stream.readInt();
1039 if (elementCount < 0) {
1040 throw new InvalidObjectException("Invalid size: " + elementCount);
1041 }
1042 init(elementCount);
1043 for (int i = 0; i < elementCount; i++) {
1044 K key = (K) stream.readObject();
1045 V value = (V) stream.readObject();
1046 put(key, value);
1047 }
1048 }
1049 }