HashMap collision speed (regression 7->8)
dl at cs.oswego.edu
Fri Jan 9 19:51:03 UTC 2015
On 01/09/2015 02:22 PM, Bernd Eckenfels wrote:
> My naive suggestion would be to delay the treeifying a bit longer if
> the hash keys are not Compareable and the hash tables are large(er).
Feel free to experiment. Bear in mind that the main rationale for
treeifying HashMap and ConcurrentHashMap is that there are bad guys
out there who hand-craft millions of keys with identical hashCodes
to try to bring down servers. The treeified versions successfully
resist this, at the expense of adding a further penalty to classes
with already-terrible hashCodes. (One arguable benefit is that people
who now notice this will be more motivated to fix their hashCodes.)
The main penalty here vs linear lists for cases with only dozens
(vs millions) of clashing elements is the call to comparableClassFor
for non-Strings, which hits some reflective goop.
I posted something a few years ago mentioning that this could be
made faster with some other JDK support. But as Peter Levart noted,
bootstrapping issues preclude the most straightforward solution.
More information about the core-libs-dev