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

Doug Lea dl at cs.oswego.edu
Fri Jul 11 19:08:53 UTC 2014

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.


More information about the core-libs-dev mailing list