[Freeciv-Dev] Re: hashtables

[Jed Davis <jldavis@xxxxxxxxxxxxxx>]

--On Friday, 21 July 2000 1:03 +0100 Vasco Alexandre Da Silva Costa 
<vasc@xxxxxxxxxxxxxxx> wrote:
> On Wed, 19 Jul 2000, Jed Davis wrote:
>
> > Would there be any problem with requiring hashtable (common/hash.*)
> > sizes  to be powers of two?  The current situation seems to be more of a
> Yes there would.
> Powers of two aren't prime numbers (by definition, except 1 & 2).
> Having hashtable sizes based on prime numbers reduces the number of key
> collisions.
Some hash functions are intended for tables with prime-number sizes, but 
some are intended for tables with sizes that are powers of 2.  (And some 
might have some other conditions on the table size.)
The current hashtables already use powers of 2 for sizes, but this isn't 
very strict, so hash functions that are designed around this constraint, 
and in fact require it (e.g. take the N most significant bits of something 
to get the hash value), can't really be implemented.
--Jed