On Mon, 7 Sep 1998 03:07:51 -0700, "David S. Miller"
<davem@dm.cobaltmicro.com> said:
> Talk to researchers on this topic (I do), tree schemes only begin to
> give you back _lookup_ performance at 1,000 or so entires compared to
> any hash or skiplist scheme. And trees _never_ give you the
> insert/delete characteristics hash/skiplist schemes do (balancing
> overhead of trees vs. hash's constant time insert delete).
David, not only is the fuzzy hash O(n) (with low constant) for lookup,
it is also O(n) for insert, requiring insertion onto two separate
ordered lists...
--Stephen
-
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/faq.html