Details
-
Improvement
-
Status: Open
-
Major
-
Resolution: Unresolved
-
2.6.0
-
None
-
None
Description
Comment by David Bertoni [25/Feb/05 03:14 AM]
I've also noticed that many places in the code, people have been careful to provide a prime number as the bucket count for hash tables, presumably for better distribution. However, when the table grows, we multiply the initial hash by 2, which means the bucket count is no longer a prime number. Should we be concerned?
I can think if a couple of other choices:
1. choose the first prime number that's less than the original bucket count * 2 (or the first that's greater).
2. extend the HasherBase class to provide the new bucket count.
Comment by Gareth Reakes [25/Feb/05 10:28 AM]
I committed that patch David. For your next problem, is there any nice way of finding the nearest prime? I know its not possible except through brute force, but would most of the time do. For example, I found this
In each 30 integers, for N >= 1, the numbers that might be prime are
N*30+1,
N*30+7,
N*30+11,
N*30+13,
N*30+17,
N*30+19,
N*30+23,
N*30+29
how often does that hold? Could we just ensure the next number is divisable by 30 and add 1 and say thats OK most of the time? Otherwise we could populate a structure with some primes during startup. How big is the table likely to get?