[Freeciv-Dev] Re: patch: hash table improvements

[Jed Davis <jldavis@xxxxxxxxxxxxxx>]

--On Sunday, 30 July 2000 3:35 PM +0200 Falk Hueffner 
<falk.hueffner@xxxxxxxxxxxxxxxxxxxxxxxx> wrote:
> Jed Davis <jldavis@xxxxxxxxxxxxxx> writes:
>
> > Well, I hope they're improvements, anyway:
> >
> > * Replaced hash_fval_int and hash_fval_string.  hash_fval_int had a
> > * bit of a bug: if it's given a series of numbers that differ by a
> > * multiple of the table size (including any larger power of 2),
> > * they'll all hash to the same bucket.  hash_fval_string might have
> > * done something similar.
> Does it really have to be that complicated? STL for example uses x as
> a hash value for an integer x, and that works pretty well. Of course
> then the hash table size has to be prime to minimize collisions. This
> table is being used for sizes:
>
> // Note: assumes long is at least 32 bits.
My copy of Stroustrup (the book) states that this is a safe assumption, for 
what it's worth.
> static const int __stl_num_primes = 28;
> static const unsigned long __stl_prime_list[__stl_num_primes] =
> {
>   53ul,         97ul,         193ul,       389ul,       769ul,
>   1543ul,       3079ul,       6151ul,      12289ul,     24593ul,
>   49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
>   1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,
>   50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,
>   1610612741ul, 3221225473ul, 4294967291ul
> };
>
> BTW, the string hash is:
>   unsigned long __h = 0;
>   for ( ; *__s; ++__s)
>     __h = 5*__h + *__s;
>
>   return size_t(__h);
Well, if an STL implementation uses it it can't be especially flawed... and 
simplicity is always a good idea...  and my functions were more ad-hoc 
numerical alchemy than anything else...  So I'll put these in instead.
BTW, are my [proposed] changes to the table-size management a good idea or 
am I just wasting perfectly good CPU cycles?
--Jed