On Thu, Aug 18, 2011 at 8:40 AM, Sean Kelly <[email protected]> wrote: > On Aug 17, 2011, at 2:36 PM, bearophile wrote: > >> Walter: >> >>> Bottom line, I don't think there's an actual problem here. >> >> Thank you for your answers. And I agree that the current situation is >> overall better than the precedent one. >> >> My original first post of this thread was about other problems, quite more >> practical ones, like receiving help from the compiler if I am using hash >> protocol badly, etc. :-) > > This would be a run-time issue, unless you're asking the compiler to verify > your hash algorithm at compile-time :-p I'd actually like to have some > introspection functionality so I could find out the average chain length, max > chain length, etc (basically what's provided by the unordered containers from > C++11), but the user would still have to query this stuff to know that > something was wrong.
The security issue is basically a DoS one, for example if you know a web server is using a specific hash and collision resolution method to store message headers you can pass headers that all hash to buckets that provide worst-case behavior. In this instance universal hashing where a hash function is chosen randomly from a pool of hashes combined with good algorithmic complexity means the attacker is unable to do this reliably. Unrelated though, I'm quite a fan of hopscotch hashing at the moment, in theory at least. It'd be interesting to get a few different resolution schemes working and compare their performance on various workloads.
