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