ImmutableCollections SetN implementation detail : <p>I have sort of a hard time understanding an implementation detail from java-9 <code>ImmutableCollections.SetN</code>; specifically why is there a need to increase the inner array twice.</p>

<p>Suppose you do this:</p>

<pre><code>Set.of(1,2,3,4) // 4 elements, but internal array is 8
</code></pre>

<p>More exactly I perfectly understand why this is done (a double expansion) in case of a <code>HashMap</code> - where you never (almost) want the <code>load_factor</code> to be one. A value of <code>!=1</code> improves search time as entries are better dispersed to buckets for example.</p>

<p>But in case of an <em>immutable Set</em> - I can't really tell. Especially since the way an index of the internal array is chosen.</p>

<p>Let me provide some details. First how the index is searched:</p>

<pre><code> int idx = Math.floorMod(pe.hashCode() ^ SALT, elements.length);
</code></pre>

<p><code>pe</code> is the actual value we put in the set. <code>SALT</code> is just 32 bits generated at start-up, once per <code>JVM</code> (this is the actual randomization if you want). <code>elements.length</code> for our example is <code>8</code> (4 elements, but 8 here - double the size).</p>

<p>This expression is like a <em>negative-safe modulo operation</em>. Notice that the same logical thing is done in <code>HashMap</code> for example (<code>(n - 1) &amp; hash</code>) when the bucket is chosen. </p>

<p>So if <code>elements.length is 8</code> for our case, then this expression will return any positive value that is less than 8 <code>(0, 1, 2, 3, 4, 5, 6, 7)</code>.</p>

<p>Now the rest of the method:</p>

<pre><code> while (true) {
        E ee = elements[idx];
        if (ee == null) {
            return -idx - 1;
        } else if (pe.equals(ee)) {
            return idx;
        } else if (++idx == elements.length) {
            idx = 0;
        }
    }
</code></pre>

<p>Let's break it down:</p>

<pre><code>if (ee == null) {
    return -idx - 1;
</code></pre>

<p>This is good, it means that the current slot in the array is empty - we can put our value there.</p>

<pre><code>} else if (pe.equals(ee)) {
    return idx;
</code></pre>

<p>This is bad - slot is occupied and the already in place entry is equal to the one we want to put. <code>Set</code>s can't have duplicate elements - so an Exception is later thrown.</p>

<pre><code> else if (++idx == elements.length) {
      idx = 0;
 }
</code></pre>

<p>This means that this slot is occupied (hash collision), but elements are not equal. In a <code>HashMap</code> this entry would be put to the same bucket as a <code>LinkedNode</code> or <code>TreeNode</code> - but not the case here. </p>

<p>So <code>index</code> is incremented and the next position is tried (with the small caveat that it moves in a circular way when it reaches the last position).</p>

<p>And here is the question: if nothing too fancy (unless I'm missing something) is being done when searching the index, why is there a need to have an array twice as big? Or why the function was not written like this:</p>

<pre><code>int idx = Math.floorMod(pe.hashCode() ^ SALT, input.length);

// notice the diff elements.length (8) and not input.length (4)
</code></pre>
