Newsgroups: comp.lang.c
Path: utzoo!henry
From: henry@utzoo.uucp (Henry Spencer)
Subject: Re: hash algorithm
Message-ID: <1988Aug24.161422.13066@utzoo.uucp>
Organization: U of Toronto Zoology
References: <654@novavax.UUCP> <2550078@hpisod2.HP.COM> <4712@b-tech.UUCP> <2392@rtech.rtech.com>
Date: Wed, 24 Aug 88 16:14:22 GMT

In article <2392@rtech.rtech.com> daveb@llama.UUCP (Dave Brower) writes:
>If the collision chains generated by the naive function are short, it
>may be cheaper to search the chain than use a smarter hash.
>
>What I found in some real application, with about 3000 entries in the
>table, was that naive beat smart in real execution time.   The naive
>collision chains were typically 4-7 entries long.  I could not reduce
>the time spent in the smart hash function enough to make it worth using.

I second this.  Those of you who have looked over that masterpiece of
brilliant coding :-), the C News expire, will have noticed that it hashes
newsgroups simply by the length of the name.  Crude and inelegant... but
the longest collision chain is only a handful of entries long, and none
of the fancier hash functions did significantly better.
-- 
Intel CPUs are not defective,  |     Henry Spencer at U of Toronto Zoology
they just act that way.        | uunet!attcan!utzoo!henry henry@zoo.toronto.edu