Double hashing
Double hashing is designed to reduce clustering. It does this by calculating the stride for a given key using a second, independent hash function. Thus, two objects will have the same probe sequence only if there is a collision in the output of both the primary hash function and the secondary hash function. If these functions are well-designed, then the probability of this occurring should be very small鈥攐n the order of 1 / (n^2) where n is the table size.
Supplemental materials:
Comprehension check:
- With double hashing we calculate not only the index where we wish to insert (that is, the start of our probe sequence), but we calculate the _____________ as well.
- Our secondary hash function should never return the value ________ because if it did, we would never probe beyond the initial position.
- Ideally, our primary and secondary hash functions should be ___________________ of one another.
- If our primary function is f(x) = x \mod 7, and our secondary hash function is g(x) = 5 - (x \mod 5), then for a key value of 8 the first three steps in our probe sequence would be ___________, ____________, ___________.
- Double hashing is designed to prevent _______________.
Answers: 苾u岽壣骨澥噑nl蓴 / 蠜 鈥櫰� 鈥櫰� / 蕠u菨pu菨d菨pu岽� 菨s岽壥嵣贯磯蓯d / o晒菨z / 菨p岽壣故噑
Copyright 漏 2023鈥�2025 Clayton Cafiero
No generative AI was used in producing this material. This was written the old-fashioned way.