Re: [PATCH] Define hash_mem in lib/hash.c to apply hash_long to an

Jeremy Fitzhardinge (jeremy@goop.org)
06 Jan 2003 23:33:23 -0800


On Mon, 2003-01-06 at 21:03, Neil Brown wrote:
> Seeing as we have a simple, elegant, and effective hash_long in
> hash.h, and seeing that I need to hash things that aren't a long
> (i.e. strings), I would like to propose defining "hash_mem" based on
> hash_long as done in the following patch (hash_mem already exists
> local to net/sunrpc/svcauth.c, this patch tidies it up and moves it to
> lib/hash.c).
>
> It could be argued that there are better hashing functions for
> strings, and indeed Andrew Morton pointed me to ext3/hash.c
>
> I did a little testing and found that on a list of 2 million
> basenames from a recent backup index (800,000 unique):
>
> hash_mem (as included here) is noticably faster than HASH_HALF_MD4 or
> HASH_TEA:
>
> hash_mem: 10 seconds
> DX_HASH_HALF_MD4: 14 seconds
> DX_HASH_TEA: 15.2 seconds

I think they have a different set of design requirements. They're both
designed to not only generate hashes, but make the hashes
cryptographically strong (ie, impossible to generate collisions with
less effort than brute force). They're naturally slower than a simple
hash, so you'd only use them if you need the stronger requirements.

J

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/