[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Qemu-devel] Re: [PATCH 04/29] Introduce QDict
From: |
Luiz Capitulino |
Subject: |
[Qemu-devel] Re: [PATCH 04/29] Introduce QDict |
Date: |
Thu, 20 Aug 2009 11:14:40 -0300 |
On Thu, 20 Aug 2009 11:00:46 +0200
Paolo Bonzini <address@hidden> 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.
- [Qemu-devel] [PATCH 03/29] Introduce QString, (continued)
[Qemu-devel] Re: [PATCH 04/29] Introduce QDict, Paolo Bonzini, 2009/08/20
- [Qemu-devel] Re: [PATCH 04/29] Introduce QDict,
Luiz Capitulino <=
Re: [Qemu-devel] [PATCH 04/29] Introduce QDict, Markus Armbruster, 2009/08/24
[Qemu-devel] [PATCH 05/29] Add wrappers to functions used by the Monitor, Luiz Capitulino, 2009/08/19
[Qemu-devel] [PATCH 06/29] monitor: New format for handlers argument types, Luiz Capitulino, 2009/08/19
[Qemu-devel] [PATCH 07/29] monitor: Setup a QDict with arguments to handlers, Luiz Capitulino, 2009/08/19