Question about Linear hashing: A New Tool ...
Date: Mon, 27 Feb 2006 19:09:22 GMT
Message-ID: <m2ek1owrdq.fsf_at_gigamonkeys.com>
Hello, I was reading Witold Litwin's paper "Linear Hashing: A New Tool for File and Table Addressing" and it all makes good sense except one bit:
In section 2.3.3 "Other Split Functions" he describes a technique for creating functions that "are, obviously, split functions for *any* h0". However the technique he describes is to create a function h-sub-i of c by adding, essentially, a random number to the value of h-sub-i-minus-one applied to c. Since if h-sub-i is a "split function" of h-sub-i-minus-one it is supposed to return the same value as h-sub-i-minus-one half the time and h-sub-i-minus-one + 2^(i - 1)N the other half of the time, I don't get how this is obvious at all.
Obviously I'm not explaining this well enough for someone unfamiliar with the paper to know what I'm talking about but I'm hoping maybe somebody who has read it can explain to me what I'm missing. (Unfortunately I couldn't find the the paper anywhere for free on the web; it's available from the ACM's digital library for $5.00.)
-Peter
-- Peter Seibel * peter_at_gigamonkeys.com Gigamonkeys Consulting * http://www.gigamonkeys.com/ Practical Common Lisp * http://www.gigamonkeys.com/book/Received on Mon Feb 27 2006 - 20:09:22 CET