Re: Question regarding Larson's "Linear Hashing with Partial Expansions" whitepaper

In the last exciting episode, xagrx_at_pobox.com (XagrX) wrote:
> I am implementing a DB based on Larson's "A Single-File Version Of
> Linear Hashing With Partial Expansions" whitepaper. I am certain
> many of you will be familiar with this.
> A copy of this paper can be found online at
> www.acm.org/sigmod/vldb/conf/1982/P300.PDF
>
> My question is concerning Algorithm A on page 5. Specifically, the
> D(K) function makes no sense to me, because perhaps it is using
> mathematical terminology that I am unfamiliar with.
>
> The paper states:
> "the address computation algorithm makes use" ... " a sequence of
> hashing functions
> D(K) = (d 1 (K) , d 2 (K), ...) where each function d i (K) hashes
> uniformly over {0, 1, ... 2n0 - 1}."
>
> Notice that n0 is a constant value. Anyway, if I am reading this
> properly, it appears that each d?(K) function will return the same
> result given a similar K value.
> I thought that it might actually be d i (K) = {0, 1, ... 2^i*n0 - 1}
> but this does not work in my testing.
>
> Any enlightenment would be greatly appreciated! Many thanks.

No, the idea would be that each d_{i}(K) function performs a _different_ uniform hashing of values across the set of keys.

The simplest such set of hash functions would be

  d_{i}(K) = (K + i) mod (2n_{0} - 1)

although that's not much of a hash; that's just a linear transformation.

-- 
select 'cbbrowne' || '_at_' || 'cbbrowne.com';
http://www.ntlug.org/~cbbrowne/finances.html
"Success is something  I  will dress for   when I get  there,  and not
until."  -- Unknown