About built-in AAs

[Josh Simmons]

On Thu, Aug 18, 2011 at 8:40 AM, Sean Kelly <sean at invisibleduck.org> 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.