Browse Prior Art Database

Modified Linear Scatter Storage Technique

IP.com Disclosure Number: IPCOM000076798D
Original Publication Date: 1972-Apr-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 1 page(s) / 11K

IBM

Related People

Brent, RP: AUTHOR

Abstract

A new algorithm and method for entering and retrieving information in a hash table is described. The method is intended to be efficient if most entries are looked up several times. The expected number of probes to look up an entry, predicted theoretically, is considerably less than for other comparable methods if the table is nearly full.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 100% of the total text.

Page 1 of 1

Modified Linear Scatter Storage Technique

A new algorithm and method for entering and retrieving information in a hash table is described. The method is intended to be efficient if most entries are looked up several times. The expected number of probes to look up an entry, predicted theoretically, is considerably less than for other comparable methods if the table is nearly full.

Let T(0),...,T(n-1) be available table positions, where n is an odd prime. Let k be a nonzero integer key. (Zero is reserved to denote an empty space in T.) If r = (k mod n) and q = (k mod (n-2)) + 1, define h(s) = (r + sq) mod n for s >/- 0.

To look up k in T we inspect T(h(0)), T(h(1)),... until, for some s, either 1) T(h(s)) = k, so k is found at position h(s); 2) T(h(s)) = 0, so T is not full and k is not in T; or 3) s > 0 and h(s) = h(0), so T is full and k is not in T.

Suppose that k is to be inserted in T. If case B arises on looking up k as above, then there is an s > 0 such that T(h(0)),..., T(h(s-1)) not = 0 and T(h(s)) =
0. Define q(i) = (T(h(i)) mod (n-2)) + 1 for i >/- 0, and h(i,j) = (j(i) + jq(i)) mod n for j >/- 1. Amongst all i and j such that T(h(i,j)) = 0, choose (i,j) to minimize i+j and, in case of a tie, to minimize i. If ikj > s, insert k by setting T(h(s)) <- k. Otherwise, insert k by setting T(h(i,j)) <- T(h(i)) and then T(h(i)) <- k.

1