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