The Three Distance Theorem goes like this :
For any irrational number 'a', if the sequence of points {i*a}, where 0 <= i <= n, are plotted on a unit distance / circle (wrapped at unit distance), then :
- The points divide the circle / line into n+1 distances
- The maximum number of distinct distances defined is 3
- The minimum number of distinct distances defined is 2
- Of the three distinct distances, one is a sum of the other two
The findings are really awesome - as Prof Skiena explains and proves the theorem in the lecture.
Application To Hashing
I think because of the distinct distance generation property of the theorem, the theorem can be an effective way to avoid collisions by the basic multiplication method. Ofcourse the other limitations of open addressing apply, but if that approach is chosen, this theorem might be helpful.
The basic idea for collision resoluton would be hashing in this order :
h(k, 1) = H(K*1*a)
h(k, 2) = H(K*2*a) ...where
h(k, l) - hash for the key k, being hashed for the lth time
k - key to insert / lookup
a - an irrational number
1, 2 - the first, second lookup. The l+1th lookup should be performed only if lth lookup had a collision
