* #offer} and a call to {@link #topK}, with O(k) memory. In comparison, quickselect has the same
 * asymptotics but requires O(n) memory, and a {@code PriorityQueue} implementation takes O(n log
 * k). In benchmarks, this implementation performs at least as well as either implementation, and
 * degrades more gracefully for worst-case input.
 *

  /** The number of occurrences of each element. */
  private final transient ConcurrentMap<E, AtomicInteger> countMap;

  // This constant allows the deserialization code to set a final field. This holder class
  // makes sure it is not initialized unless an instance is deserialized.
  private static class FieldSettersHolder {
    static final FieldSetter<? super ConcurrentHashMultiset<?>> COUNT_MAP_FIELD_SETTER =

  @GwtIncompatible // java.math.BigInteger
  public void testMean() {
    // Odd-sized ranges have an obvious mean
    assertMean(2, 1, 3);

    assertMean(-2, -3, -1);
    assertMean(0, -1, 1);
    assertMean(1, -1, 3);
    assertMean((1 << 30) - 1, -1, Integer.MAX_VALUE);

    // Even-sized ranges should prefer the lower mean
    assertMean(2, 1, 4);
    assertMean(-3, -4, -1);
    assertMean(0, -1, 2);

  }

  /**
   * This test attempts to cause a future to wait for longer than it was requested to from a timed
   * get() call. As measurements of time are prone to flakiness, it tries to assert based on ranges
   * derived from observing how much time actually passed for various operations.
   */
  @SuppressWarnings({"DeprecatedThreadMethods", "ThreadPriorityCheck"})
  @AndroidIncompatible // Thread.suspend

    return getSubMap(0, keySet.headIndex(checkNotNull(toKey), inclusive));
  }

  /**
   * This method returns a {@code ImmutableSortedMap}, consisting of the entries whose keys ranges
   * from {@code fromKey}, inclusive, to {@code toKey}, exclusive.
   *
   * <p>The {@link SortedMap#subMap} documentation states that a submap of a submap throws an {@link

    // and reduces the false-positive probability.
    static final int MAX_RUN_MULTIPLIER = 13;

    /**
     * Checks the whole hash table for poor hash distribution. Takes O(n) in the worst case, O(n /
     * log n) on average.
     *
     * <p>The online hash flooding detecting in RegularSetBuilderImpl.add can detect e.g. many

     * be read without locking. Next fields of nodes are immutable (final). All list additions are
     * performed at the front of each bin. This makes it easy to check changes, and also fast to
     * traverse. When nodes would otherwise be changed, new nodes are created to replace them. This

     *   `map.getOrDefault(FOO_KEY, defaultValue)`
     *
     * - a call that consults a chain of maps, as in `mapA.getOrDefault(key, mapB.getOrDefault(key,
     *   ...))`
     *
     * So it makes sense for the parameter (and thus the return type) to be @CheckForNull.
     *
     * Two other points:
     *
     * 1. We'll want to use something like @PolyNull once we can make that work for the various

   * hang forever. More precisely, if it's expected to return, we simply call it[*], but if it's
   * expected to hang (because one of the input futures that we know makes it up isn't done yet),
   * then we call it in a separate thread (using pseudoTimedGet). The result is that we wait as long
   * as necessary when the method is expected to return (at the cost of hanging forever if there is

    try {
      Maps.capacity(-1);
      fail("Negative expected size must result in IllegalArgumentException");
    } catch (IllegalArgumentException expected) {
    }
  }

  /**
   * Tests that nHMWES makes hash maps large enough that adding the expected number of elements
   * won't cause a rehash.
   *
   * <p>As of jdk7u40, HashMap has an empty-map optimization. The argument to new HashMap(int) is