Re: g_str_hash

[Kaz Kylheku <kaz ashi footprints net>]

On 11 Feb 2000, Havoc Pennington wrote:

> Date: 11 Feb 2000 01:29:43 -0500
> From: Havoc Pennington <hp@redhat.com>
> Reply-To: gtk-devel-list@redhat.com
> To: gtk-devel-list@redhat.com
> Subject: g_str_hash
> Resent-Date: 11 Feb 2000 06:31:43 -0000
> Resent-From: gtk-devel-list@redhat.com
> Resent-cc: recipient list not shown: ;
> 
> 
> Hi,
> 
> g_str_hash is really slow. The Tcl string hash function is twice as
> fast, literally. Here's a test program, and it also shows you the Tcl
> function. Any objections to the Tcl version?
> 
> Havoc
> 
> #include <glib.h>
> #include <stdio.h>
> #include <time.h>
> 
> guint
> copy_of_g_str_hash (gconstpointer v)
> {
>   const char *s = (char*)v;
>   const char *p;
>   guint h=0, g;
> 
>   for(p = s; *p != '\0'; p += 1) {
>     h = ( h << 4 ) + *p;
>     if ( ( g = h & 0xf0000000 ) ) {
>       h = h ^ (g >> 24);
>       h = h ^ g;
>     }
>   }

Remark: this function is derived from the one in the Dragon Book. I've
seen it used in quite a few places, including the directory caching code
in the Linux kernel. It is essentially a feedback shift register.
 
>   return h /* % M */;
> }
> 
> guint
> tcl_hash(gconstpointer v)
> {
>   const char* string = (char*)v;
>   unsigned int result = 0;
>   int c;
> 
>   while (1) {
>     c = *string;
>     string++;
>     if (c == 0) {
>       break;
>     }
>     result += (result<<3) + c;
>   }
>   return result;
> }

This function may execute faster on your machine but it is somewhat more naive.
Note that strings which have a common suffix will hash to common value.  This
may or may not be a problem.