Honey, I sped up the associated array

[Josh Stern]

On Fri, 13 Oct 2006 12:05:02 -0700, Walter Bright wrote:

> Lionello Lunesu wrote:
>> The size of the AA's internal array is the biggest factor, I've noticed. 
> 
> Not exactly, it's the number of collisions that matters, and the size of 
> the array influences this as well as the hash algorithm. For 
> mathematical reasons I do not understand, taking the remainder of 
> division by a prime number gives the most even 'spread' across the 
> array, minimizing collisions for a given array size.


If the hash code and the hash array size shared a common factor, then
the first can be written in the form k*x and the second in the form k*y,
so in the division the k's would cancel and spread function would be
really only modulus y rather than modulus k*y.   So picking a prime number
for the size of the array eliminates that possibility for k smaller than
the table size.

This link has the same values used in gcc's hashtable implementation:
http://planetmath.org/encyclopedia/GoodHashTablePrimes.html