[concurrency-interest] ConcurrentHashMapV8 improvements

Nathan Reynolds nathan.reynolds at oracle.com
Thu Jun 7 12:06:18 EDT 2012


Doug,

 > 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.

I recommend making similar changes to HashMap for this same reason.

Nathan Reynolds 
<http://psr.us.oracle.com/wiki/index.php/User:Nathan_Reynolds> | 
Consulting Member of Technical Staff | 602.333.9091
Oracle PSR Engineering <http://psr.us.oracle.com/> | Server Technology

On 6/6/2012 9:19 AM, Doug Lea wrote:
>
> 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
> source: 
> 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
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20120607/ca90459e/attachment.html>


More information about the Concurrency-interest mailing list