HashMap collision speed (regression 7->8)
Peter Levart
peter.levart at gmail.com
Sun Jan 11 11:35:01 UTC 2015
On 01/11/2015 02:21 AM, Martin Buchholz wrote:
> 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.
As I understand the code, compareTo is only called when hashes are equal
to break the tie, otherwise hash is always used 1st in tree bins, but if
hashes are the same, then equlas() does check the length 1st but
compareTo can't.
Peter
More information about the core-libs-dev
mailing list