[net.general] Hash table size selection

andrew@inmet.UUCP (02/15/84)

#R:proper:-99700:inmet:4100027:000:868
inmet!andrew    Feb 14 10:57:00 1984

Yes.. it relates to double hashing, where a second hash function is used for
resolution of collisions:  If slot f1(x) is already occupied, compute a new
hash address ((f1(x)+f2(x)) mod tablesize) and try that, repeating this until
a) a vacant slot is found, or b) you return to the original f1(x), in which
case the table is effectively full.  

Case b) above will occur after (tablesize/GCD(tablesize, f2(x)) iterations;
this number is maximized when tablesize and f2(x) are relatively prime (GCD =
1).  The easiest way to ensure this for all values of f2(x) is to select a 
prime number for tablesize.

If f2(x) is a constant (degenerate double hashing), tablesize need only be
relatively prime to it; for example, a table size of 46 would be acceptable
in conjunction with a constant f2 of 9.
 
Andrew W. Rogers, Intermetrics    ...{harpo|ima|esquire}!inmet!andrew