An Alternative Hashing Alternative (original) (raw)

Rémi Forax forax at univ-mlv.fr
Wed Jun 6 17:09:36 UTC 2012

I haven't read the whole code (I need a blackboard :) I wonder if it's not better to use unsafe.tryMonitorEnter() instead of a lock bit.

Also the class depends on LongAdder, is it a requirement or an AtomicLongUpdater can be used ?

cheers, Rémi

On 06/06/2012 06:51 PM, Doug Lea wrote:

On 06/06/12 12:22, Doug Lea 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. The main issue is whether adding generic overflow-handling techniques to hash table classes (as used here for ConcurrentHashMap, but variations are applicable with a lot of effort to others) are a better solution than special-casing a better String hash method (i.e., the hash32 changes). My current sense is that they are: * They also address the huge-map problem (although not as well as would be the case if we had 64bit arrays and hash codes, but that is not happening anytime soon). * They work for types other than String (although still only for Comparables), and improve performance when hashes are merely poorly distributed, not hostilely identical. * They avoid the need for a cascading series of related OpenJDK updates. * Normal-case (non-hostile etc) throughput is better. On the other hand: Worst-case throughput using this approach for hostile Strings cannot be quite as good as using better, randomly-seeded hash functions. However, so long as the worst case is no worse than other ways to hostilely annoy busy servers etc, it is not clear to me that the hash32 approach is worthwhile. I don't have any factual basis for concluding this though, since I don't have full test setup for VU#903934. If anyone else does, I'd be interested in hearing about results. One more semi-related follow-up while I am at it: On 06/01/12 16:05, Eamonn McManus wrote: There's also a performance problem in that accesses start becoming linear once there are more than 1<< 30 entries, but fixing that is substantially harder than just fixing size(), and ConcurrentHashMap already provides a better alternative for such huge maps. Well, it does now in CHMV8. But before, even though it used segmented arrays, there are still only 32bits of hash code, so keys still collided. -Doug

More information about the core-libs-dev mailing list