Re: Glib hash tables, how to create the hash for optiomal performance.

[Havoc Pennington <hp redhat com>]

On Sat, Aug 30, 2003 at 12:28:09PM +1000, Ronnie Sahlberg wrote: 
> I guess my question is,   when i create the hash function,   how should i
> distribute the calcualted hash values in the range 0 to 2^32-1
> in order to get optimal performance.

As evenly as possible.
 
> Second question is:    how should I distribute collissions when calculating
> the hash value?
> Should I try to avoid collissions completely?
> Should I try to completely avoid collissions? or should I try to
> deliberately create some collissions in order to keep the number of hash
> buckets down?

You want to have as few collisions as possible (evenly distribute
through the range 0 to 2^32-1). If there are collisions, GHashTable
will handle it by putting all the collisions in the same hash bucket,
but then a lookup involves scanning the linked list in the bucket. 
So if your hash function isn't evenly distributed you can degenerate
to O(n) performance.

Havoc