×

An ordered minimal perfect hashing scheme based upon Euler’s theorem. (English) Zbl 0567.68037

A hashing function is a function h on a key set \(K=\{k_ 1,k_ 1,...,k_ n\}\) into the set \(\{\) 1,2,3,...,m\(\}\) of locations. A hashing function can hence be considered as a mapping of a given set of records into a set of addresses. If no collisions occur and the mapping is into unique addresses a single probe is sufficient to retrieve each record. Such a transformation is called a perfect hashing function. If the cardinality of the set of records is equal to the cardinality of the address space a perfect hashing function is called a minimal perfect hashing function. As such hashing functions avoid collisions of keys and do not waste memory locations their study is of considerable importance. The author proposes a hashing scheme based upon Fermat’s number and Euler’s theorem. This hashing function stores the records in order. Furthermore it is shown that the proposed hashing scheme is a minimal perfect hashing scheme.
Reviewer: W.Janko

MSC:

68P10 Searching and sorting
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Buchholz, W., File organization and addressing, IBM Systems J., 2, 86-111 (June 1963)
[2] Cichelli, R. J., Minimal perfect hash functions made simple, Comm. ACM, 23, 17-19 (Jan. 1980)
[3] Cook, C. R.; Oldehoeft, R. R., A letter oriented minimal perfect hashing function, Sigplan Notices, 17, No. 9, 18-27 (Sept. 1982)
[4] Du, M. W.; Jea, K. F.; Shieh, D. W., The study of a new perfect hash scheme, (Proceedings, COMPSAC ’80. Proceedings, COMPSAC ’80, Chicago (Oct. 1980)), 341-347 · Zbl 0509.68063
[5] Ghosh, S. P., Data Base Organization for Data Management (1977), Academic: Academic New York · Zbl 0415.68059
[6] Hardy, G. H.; Wright, E. M., An Introduction to the Theory of Numbers (1938), Clarendon: Clarendon Oxford, Reading · Zbl 0020.29201
[7] Jaeschke, G., Reciprocal hashing: A method for generating minimal perfect hashing functions, Comm. ACM, 24, 12, 829-833 (Dec. 1981)
[8] Jaeschke, G.; Osterburg, G., On Cichelli’s minimal perfect hash functions method, Comm. ACM, 23, 728-729 (1980)
[9] Johnson, L. R., An indirect chaining method for addressing on secondary keys, Comm. ACM, 4, 5, 218-222 (May 1961)
[10] Knuth, D. E., The Art of Computer Programming, Vol. 3: Sorting and Searching (1973), Addison-Wesley: Addison-Wesley Reading, Mass · Zbl 0302.68010
[11] Lum, V. Y.; Yuan, P. S.T.; Dodd, M., Key-to-address transform techniques: A fundamental performance study on large existing formatted files, Comm. ACM, 14, 4, 228-239 (Apr. 1971)
[12] Maurer, W. D.; Lewis, T. G., Hash table method, Comput. Surveys, 7, 1, 5-19 (Mar. 1975)
[13] Morris, R., Scatter storage techniques, Comm. ACM, 11, 1, 38-44 (Jan. 1968)
[14] Olson, C. A., Random access file organization for indirectly accessed records, (Proceedings 1969 ACM 24th National Conference (1969)), 539-549
[15] Peterson, W. W., Addressing for random-access storage, IBM J. Develop., 1, 2, 130-146 (Apr. 1957)
[16] Schay, G.; Spruth, W. G., Analysis of a file addressing method, Comm. ACM, 5, 8, 459-462 (Aug. 1962)
[17] Severance, D. G., Identifier search mechanisms: A survey and generalized model, Comput. Surveys, 6, 3, 175-194 (Sept. 1974)
[18] Sprugnoli, R., Perfect hashing functions: A single probe retrieving method for static sets, Commun. ACM, 20, 11, 841-850 (Nov. 1977)
[19] Trainiter, M., Addressing for random-access storage with multiple bucket capacities, J. Assoc. Comput. Mach., 10, 3, 307-315 (July 1963)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.