Full period quadratic hashing

Abstract

If n, the size of an open hash table, is a prime number then quadratic displacement guarantees that, in the event of successive collisions, exactly (n+1)/2 different entries are eventually examined (although more than (n+1)/2 probes may be necessary to achieve this). If n is a power of 2 then in general only a small portion of the table will be searched. We present here two sets of quadratic polynomials which guarantee full period search (n different entries hit in n probes) for any table size which is a power of 2. We also prove that these are the only quadratic polynomials with this property.

Keywords:

• Hashing
• Hash Table
• Open Hash Table
• Scatter Table
• Scatter Storage
• Table Access
• Table Look-Up
• Searching
• Full Period Search
• Quadratic Displacement
• Symbol Table

C.R. Categories::

• 3.74
• 4.49
• 4.9