HashMap collision speed (regression 7->8)

Martin Buchholz martinrb at google.com
Sun Jan 11 01:21:59 UTC 2015

On Fri, Jan 9, 2015 at 4:20 PM, Doug Lea <dl at cs.oswego.edu> wrote:

> On 01/09/2015 06:29 PM, Martin Buchholz wrote:
>> Given the prevalence of sub-optimal hashcodes, my own intuition is also
>> that
>> raising the treeification threshold from 8 will be a win.
> That's what I thought at first. But 8 is a better choice for String
> and other Comparable keys, which account for the majority of HashMaps
> out there. (For non-comparables, infinity is the best threshold.)

Non-malicious Strings are only rarely going to end up in treebins, because
their hash codes are not awful (just sub-optimal - hmmm ... is anyone
putting all possible 2-char Strings into a HashMap?).  I'm not convinced
that comparableClassFor should special-case Strings.

Linear search through a non-treebin of non-malicious Strings is likely to
be fast, because we will short-circuit if hash codes or length don't match,
which compareTo cannot.  So compareTo is likely to have more overhead per
element, although of course in the end log(N) beats N.

More information about the core-libs-dev mailing list