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

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.

-Doug

More information about the core-libs-dev mailing list