News for hackers. Stuff that matters.

A comment on Optimizing Open Addressing. Parent comment

Re:Optimizing Open Addressing by anarazel on Sunday April 02, 2023 @03:42PM (#35414313)
One situation where I painfully learned that it doesn't, is when you iterate over one hashtable to fill another. To defend against that one needs to add some per-hashtable randomized state into the hash IV.

Through bad experience I also learned that you need to not just grow due to fillfactor, but also due to disproportional chain length, even with the above defense in place.

[ Parent | on HN ]
Re:Optimizing Open Addressing by 10000truths on Sunday April 02, 2023 @04:53PM (#35415080)
> To defend against that one needs to add some per-hashtable randomized state into the hash IV.

You should almost always be doing this anyways, since most hash tables use user-provided data as keys, which opens up a well known avenue for denial-of-service attacks:

https://lwn.net/Articles/474912/

[ Parent | on HN ]
Re:Optimizing Open Addressing by anarazel on Sunday April 02, 2023 @05:29PM (#35415448)
I think that's often fixed using a per run random seed, rather than a per table seed. The patch linked in the python bug linked from that article does seem to do that, for example.
[ Parent | on HN ]