"fuzzy hashing" = skiplists in a different shape

Patrik Hagglund (patha@ida.liu.se)
Fri, 28 Aug 1998 11:06:33 +0200


I saw your "fuzzy hashing" implementation on Linux Weekly News
yesterday, and to me it looks much like randomized skip list. The
neigbour_next list is the first level pointer chain and hash_next is
the second level. But, there is a notable exception. Your code
contians 16 second-level lists, that is, 15 redundant ones.

> it will be as fast or cheaper _even_ in the common case than what we
> have now

? What is this common case. I can't see how your implementation would
be faster than a good implementation of a balanced search tree.

Regards,
Patrik Hägglund,
intrested in data structures and algorithms,
but not a kernel hacker (yet)

-
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.altern.org/andrebalsa/doc/lkml-faq.html