Key-to-Address Transform Techniques: A Fundamental
Performance Study on Large Existing Formatted 
Files

The results of a study of eight different
key-to-address transformation methods applied to 
a set of existing files are presented.  As each method
is applied to a particular file, load factor and 
bucket size are varied over a wide range.  In addition,
appropriate variables pertinent only to a specific 
method take on different values.  The performance of
each method is summarized in terms of the number 
of accesses required to get to a record and the number
of overflow records created by a transformation. 
 Peculiarities of each method are discussed.  Practical
guidelines obtained from the results are stated. 
 Finally, a proposal for further quantitative fundamental study is outlined.

CACM April, 1971

Lum, V. Y.
Yuen, P. S. T.
Dodd, M.

hashing, hashing techniques, hashing methods, hash
coding, keys, key transformation, key-to-address 
transformation, direct addressing, direct access method,
randomizing, random access,file addressing, 
file organizations, file structures, scatter storage,
search, collisions, clusters, information retrieval

3.7 3.72 3.73 3.74 3.79 4.9

CA710402 JB February 3, 1978  4:10 PM

1676	4	2203
1682	4	2203
1728	4	2203
1785	4	2203
1785	4	2203
1860	4	2203
1860	4	2203
1973	4	2203
1973	4	2203
1973	4	2203
1973	4	2203
1992	4	2203
1992	4	2203
2018	4	2203
2018	4	2203
2018	4	2203
2032	4	2203
2033	4	2203
2033	4	2203
2107	4	2203
2107	4	2203
2109	4	2203
2109	4	2203
2138	4	2203
2203	4	2203
2203	4	2203
2203	4	2203
2203	4	2203
2203	4	2203
2203	4	2203
2251	4	2203
2251	4	2203
2251	4	2203
2251	4	2203
2359	4	2203
2524	4	2203
2530	4	2203
2537	4	2203
2543	4	2203
2543	4	2203
2543	4	2203
2543	4	2203
2552	4	2203
2552	4	2203
2559	4	2203
2559	4	2203
2573	4	2203
2573	4	2203
2770	4	2203
2770	4	2203
2860	4	2203
2974	4	2203
2991	4	2203
2991	4	2203
3053	4	2203
3053	4	2203
3053	4	2203
3083	4	2203
911	4	2203
911	5	2203
1785	5	2203
1786	5	2203
2107	5	2203
2109	5	2203
2203	5	2203
2203	5	2203
2203	5	2203
2258	5	2203
2313	5	2203
2319	5	2203
2359	5	2203
2437	5	2203
2552	5	2203
2781	5	2203
2860	5	2203
2991	5	2203
492	5	2203
911	6	2203
1328	6	2203
1408	6	2203
1719	6	2203
1749	6	2203
1751	6	2203
1785	6	2203
1785	6	2203
1785	6	2203
332	6	2203
2016	6	2203
2017	6	2203
2080	6	2203
2107	6	2203
2188	6	2203
2203	6	2203
2203	6	2203
2203	6	2203
2203	6	2203
2203	6	2203
2203	6	2203
2203	6	2203
2203	6	2203
2203	6	2203
2204	6	2203
492	6	2203