Weighted Increment Linear Search for Scatter Tables

A new linear search for hash tables whose increment
step is a function of the key being addressed 
is presented.  Comparisons with known methods are given,
in terms of efficiency and computation complexity. 
 In particular, the new method applies to tables of
size n = 2^r.  It allows full table searching, and 
practically eliminates primary clustering at a very low cost.

CACM December, 1972

Luccio, F.

linear search, weighted increment search, scatter
storage, hash table, key, hash address, clustering, 
search length

3.73 3.74 4.9

CA721204 JB January 27, 1978  11:25 AM

1676	4	2251
1682	4	2251
1728	4	2251
1860	4	2251
1860	4	2251
1973	4	2251
1973	4	2251
1973	4	2251
1973	4	2251
1992	4	2251
1992	4	2251
2018	4	2251
2018	4	2251
2018	4	2251
2032	4	2251
2033	4	2251
2033	4	2251
2107	4	2251
2107	4	2251
2109	4	2251
2109	4	2251
2138	4	2251
2203	4	2251
2203	4	2251
2203	4	2251
2203	4	2251
2251	4	2251
2251	4	2251
2251	4	2251
2251	4	2251
2251	4	2251
2251	4	2251
2359	4	2251
2524	4	2251
2530	4	2251
2534	4	2251
2537	4	2251
2543	4	2251
2543	4	2251
2543	4	2251
2543	4	2251
2543	4	2251
2552	4	2251
2559	4	2251
2559	4	2251
2559	4	2251
2573	4	2251
2573	4	2251
2573	4	2251
2770	4	2251
2770	4	2251
2770	4	2251
2770	4	2251
2974	4	2251
2991	4	2251
2991	4	2251
3053	4	2251
3053	4	2251
3053	4	2251
3053	4	2251
3083	4	2251
3083	4	2251
1785	5	2251
1786	5	2251
1973	5	2251
2018	5	2251
2107	5	2251
2109	5	2251
2251	5	2251
2251	5	2251
2251	5	2251
2974	5	2251
2109	6	2251
2251	6	2251