[Qemu-devel] Re: [PATCH 04/29] Introduce QDict

[Luiz Capitulino <lcapitulino@redhat.com>]

On Thu, 20 Aug 2009 11:00:46 +0200
Paolo Bonzini <bonzini@gnu.org> wrote:

> > +
> > +/**
> > + * tdb_hash(): based on the hash agorithm from gdbm, via tdb
> > + * (from module-init-tools)
> > + */
> > +static unsigned int tdb_hash(const char *name)
> > +{
> > +    unsigned value;	/* Used to compute the hash value.  */
> > +    unsigned   i;	/* Used to cycle through random values. */
> > +
> > +    /* Set the initial value from the key size. */
> > +    for (value = 0x238F13AF * strlen(name), i=0; name[i]; i++)
> > +        value = (value + (((const unsigned char *)name)[i]<<  (i*5 % 24)));
> 
> This is a _bad_ hash function, especially because 5 is exactly the bit 
> that is flipped between lowercase and uppercase.  So "aa" would collide 
> with "Ab".
> 
> Besides, since the function is additive, you can initialize the value to 
> 0 and add "0x238F13AF * i" at the end (but this is just showing off...).
> 
> Here is a very simple but good hash function:
> 
>    uintptr_t hashVal = 1497032417;    /* arbitrary value */
> 
>    while (len--)
>      {
>        hashVal += *str++;
>        hashVal += (hashVal << 10);
>        hashVal ^= (hashVal >> 6);
>      }
> 
>    return 1103515243 * value;

[ I have to say that I was 100% sure that someone would come with a
  'better' hash function, I'm actually impressed it took three
   submissions to happen. :) ]

 Well, to be honest I'm not a hash expert and took the first
hash function I knew that was used by a widely used program.

 That said, I would not agree changing the hash function for this
series, as we have no code in tree that can be used to really
measure this and confirm what is good and what is not.

 Also, current monitor code will push a maximum of five objects
into the dict, looks a minor issue to me.