zbMATH — the first resource for mathematics

Universal classes of hash functions. (English) Zbl 0412.68090

68P20 Information storage and retrieval of data
68R99 Discrete mathematics in relation to computer science
68P05 Data structures
Full Text: DOI
[1] Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, Mass · Zbl 0286.68029
[2] {\scR. FAGIN, J. NIEVERGELT, N. PIPPENGER, AND H. R. STRONG}, “Extendible Hashing: A Fast Access Method for Dynamic Files,” IBM Research Report RJ 2305.
[3] Gill, J.T., Computational complexity of probabilistic Turing machines, (), 91-95, Seattle, Wash.
[4] {\scE. Goto, Y. Kanada}, Hashing lemmas on time complexities with applications to formula manipulation, in “Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation,” Yorktown Heights, N. Y., pp. 149-153. · Zbl 0453.68011
[5] {\scF. GUSTAVSON AND D. Y. Y. YUN}, Arithmetic complexity of unordered or sparse polynomials, in “Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation,” Yorktown Heights, N. Y., pp. 154-159. · Zbl 0453.68012
[6] Knuth, D.E., ()
[7] {\scG. MARKOWSKY, J. L. CARTER, AND M. N. WEGMAN}, Analysis of a universal class of hash functions, in “Proceedings of the Seventh Mathematical Foundations of Computer Science Conference”, Lecture Notes in Computer Science, Vol. 64, Springer-Verlag, Berlin. · Zbl 0383.68079
[8] Rabin, M.O., Probabilistic algorithms, (), 21-39
[9] Rosenbaum, W.S.; Hilliard, J.J., Multifont OCR postprocessing system, IBM J. res. develop., 19, 398-421, (1975)
[10] {\scD. H. A. SMITH}, private communication.
[11] Solovay, R.; Strassena, V., A. fast Monte-Carlo test for primality, SIAM J. comput., 6, 84-86, (1977) · Zbl 0345.10002
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.