Builder(int initialCapacity) {
      this.entries = new @Nullable Entry[initialCapacity];
      this.size = 0;
      this.entriesUsed = false;
    }

    private void ensureCapacity(int minCapacity) {
      if (minCapacity > entries.length) {
        entries =
            Arrays.copyOf(
                entries, ImmutableCollection.Builder.expandedCapacity(entries.length, minCapacity));
        entriesUsed = false;

    List<Entry<K, V>> entries =
        copyToList(
            getSubjectGenerator()
                .getSampleElements(getSubjectGenerator().getCollectionSize().getNumElements()));
    sort(entries, Helpers.entryComparator(navigableMap.comparator()));

    // some tests assume SEVERAL == 3
    if (entries.size() >= 1) {
      a = entries.get(0);
      if (entries.size() >= 3) {
        c = entries.get(2);
      }

      Set<Entry<Object, Object>> entries = cache.asMap().entrySet();
      List<Entry<Object, Object>> warmed = warmUp(cache, WARMUP_MIN, WARMUP_MAX);

      Set<?> expected = new HashMap<>(cache.asMap()).entrySet();
      assertThat(entries).containsExactlyElementsIn(expected);
      assertThat(entries.toArray()).asList().containsExactlyElementsIn(expected);

    final List<Entry<K, V>> entries;
    @Nullable Comparator<? super V> valueComparator;

    public Builder() {
      this.entries = Lists.newArrayList();
    }

    Builder(int initCapacity) {
      this.entries = Lists.newArrayListWithCapacity(initCapacity);
    }

    @CanIgnoreReturnValue
    public Builder<K, V> put(K key, V value) {
      entries.add(entryOf(key, value));
      return this;

    private final transient ImmutableList<Entry<K, V>> entries;

    RegularEntrySet(ImmutableMap<K, V> map, Entry<K, V>[] entries) {
      this(map, asImmutableList(entries));
    }

    RegularEntrySet(ImmutableMap<K, V> map, ImmutableList<Entry<K, V>> entries) {
      this.map = map;
      this.entries = entries;
    }

    @Override
    ImmutableMap<K, V> map() {
      return map;
    }

                new TestStringMapGenerator() {
                  @Override
                  protected Map<String, String> create(Entry<String, String>[] entries) {
                    Map<String, String> map = CompactHashMap.create();
                    for (Entry<String, String> entry : entries) {
                      map.put(entry.getKey(), entry.getValue());
                    }
                    return map;
                  }

    Set<Entry<@Nullable String, @Nullable Boolean>> entries = map.entrySet();
    assertTrue(entries.contains(immutableEntry("a", true)));
    assertTrue(entries.contains(Maps.<String, @Nullable Boolean>immutableEntry("b", null)));
    assertTrue(
        entries.contains(Maps.<@Nullable String, @Nullable Boolean>immutableEntry(null, null)));

    assertFalse(entries.contains(Maps.<String, @Nullable Boolean>immutableEntry("c", null)));

    Set<Entry<@Nullable String, @Nullable Boolean>> entries = map.entrySet();
    assertTrue(entries.contains(immutableEntry("a", true)));
    assertTrue(entries.contains(Maps.<String, @Nullable Boolean>immutableEntry("b", null)));
    assertTrue(
        entries.contains(Maps.<@Nullable String, @Nullable Boolean>immutableEntry(null, null)));

    assertFalse(entries.contains(Maps.<String, @Nullable Boolean>immutableEntry("c", null)));

    Set<Entry<String, Collection<Integer>>> entries = asMap.entrySet();
    assertFalse(entries.contains((Object) 4.5));
    assertFalse(entries.remove((Object) 4.5));
    assertFalse(entries.contains(Maps.immutableEntry("foo", singletonList(1))));
    assertFalse(entries.remove(Maps.immutableEntry("foo", singletonList(1))));
    assertFalse(entries.contains(Maps.immutableEntry("foo", new LinkedHashSet<>(asList(1, 2)))));

const numBuckets = 100

// NewLRU returns a new thread-safe cache with expirable entries.
//
// Size parameter set to 0 makes cache of unlimited size, e.g. turns LRU mechanism off.
//
// Providing 0 TTL turns expiring off.
//
// Delete expired entries every 1/100th of ttl value. Goroutine which deletes expired entries runs indefinitely.