RFR: [6904367]: (coll) IdentityHashMap is resized before exceeding the expected maximum size

[Doug Lea]

I've been content to just observe Martin and Peter's nice efforts
on this, but one note:

On 07/11/2014 03:00 PM, Martin Buchholz wrote:
> On Wed, Jul 9, 2014 at 3:17 PM, Peter Levart <peter.levart at gmail.com> wrote:
>
>>
>> IMH resizing is arranged so that the table is always 33% ... 66% full (if
>> nothing is ever removed from it) except when capacity reaches 2**29, then
>> it can be filled up to the top.
>>
>> avg. # of probes can be taken as a rough estimation of average slow-down,
>> max. # of probes can be taken as a rough estimation of worst-case-operation
>> slow-down.
>>
>> So where to draw the line?
>>
>
> Linear probing has long been known to be prone to long worst-case probes,
> but with recent computer architectures this is offset by its extreme cache
> friendliness.

Bear in mind that the number of bits of identityHashCode is less
than 32 on all JVMs I know. It can be as low as 23, which means that
you are sure to see a lot of exact collisions on IHMs with only
tens of millions of elements, and there's nothing much you can
do that will help.

-Doug