lkml.org 
[lkml]   [1999]   [May]   [4]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: 2.2.6_andrea2.bz2
Hi!

> > 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).

Pavel
--
I'm really pavel@atrey.karlin.mff.cuni.cz. Pavel
Look at http://atrey.karlin.mff.cuni.cz/~pavel/ ;-).

-
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/

\
 
 \ /
  Last update: 2005-03-22 13:51    [W:0.054 / U:0.136 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site