An Alternative Hashing Alternative

[Bob Lee]

Whoa! This is awesome.

Bob

On Wed, Jun 6, 2012 at 9:22 AM, Doug Lea <dl at cs.oswego.edu> wrote:

>
> I just posted the following to the concurrency-interest list.
> I'll send a follow-up on tie-ins to core-lib issues next.
>
> ...
>
>
> Finally acting on an old idea, I committed an update to
> ConcurrentHashMap (currently only the one in our jdk8 preview
> package, as jsr166e.ConcurrentHashMap8) that much more gracefully
> handles maps that are huge or have many keys with colliding
> hash codes. Internally, it uses tree-map-like structures to
> maintain bins containing more nodes than would be expected
> under ideal random key distributions over ideal numbers of bins.
>
> Among other things, this provides graceful (O log(N)) degradation when
> there are more than about a billion elements (which run out of 32bit
> hash resolution and array bound limits). However, the map can only
> do so if keys are Comparable, which is true of most keys in
> practice -- Strings, Longs, etc. Without relying on Comparable,
> we can't otherwise magically find any other means to further
> resolve and organize keys after running out of bits, so performance
> for non-Comparable keys is unaffected/unimproved.
>
> This also provides a mechanism for coping with hostile usages in
> which many keys (Strings in particular) are somehow constructed to
> have the same hashCode, which can lead to algorithmic denial
> of service attacks (because of linear-time bin searches) if
> code using the map don't screen external inputs. The overflow-tree-based
> strategy here is an alternative approach to adding secondary
> randomly-seeded hash code methods ("hash32") to class String,
> as has been committed recently to OpenJDK. But ConcurrentHashMap8
> doesn't doesn't rely on this.
>
> The use of overflow-bins also allowed a few other minor speedups
> in more typical usages. A few more small improvements are still
> left unfinished for now. (I'll be traveling and/or otherwise
> committed for most of the next few weeks.)
>
> Links:
> jsr166e.jar: http://gee.cs.oswego.edu/dl/**jsr166/dist/jsr166e.jar<http://gee.cs.oswego.edu/dl/jsr166/dist/jsr166e.jar>
> source: http://gee.cs.oswego.edu/cgi-**bin/viewcvs.cgi/jsr166/src/**
> jsr166e/ConcurrentHashMapV8.**java?view=log<http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/jsr166e/ConcurrentHashMapV8.java?view=log>
>
> Please give this a try and let me know about experiences.
>
> -Doug
>
>


-- 
Bob
Square is hiring! <https://squareup.com/jobs>