Re: 2.2.6_andrea2.bz2
Chuck Lever (cel@monkey.org)
Tue, 4 May 1999 16:12:29 -0400 (EDT)
On Mon, 3 May 1999, Pavel Machek wrote:
> > > Another idea: Currently every bucket in the hash table has to be a
> > > linked list. I haven't tried it, but the linked list could be replaced
> > > by a tree in order to limit the worst case. Even better, a bucket could
> > > stay a linked list as long as only one element is in the bucket (the
> > > most common case). I a second element is added, it becomes the root
> > > of a tree. Additional elements build the tree. If an element is removed
> > > from the tree, the normal tree algorithms apply. If the first element
> > > is removed, and there are other elements in the tree, one tree element
> > > must be moved to become the new first element.
> >
> > this seems expensive and complicated for no good reason. one can
> > construct a simple-to-understand hash function that will have excellent
> > average behavior and reasonable worst-case behavior, and even be pretty
> > cheap to calculate. why would i want to go to the expense of
>
> I do not understand. How do you want to guarantee worst-case behaviour
> for hash? I think that nearly every hash is going to be linear in
> worst case (i.e. everything in one chain).
hash tables work by showing very good *average* behavior. if that isn't
good enough, don't use a hash table :)
if you're careful about choosing your hash function and testing it with
the actual data you plan to store in the table, you should get perfectly
reasonable overall results. worst-case isn't something you need to be
concerned about unless your hash function is unavoidably terrible.
- Chuck Lever
--
corporate: <chuckl@netscape.com>
personal: <chucklever@netscape.net> or <cel@monkey.org>
The Linux Scalability project:
http://www.citi.umich.edu/projects/linux-scalability/
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/