Messages in this thread | | | Date | Mon, 3 May 1999 23:08:19 +0200 | From | Pavel Machek <> | Subject | Re: 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/
| |