Hashing: robin hood, linear probing, swiss table, quadratic probing

1

If I am reading Rust's hash map correctly, it switched

from:

  • robin hood w/ linear probing of 1, 2, 3, ..., n

to

  • swiss table w/ quadratic probing of 1, 1+2, 1+2+3, ..., n(n+1)/2

===

  1. I am not 100% certain, but I believe the quadratic probing makes it difficult to do backshifts, and as a result, we (may have to) use tombstones on deletes (unless there's an empty within the 16 buckets)

  2. there are vague claims floating around that quadratic probing defends vs certain types of hash DOS attacks (ignore choice of hash function + private key for now)

Question: what exactly is the type of hash DOS attacks that quadratic probing defends against? (please be as precise as possible about the sequence of elements)

1 Like
2

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.