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

Martin Buchholz martinrb at google.com
Fri Jul 11 19:00:24 UTC 2014

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

I support a line-drawing more reasonable than the current MAX_CAPACITY - 1,
but we can leave that to another change, since it seems controversial.

More information about the core-libs-dev mailing list