Roman Leventov edited this page Apr 19, 2014 · 1 revision

Under QHash I understand not exactly the probing scheme described in Wikipedia, but a modification first suggested by C. Radke in the article "The use of quadratic residue research" (1970), which allows to probe all slots in the hash table exactly once, i. e. the probing sequence is a permutation of the slots.

Brief explaination:

  1. Table size (modulo) should be a prime of the form 4k + 3

  2. Probing sequence: h(k), h(k) + 1^2, h(k) - 1^2, h(k) + 2^2, h(k) - 2^2, h(k) + 3^2, etc.

Performance

Unsuccessful search

I made an experiment to determine mean probe counts for unsuccessful search.

Results of run $ java ...QHashProbes 1000000 1000 0.001 compared to theoretical results about linear probing and double hashing are available here (with a chart).

QHash performes very close to random probing with secondary clustering, in that number briefly discussed by Knuth in TAoCP Vol. 3 Chapter 6.4.

Mean probe count is approximated well enough by this formula:

mean probe count = (1.0 + 0.04 * α + 0.47 * α^2 - 0.21 * α^3) * (1 / (1 - α)), where α is a hash table load.

1 / (1 - α) here is the theoretical mean probe count for uniform hashing, to which double hashing is considered to be almost equal.

You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.
Press h to open a hovercard with more details.