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

[Falk Hueffner <falk.hueffner@xxxxxxxxxxxxxxxxxxxxxxxx>]

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.
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);

        Falk