[Freeciv-Dev] Re: Hash tables

[Jules Bean <jmlb2@xxxxxxxxxxxxxxxx>]

On Mon, Mar 27, 2000 at 10:01:54AM +0100, Sebastian Bauer wrote:
> 
> >>> Also, the size of an hash table (number of buckets) should be a prime
> >>> number to reduce the number of colisions.
> >> Yes, we learned that too :-)
> > I thought that in general this would depend on the specific
> > hash function used?  (Not that I know that case for any specific 
> > hash function, and thanks to Vasco for the improved one.)
> 
> Hmm...if I think about it...this could be.
> I neihter really know it nor I have tested it yet for myself. At
> least the hash function we had was better if the maximal number of
> buckets was a prime number.

You want the number of buckets to be coprime to the number you
multiply by, in general, especially if the last operation in your hash
algorithm is the multiply.

Prime just makes it easy to see nothing (of this sort) can go wrong.

-- 
Jules Bean                          |        Any sufficiently advanced 
jules@{debian.org,jellybean.co.uk}  |  technology is indistinguishable
jmlb2@xxxxxxxxxxxxxxxx              |               from a perl script