[FreecivDev] Re: patch: hash table improvements
[Top] [All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
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 adhoc
numerical alchemy than anything else... So I'll put these in instead.
BTW, are my [proposed] changes to the tablesize management a good idea or
am I just wasting perfectly good CPU cycles?
Jed

