1 /*
2 * Copyright (C) 2007 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.checkArgument;
20 import static com.google.common.base.Preconditions.checkNotNull;
21 import static com.google.common.collect.CollectPreconditions.checkNonnegative;
22 import static java.util.Objects.requireNonNull;
23
24 import com.google.common.annotations.Beta;
25 import com.google.common.annotations.GwtCompatible;
26 import com.google.common.annotations.VisibleForTesting;
27 import com.google.common.math.IntMath;
28 import com.google.common.primitives.Ints;
29 import com.google.errorprone.annotations.CanIgnoreReturnValue;
30 import com.google.errorprone.annotations.concurrent.LazyInit;
31 import com.google.j2objc.annotations.RetainedWith;
32 import java.io.Serializable;
33 import java.math.RoundingMode;
34 import java.util.Arrays;
35 import java.util.Collection;
36 import java.util.Collections;
37 import java.util.EnumSet;
38 import java.util.Iterator;
39 import java.util.Set;
40 import java.util.SortedSet;
41 import java.util.Spliterator;
42 import java.util.function.Consumer;
43 import java.util.stream.Collector;
44 import javax.annotation.CheckForNull;
45 import org.checkerframework.checker.nullness.qual.Nullable;
46
47 /**
48 * A {@link Set} whose contents will never change, with many other important properties detailed at
49 * {@link ImmutableCollection}.
50 *
51 * @since 2.0
52 */
53 @GwtCompatible(serializable = true, emulated = true)
54 @SuppressWarnings("serial") // we're overriding default serialization
55 @ElementTypesAreNonnullByDefault
56 public abstract class ImmutableSet<E> extends ImmutableCollection<E> implements Set<E> {
57 static final int SPLITERATOR_CHARACTERISTICS =
58 ImmutableCollection.SPLITERATOR_CHARACTERISTICS | Spliterator.DISTINCT;
59
60 /**
61 * Returns a {@code Collector} that accumulates the input elements into a new {@code
62 * ImmutableSet}. Elements appear in the resulting set in the encounter order of the stream; if
63 * the stream contains duplicates (according to {@link Object#equals(Object)}), only the first
64 * duplicate in encounter order will appear in the result.
65 *
66 * @since 21.0
67 */
68 public static <E> Collector<E, ?, ImmutableSet<E>> toImmutableSet() {
69 return CollectCollectors.toImmutableSet();
70 }
71
72 /**
73 * Returns the empty immutable set. Preferred over {@link Collections#emptySet} for code
74 * consistency, and because the return type conveys the immutability guarantee.
75 *
76 * <p><b>Performance note:</b> the instance returned is a singleton.
77 */
78 @SuppressWarnings({"unchecked"}) // fully variant implementation (never actually produces any Es)
79 public static <E> ImmutableSet<E> of() {
80 return (ImmutableSet<E>) RegularImmutableSet.EMPTY;
81 }
82
83 /**
84 * Returns an immutable set containing {@code element}. Preferred over {@link
85 * Collections#singleton} for code consistency, {@code null} rejection, and because the return
86 * type conveys the immutability guarantee.
87 */
88 public static <E> ImmutableSet<E> of(E element) {
89 return new SingletonImmutableSet<E>(element);
90 }
91
92 /**
93 * Returns an immutable set containing the given elements, minus duplicates, in the order each was
94 * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except
95 * the first are ignored.
96 */
97 public static <E> ImmutableSet<E> of(E e1, E e2) {
98 return construct(2, 2, e1, e2);
99 }
100
101 /**
102 * Returns an immutable set containing the given elements, minus duplicates, in the order each was
103 * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except
104 * the first are ignored.
105 */
106 public static <E> ImmutableSet<E> of(E e1, E e2, E e3) {
107 return construct(3, 3, e1, e2, e3);
108 }
109
110 /**
111 * Returns an immutable set containing the given elements, minus duplicates, in the order each was
112 * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except
113 * the first are ignored.
114 */
115 public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4) {
116 return construct(4, 4, e1, e2, e3, e4);
117 }
118
119 /**
120 * Returns an immutable set containing the given elements, minus duplicates, in the order each was
121 * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except
122 * the first are ignored.
123 */
124 public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5) {
125 return construct(5, 5, e1, e2, e3, e4, e5);
126 }
127
128 /**
129 * Returns an immutable set containing the given elements, minus duplicates, in the order each was
130 * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except
131 * the first are ignored.
132 *
133 * <p>The array {@code others} must not be longer than {@code Integer.MAX_VALUE - 6}.
134 *
135 * @since 3.0 (source-compatible since 2.0)
136 */
137 @SafeVarargs // For Eclipse. For internal javac we have disabled this pointless type of warning.
138 public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E... others) {
139 checkArgument(
140 others.length <= Integer.MAX_VALUE - 6, "the total number of elements must fit in an int");
141 final int paramCount = 6;
142 Object[] elements = new Object[paramCount + others.length];
143 elements[0] = e1;
144 elements[1] = e2;
145 elements[2] = e3;
146 elements[3] = e4;
147 elements[4] = e5;
148 elements[5] = e6;
149 System.arraycopy(others, 0, elements, paramCount, others.length);
150 return construct(elements.length, elements.length, elements);
151 }
152
153 /**
154 * Constructs an {@code ImmutableSet} from the first {@code n} elements of the specified array,
155 * which we have no particular reason to believe does or does not contain duplicates. If {@code k}
156 * is the size of the returned {@code ImmutableSet}, then the unique elements of {@code elements}
157 * will be in the first {@code k} positions, and {@code elements[i] == null} for {@code k <= i <
158 * n}.
159 *
160 * <p>This may modify {@code elements}. Additionally, if {@code n == elements.length} and {@code
161 * elements} contains no duplicates, {@code elements} may be used without copying in the returned
162 * {@code ImmutableSet}, in which case the caller must not modify it.
163 *
164 * <p>{@code elements} may contain only values of type {@code E}.
165 *
166 * @throws NullPointerException if any of the first {@code n} elements of {@code elements} is null
167 */
168 private static <E> ImmutableSet<E> constructUnknownDuplication(int n, Object... elements) {
169 // Guess the size is "halfway between" all duplicates and no duplicates, on a log scale.
170 return construct(
171 n,
172 Math.max(
173 ImmutableCollection.Builder.DEFAULT_INITIAL_CAPACITY,
174 IntMath.sqrt(n, RoundingMode.CEILING)),
175 elements);
176 }
177
178 /**
179 * Constructs an {@code ImmutableSet} from the first {@code n} elements of the specified array. If
180 * {@code k} is the size of the returned {@code ImmutableSet}, then the unique elements of {@code
181 * elements} will be in the first {@code k} positions, and {@code elements[i] == null} for {@code
182 * k <= i < n}.
183 *
184 * <p>This may modify {@code elements}. Additionally, if {@code n == elements.length} and {@code
185 * elements} contains no duplicates, {@code elements} may be used without copying in the returned
186 * {@code ImmutableSet}, in which case it may no longer be modified.
187 *
188 * <p>{@code elements} may contain only values of type {@code E}.
189 *
190 * @throws NullPointerException if any of the first {@code n} elements of {@code elements} is null
191 */
192 private static <E> ImmutableSet<E> construct(int n, int expectedSize, Object... elements) {
193 switch (n) {
194 case 0:
195 return of();
196 case 1:
197 @SuppressWarnings("unchecked") // safe; elements contains only E's
198 E elem = (E) elements[0];
199 return of(elem);
200 default:
201 SetBuilderImpl<E> builder = new RegularSetBuilderImpl<E>(expectedSize);
202 for (int i = 0; i < n; i++) {
203 @SuppressWarnings("unchecked")
204 E e = (E) checkNotNull(elements[i]);
205 builder = builder.add(e);
206 }
207 return builder.review().build();
208 }
209 }
210
211 /**
212 * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order
213 * each appears first in the source collection.
214 *
215 * <p><b>Performance note:</b> This method will sometimes recognize that the actual copy operation
216 * is unnecessary; for example, {@code copyOf(copyOf(anArrayList))} will copy the data only once.
217 * This reduces the expense of habitually making defensive copies at API boundaries. However, the
218 * precise conditions for skipping the copy operation are undefined.
219 *
220 * @throws NullPointerException if any of {@code elements} is null
221 * @since 7.0 (source-compatible since 2.0)
222 */
223 public static <E> ImmutableSet<E> copyOf(Collection<? extends E> elements) {
224 /*
225 * TODO(lowasser): consider checking for ImmutableAsList here
226 * TODO(lowasser): consider checking for Multiset here
227 */
228 // Don't refer to ImmutableSortedSet by name so it won't pull in all that code
229 if (elements instanceof ImmutableSet && !(elements instanceof SortedSet)) {
230 @SuppressWarnings("unchecked") // all supported methods are covariant
231 ImmutableSet<E> set = (ImmutableSet<E>) elements;
232 if (!set.isPartialView()) {
233 return set;
234 }
235 } else if (elements instanceof EnumSet) {
236 return copyOfEnumSet((EnumSet) elements);
237 }
238 Object[] array = elements.toArray();
239 if (elements instanceof Set) {
240 // assume probably no duplicates (though it might be using different equality semantics)
241 return construct(array.length, array.length, array);
242 } else {
243 return constructUnknownDuplication(array.length, array);
244 }
245 }
246
247 /**
248 * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order
249 * each appears first in the source iterable. This method iterates over {@code elements} only
250 * once.
251 *
252 * <p><b>Performance note:</b> This method will sometimes recognize that the actual copy operation
253 * is unnecessary; for example, {@code copyOf(copyOf(anArrayList))} should copy the data only
254 * once. This reduces the expense of habitually making defensive copies at API boundaries.
255 * However, the precise conditions for skipping the copy operation are undefined.
256 *
257 * @throws NullPointerException if any of {@code elements} is null
258 */
259 public static <E> ImmutableSet<E> copyOf(Iterable<? extends E> elements) {
260 return (elements instanceof Collection)
261 ? copyOf((Collection<? extends E>) elements)
262 : copyOf(elements.iterator());
263 }
264
265 /**
266 * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order
267 * each appears first in the source iterator.
268 *
269 * @throws NullPointerException if any of {@code elements} is null
270 */
271 public static <E> ImmutableSet<E> copyOf(Iterator<? extends E> elements) {
272 // We special-case for 0 or 1 elements, but anything further is madness.
273 if (!elements.hasNext()) {
274 return of();
275 }
276 E first = elements.next();
277 if (!elements.hasNext()) {
278 return of(first);
279 } else {
280 return new ImmutableSet.Builder<E>().add(first).addAll(elements).build();
281 }
282 }
283
284 /**
285 * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order
286 * each appears first in the source array.
287 *
288 * @throws NullPointerException if any of {@code elements} is null
289 * @since 3.0
290 */
291 public static <E> ImmutableSet<E> copyOf(E[] elements) {
292 switch (elements.length) {
293 case 0:
294 return of();
295 case 1:
296 return of(elements[0]);
297 default:
298 return constructUnknownDuplication(elements.length, elements.clone());
299 }
300 }
301
302 @SuppressWarnings("rawtypes") // necessary to compile against Java 8
303 private static ImmutableSet copyOfEnumSet(EnumSet enumSet) {
304 return ImmutableEnumSet.asImmutable(EnumSet.copyOf(enumSet));
305 }
306
307 ImmutableSet() {}
308
309 /** Returns {@code true} if the {@code hashCode()} method runs quickly. */
310 boolean isHashCodeFast() {
311 return false;
312 }
313
314 @Override
315 public boolean equals(@CheckForNull Object object) {
316 if (object == this) {
317 return true;
318 }
319 if (object instanceof ImmutableSet
320 && isHashCodeFast()
321 && ((ImmutableSet<?>) object).isHashCodeFast()
322 && hashCode() != object.hashCode()) {
323 return false;
324 }
325 return Sets.equalsImpl(this, object);
326 }
327
328 @Override
329 public int hashCode() {
330 return Sets.hashCodeImpl(this);
331 }
332
333 // This declaration is needed to make Set.iterator() and
334 // ImmutableCollection.iterator() consistent.
335 @Override
336 public abstract UnmodifiableIterator<E> iterator();
337
338 @LazyInit @RetainedWith @CheckForNull private transient ImmutableList<E> asList;
339
340 @Override
341 public ImmutableList<E> asList() {
342 ImmutableList<E> result = asList;
343 return (result == null) ? asList = createAsList() : result;
344 }
345
346 ImmutableList<E> createAsList() {
347 return new RegularImmutableAsList<E>(this, toArray());
348 }
349
350 abstract static class Indexed<E> extends ImmutableSet<E> {
351 abstract E get(int index);
352
353 @Override
354 public UnmodifiableIterator<E> iterator() {
355 return asList().iterator();
356 }
357
358 @Override
359 public Spliterator<E> spliterator() {
360 return CollectSpliterators.indexed(size(), SPLITERATOR_CHARACTERISTICS, this::get);
361 }
362
363 @Override
364 public void forEach(Consumer<? super E> consumer) {
365 checkNotNull(consumer);
366 int n = size();
367 for (int i = 0; i < n; i++) {
368 consumer.accept(get(i));
369 }
370 }
371
372 @Override
373 int copyIntoArray(@Nullable Object[] dst, int offset) {
374 return asList().copyIntoArray(dst, offset);
375 }
376
377 @Override
378 ImmutableList<E> createAsList() {
379 return new ImmutableAsList<E>() {
380 @Override
381 public E get(int index) {
382 return Indexed.this.get(index);
383 }
384
385 @Override
386 Indexed<E> delegateCollection() {
387 return Indexed.this;
388 }
389 };
390 }
391 }
392
393 /*
394 * This class is used to serialize all ImmutableSet instances, except for
395 * ImmutableEnumSet/ImmutableSortedSet, regardless of implementation type. It
396 * captures their "logical contents" and they are reconstructed using public
397 * static factories. This is necessary to ensure that the existence of a
398 * particular implementation type is an implementation detail.
399 */
400 private static class SerializedForm implements Serializable {
401 final Object[] elements;
402
403 SerializedForm(Object[] elements) {
404 this.elements = elements;
405 }
406
407 Object readResolve() {
408 return copyOf(elements);
409 }
410
411 private static final long serialVersionUID = 0;
412 }
413
414 @Override
415 Object writeReplace() {
416 return new SerializedForm(toArray());
417 }
418
419 /**
420 * Returns a new builder. The generated builder is equivalent to the builder created by the {@link
421 * Builder} constructor.
422 */
423 public static <E> Builder<E> builder() {
424 return new Builder<E>();
425 }
426
427 /**
428 * Returns a new builder, expecting the specified number of distinct elements to be added.
429 *
430 * <p>If {@code expectedSize} is exactly the number of distinct elements added to the builder
431 * before {@link Builder#build} is called, the builder is likely to perform better than an unsized
432 * {@link #builder()} would have.
433 *
434 * <p>It is not specified if any performance benefits apply if {@code expectedSize} is close to,
435 * but not exactly, the number of distinct elements added to the builder.
436 *
437 * @since 23.1
438 */
439 @Beta
440 public static <E> Builder<E> builderWithExpectedSize(int expectedSize) {
441 checkNonnegative(expectedSize, "expectedSize");
442 return new Builder<E>(expectedSize);
443 }
444
445 /**
446 * A builder for creating {@code ImmutableSet} instances. Example:
447 *
448 * <pre>{@code
449 * static final ImmutableSet<Color> GOOGLE_COLORS =
450 * ImmutableSet.<Color>builder()
451 * .addAll(WEBSAFE_COLORS)
452 * .add(new Color(0, 191, 255))
453 * .build();
454 * }</pre>
455 *
456 * <p>Elements appear in the resulting set in the same order they were first added to the builder.
457 *
458 * <p>Building does not change the state of the builder, so it is still possible to add more
459 * elements and to build again.
460 *
461 * @since 2.0
462 */
463 public static class Builder<E> extends ImmutableCollection.Builder<E> {
464 /*
465 * `impl` is null only for instances of the subclass, ImmutableSortedSet.Builder. That subclass
466 * overrides all the methods that access it here. Thus, all the methods here can safely assume
467 * that this field is non-null.
468 */
469 @CheckForNull private SetBuilderImpl<E> impl;
470 boolean forceCopy;
471
472 public Builder() {
473 this(DEFAULT_INITIAL_CAPACITY);
474 }
475
476 Builder(int capacity) {
477 impl = new RegularSetBuilderImpl<E>(capacity);
478 }
479
480 Builder(@SuppressWarnings("unused") boolean subclass) {
481 this.impl = null; // unused
482 }
483
484 @VisibleForTesting
485 void forceJdk() {
486 requireNonNull(impl); // see the comment on the field
487 this.impl = new JdkBackedSetBuilderImpl<E>(impl);
488 }
489
490 final void copyIfNecessary() {
491 if (forceCopy) {
492 copy();
493 forceCopy = false;
494 }
495 }
496
497 void copy() {
498 requireNonNull(impl); // see the comment on the field
499 impl = impl.copy();
500 }
501
502 @Override
503 @CanIgnoreReturnValue
504 public Builder<E> add(E element) {
505 requireNonNull(impl); // see the comment on the field
506 checkNotNull(element);
507 copyIfNecessary();
508 impl = impl.add(element);
509 return this;
510 }
511
512 @Override
513 @CanIgnoreReturnValue
514 public Builder<E> add(E... elements) {
515 super.add(elements);
516 return this;
517 }
518
519 /**
520 * Adds each element of {@code elements} to the {@code ImmutableSet}, ignoring duplicate
521 * elements (only the first duplicate element is added).
522 *
523 * @param elements the elements to add
524 * @return this {@code Builder} object
525 * @throws NullPointerException if {@code elements} is null or contains a null element
526 */
527 @Override
528 @CanIgnoreReturnValue
529 public Builder<E> addAll(Iterable<? extends E> elements) {
530 super.addAll(elements);
531 return this;
532 }
533
534 @Override
535 @CanIgnoreReturnValue
536 public Builder<E> addAll(Iterator<? extends E> elements) {
537 super.addAll(elements);
538 return this;
539 }
540
541 Builder<E> combine(Builder<E> other) {
542 requireNonNull(impl);
543 requireNonNull(other.impl);
544 /*
545 * For discussion of requireNonNull, see the comment on the field.
546 *
547 * (And I don't believe there's any situation in which we call x.combine(y) when x is a plain
548 * ImmutableSet.Builder but y is an ImmutableSortedSet.Builder (or vice versa). Certainly
549 * ImmutableSortedSet.Builder.combine() is written as if its argument will never be a plain
550 * ImmutableSet.Builder: It casts immediately to ImmutableSortedSet.Builder.)
551 */
552 copyIfNecessary();
553 this.impl = this.impl.combine(other.impl);
554 return this;
555 }
556
557 @Override
558 public ImmutableSet<E> build() {
559 requireNonNull(impl); // see the comment on the field
560 forceCopy = true;
561 impl = impl.review();
562 return impl.build();
563 }
564 }
565
566 /** Swappable internal implementation of an ImmutableSet.Builder. */
567 private abstract static class SetBuilderImpl<E> {
568 // The first `distinct` elements are non-null.
569 @Nullable E[] dedupedElements;
570 int distinct;
571
572 @SuppressWarnings("unchecked")
573 SetBuilderImpl(int expectedCapacity) {
574 this.dedupedElements = (@Nullable E[]) new @Nullable Object[expectedCapacity];
575 this.distinct = 0;
576 }
577
578 /** Initializes this SetBuilderImpl with a copy of the deduped elements array from toCopy. */
579 SetBuilderImpl(SetBuilderImpl<E> toCopy) {
580 this.dedupedElements = Arrays.copyOf(toCopy.dedupedElements, toCopy.dedupedElements.length);
581 this.distinct = toCopy.distinct;
582 }
583
584 /**
585 * Resizes internal data structures if necessary to store the specified number of distinct
586 * elements.
587 */
588 private void ensureCapacity(int minCapacity) {
589 if (minCapacity > dedupedElements.length) {
590 int newCapacity =
591 ImmutableCollection.Builder.expandedCapacity(dedupedElements.length, minCapacity);
592 dedupedElements = Arrays.copyOf(dedupedElements, newCapacity);
593 }
594 }
595
596 /** Adds e to the insertion-order array of deduplicated elements. Calls ensureCapacity. */
597 final void addDedupedElement(E e) {
598 ensureCapacity(distinct + 1);
599 dedupedElements[distinct++] = e;
600 }
601
602 /**
603 * Adds e to this SetBuilderImpl, returning the updated result. Only use the returned
604 * SetBuilderImpl, since we may switch implementations if e.g. hash flooding is detected.
605 */
606 abstract SetBuilderImpl<E> add(E e);
607
608 /** Adds all the elements from the specified SetBuilderImpl to this SetBuilderImpl. */
609 final SetBuilderImpl<E> combine(SetBuilderImpl<E> other) {
610 SetBuilderImpl<E> result = this;
611 for (int i = 0; i < other.distinct; i++) {
612 /*
613 * requireNonNull is safe because we ensure that the first `distinct` elements have been
614 * populated.
615 */
616 result = result.add(requireNonNull(other.dedupedElements[i]));
617 }
618 return result;
619 }
620
621 /**
622 * Creates a new copy of this SetBuilderImpl. Modifications to that SetBuilderImpl will not
623 * affect this SetBuilderImpl or sets constructed from this SetBuilderImpl via build().
624 */
625 abstract SetBuilderImpl<E> copy();
626
627 /**
628 * Call this before build(). Does a final check on the internal data structures, e.g. shrinking
629 * unnecessarily large structures or detecting previously unnoticed hash flooding.
630 */
631 SetBuilderImpl<E> review() {
632 return this;
633 }
634
635 abstract ImmutableSet<E> build();
636 }
637
638 // We use power-of-2 tables, and this is the highest int that's a power of 2
639 static final int MAX_TABLE_SIZE = Ints.MAX_POWER_OF_TWO;
640
641 // Represents how tightly we can pack things, as a maximum.
642 private static final double DESIRED_LOAD_FACTOR = 0.7;
643
644 // If the set has this many elements, it will "max out" the table size
645 private static final int CUTOFF = (int) (MAX_TABLE_SIZE * DESIRED_LOAD_FACTOR);
646
647 /**
648 * Returns an array size suitable for the backing array of a hash table that uses open addressing
649 * with linear probing in its implementation. The returned size is the smallest power of two that
650 * can hold setSize elements with the desired load factor. Always returns at least setSize + 2.
651 */
652 // TODO(cpovirk): Move to Hashing or something, since it's used elsewhere in the Android version.
653 static int chooseTableSize(int setSize) {
654 setSize = Math.max(setSize, 2);
655 // Correct the size for open addressing to match desired load factor.
656 if (setSize < CUTOFF) {
657 // Round up to the next highest power of 2.
658 int tableSize = Integer.highestOneBit(setSize - 1) << 1;
659 while (tableSize * DESIRED_LOAD_FACTOR < setSize) {
660 tableSize <<= 1;
661 }
662 return tableSize;
663 }
664
665 // The table can't be completely full or we'll get infinite reprobes
666 checkArgument(setSize < MAX_TABLE_SIZE, "collection too large");
667 return MAX_TABLE_SIZE;
668 }
669
670 /**
671 * Default implementation of the guts of ImmutableSet.Builder, creating an open-addressed hash
672 * table and deduplicating elements as they come, so it only allocates O(max(distinct,
673 * expectedCapacity)) rather than O(calls to add).
674 *
675 * <p>This implementation attempts to detect hash flooding, and if it's identified, falls back to
676 * JdkBackedSetBuilderImpl.
677 */
678 private static final class RegularSetBuilderImpl<E> extends SetBuilderImpl<E> {
679 private @Nullable Object[] hashTable;
680 private int maxRunBeforeFallback;
681 private int expandTableThreshold;
682 private int hashCode;
683
684 RegularSetBuilderImpl(int expectedCapacity) {
685 super(expectedCapacity);
686 int tableSize = chooseTableSize(expectedCapacity);
687 this.hashTable = new @Nullable Object[tableSize];
688 this.maxRunBeforeFallback = maxRunBeforeFallback(tableSize);
689 this.expandTableThreshold = (int) (DESIRED_LOAD_FACTOR * tableSize);
690 }
691
692 RegularSetBuilderImpl(RegularSetBuilderImpl<E> toCopy) {
693 super(toCopy);
694 this.hashTable = Arrays.copyOf(toCopy.hashTable, toCopy.hashTable.length);
695 this.maxRunBeforeFallback = toCopy.maxRunBeforeFallback;
696 this.expandTableThreshold = toCopy.expandTableThreshold;
697 this.hashCode = toCopy.hashCode;
698 }
699
700 @Override
701 SetBuilderImpl<E> add(E e) {
702 checkNotNull(e);
703 int eHash = e.hashCode();
704 int i0 = Hashing.smear(eHash);
705 int mask = hashTable.length - 1;
706 for (int i = i0; i - i0 < maxRunBeforeFallback; i++) {
707 int index = i & mask;
708 Object tableEntry = hashTable[index];
709 if (tableEntry == null) {
710 addDedupedElement(e);
711 hashTable[index] = e;
712 hashCode += eHash;
713 ensureTableCapacity(distinct); // rebuilds table if necessary
714 return this;
715 } else if (tableEntry.equals(e)) { // not a new element, ignore
716 return this;
717 }
718 }
719 // we fell out of the loop due to a long run; fall back to JDK impl
720 return new JdkBackedSetBuilderImpl<E>(this).add(e);
721 }
722
723 @Override
724 SetBuilderImpl<E> copy() {
725 return new RegularSetBuilderImpl<E>(this);
726 }
727
728 @Override
729 SetBuilderImpl<E> review() {
730 int targetTableSize = chooseTableSize(distinct);
731 if (targetTableSize * 2 < hashTable.length) {
732 hashTable = rebuildHashTable(targetTableSize, dedupedElements, distinct);
733 maxRunBeforeFallback = maxRunBeforeFallback(targetTableSize);
734 expandTableThreshold = (int) (DESIRED_LOAD_FACTOR * targetTableSize);
735 }
736 return hashFloodingDetected(hashTable) ? new JdkBackedSetBuilderImpl<E>(this) : this;
737 }
738
739 @Override
740 ImmutableSet<E> build() {
741 switch (distinct) {
742 case 0:
743 return of();
744 case 1:
745 /*
746 * requireNonNull is safe because we ensure that the first `distinct` elements have been
747 * populated.
748 */
749 return of(requireNonNull(dedupedElements[0]));
750 default:
751 /*
752 * The suppression is safe because we ensure that the first `distinct` elements have been
753 * populated.
754 */
755 @SuppressWarnings("nullness")
756 Object[] elements =
757 (distinct == dedupedElements.length)
758 ? dedupedElements
759 : Arrays.copyOf(dedupedElements, distinct);
760 return new RegularImmutableSet<E>(elements, hashCode, hashTable, hashTable.length - 1);
761 }
762 }
763
764 /** Builds a new open-addressed hash table from the first n objects in elements. */
765 static @Nullable Object[] rebuildHashTable(
766 int newTableSize, @Nullable Object[] elements, int n) {
767 @Nullable Object[] hashTable = new @Nullable Object[newTableSize];
768 int mask = hashTable.length - 1;
769 for (int i = 0; i < n; i++) {
770 // requireNonNull is safe because we ensure that the first n elements have been populated.
771 Object e = requireNonNull(elements[i]);
772 int j0 = Hashing.smear(e.hashCode());
773 for (int j = j0; ; j++) {
774 int index = j & mask;
775 if (hashTable[index] == null) {
776 hashTable[index] = e;
777 break;
778 }
779 }
780 }
781 return hashTable;
782 }
783
784 void ensureTableCapacity(int minCapacity) {
785 if (minCapacity > expandTableThreshold && hashTable.length < MAX_TABLE_SIZE) {
786 int newTableSize = hashTable.length * 2;
787 hashTable = rebuildHashTable(newTableSize, dedupedElements, distinct);
788 maxRunBeforeFallback = maxRunBeforeFallback(newTableSize);
789 expandTableThreshold = (int) (DESIRED_LOAD_FACTOR * newTableSize);
790 }
791 }
792
793 /**
794 * We attempt to detect deliberate hash flooding attempts. If one is detected, we fall back to a
795 * wrapper around j.u.HashSet, which has built in flooding protection. MAX_RUN_MULTIPLIER was
796 * determined experimentally to match our desired probability of false positives.
797 */
798 // NB: yes, this is surprisingly high, but that's what the experiments said was necessary
799 // Raising this number slows the worst-case contains behavior, speeds up hashFloodingDetected,
800 // and reduces the false-positive probability.
801 static final int MAX_RUN_MULTIPLIER = 13;
802
803 /**
804 * Checks the whole hash table for poor hash distribution. Takes O(n) in the worst case, O(n /
805 * log n) on average.
806 *
807 * <p>The online hash flooding detecting in RegularSetBuilderImpl.add can detect e.g. many
808 * exactly matching hash codes, which would cause construction to take O(n^2), but can't detect
809 * e.g. hash codes adversarially designed to go into ascending table locations, which keeps
810 * construction O(n) (as desired) but then can have O(n) queries later.
811 *
812 * <p>If this returns false, then no query can take more than O(log n).
813 *
814 * <p>Note that for a RegularImmutableSet with elements with truly random hash codes, contains
815 * operations take expected O(1) time but with high probability take O(log n) for at least some
816 * element. (https://en.wikipedia.org/wiki/Linear_probing#Analysis)
817 *
818 * <p>This method may return {@code true} even on truly random input, but {@code
819 * ImmutableSetTest} tests that the probability of that is low.
820 */
821 static boolean hashFloodingDetected(@Nullable Object[] hashTable) {
822 int maxRunBeforeFallback = maxRunBeforeFallback(hashTable.length);
823 int mask = hashTable.length - 1;
824
825 // Invariant: all elements at indices in [knownRunStart, knownRunEnd) are nonnull.
826 // If knownRunStart == knownRunEnd, this is vacuously true.
827 // When knownRunEnd exceeds hashTable.length, it "wraps", detecting runs around the end
828 // of the table.
829 int knownRunStart = 0;
830 int knownRunEnd = 0;
831
832 outerLoop:
833 while (knownRunStart < hashTable.length) {
834 if (knownRunStart == knownRunEnd && hashTable[knownRunStart] == null) {
835 if (hashTable[(knownRunStart + maxRunBeforeFallback - 1) & mask] == null) {
836 // There are only maxRunBeforeFallback - 1 elements between here and there,
837 // so even if they were all nonnull, we wouldn't detect a hash flood. Therefore,
838 // we can skip them all.
839 knownRunStart += maxRunBeforeFallback;
840 } else {
841 knownRunStart++; // the only case in which maxRunEnd doesn't increase by mRBF
842 // happens about f * (1-f) for f = DESIRED_LOAD_FACTOR, so around 21% of the time
843 }
844 knownRunEnd = knownRunStart;
845 } else {
846 for (int j = knownRunStart + maxRunBeforeFallback - 1; j >= knownRunEnd; j--) {
847 if (hashTable[j & mask] == null) {
848 knownRunEnd = knownRunStart + maxRunBeforeFallback;
849 knownRunStart = j + 1;
850 continue outerLoop;
851 }
852 }
853 return true;
854 }
855 }
856 return false;
857 }
858
859 /**
860 * If more than this many consecutive positions are filled in a table of the specified size,
861 * report probable hash flooding. ({@link #hashFloodingDetected} may also report hash flooding
862 * if fewer consecutive positions are filled; see that method for details.)
863 */
864 static int maxRunBeforeFallback(int tableSize) {
865 return MAX_RUN_MULTIPLIER * IntMath.log2(tableSize, RoundingMode.UNNECESSARY);
866 }
867 }
868
869 /**
870 * SetBuilderImpl version that uses a JDK HashSet, which has built in hash flooding protection.
871 */
872 private static final class JdkBackedSetBuilderImpl<E> extends SetBuilderImpl<E> {
873 private final Set<Object> delegate;
874
875 JdkBackedSetBuilderImpl(SetBuilderImpl<E> toCopy) {
876 super(toCopy); // initializes dedupedElements and distinct
877 delegate = Sets.newHashSetWithExpectedSize(distinct);
878 for (int i = 0; i < distinct; i++) {
879 /*
880 * requireNonNull is safe because we ensure that the first `distinct` elements have been
881 * populated.
882 */
883 delegate.add(requireNonNull(dedupedElements[i]));
884 }
885 }
886
887 @Override
888 SetBuilderImpl<E> add(E e) {
889 checkNotNull(e);
890 if (delegate.add(e)) {
891 addDedupedElement(e);
892 }
893 return this;
894 }
895
896 @Override
897 SetBuilderImpl<E> copy() {
898 return new JdkBackedSetBuilderImpl<>(this);
899 }
900
901 @Override
902 ImmutableSet<E> build() {
903 switch (distinct) {
904 case 0:
905 return of();
906 case 1:
907 /*
908 * requireNonNull is safe because we ensure that the first `distinct` elements have been
909 * populated.
910 */
911 return of(requireNonNull(dedupedElements[0]));
912 default:
913 return new JdkBackedImmutableSet<E>(
914 delegate, ImmutableList.asImmutableList(dedupedElements, distinct));
915 }
916 }
917 }
918 }