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