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