Search code examples
hashtable

Hashtable with double hashing and twin primes without secondary hash function


I was told we can have a hashtable with double hashing without any secondary hash function and larger twin prime as capacity. I am wondering how how accessing an element would look like.

First try to get index using the following:

index = hash % capacity

Otherwise use the following where attempt starts from zero:

index = (hash + attempt++) % (capacity - 2)

Am I on the right track?


Solution

  • I found the answer. Page 614 of "Data Structures and Other Objects Using C++ (4th Edition)" describes the approach:

    enter image description here