J. Lawrence Carter
ABSTRACT
This paper gives an input independent average linear time algorithm for storage and retrieval on keys. The algorithm makes a random choice of hash function from a suitable class of hash functions. Given any sequence of inputs the expected time (averaging over all functions in the class) to store and retrieve elements is linear in the length of the sequence. The number of references to the data base required by the algorithm for any input is extremely close to the theoretical minimum for any possible hash function with randomly distributed inputs. We present three suitable classes of hash functions which also may be evaluated rapidly. The ability to analyze the cost of storage and retrieval without worrying about the distribution of the input allows as corollaries improvements on the bounds of several algorithms.
- 1.Aho, A.V., Hopcroft, J.E., and Ullman, J.D., The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass. (1974). Google Scholar
Digital Library
- 2.Gill, J.T., III, Computational Complexity of Probabilistic Turing Machines, Proceedings of the Sixth ACM Symposium on the Theory of Computing, May, 1976, Seattle, Washington, p. 91-95. Google ScholarDigital Library
- 3.Goto, E., and Kanada, Y., Hashing Lemmas on Time Complexities with Applications to Formula Manipulation, Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation, August, 1976, Yorktown Heights, New York, p.149-153. Google ScholarDigital Library
- 4.Gustavson, F., and Yun, D.Y.Y., Arithmetic Complexity of Unordered or Sparse Polynomials Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation, August, 1976, Yorktown Heights, New York, p.154-159. Google ScholarDigital Library
- 5.Knuth, D.E., Sorting and Searching, Addison-Wesley, Reading, Mass. (1973).Google Scholar
- 6.Markowsky, G., private communication.Google Scholar
- 7.Rabin, M.O., Probabilistic algorithms, Proceedings of Symposium on New Directions and Recent Results in Algorithms and Complexity (1976-to appear).Google Scholar
- 8.Rosenbaum, W.S., and Hilliard, J.J., Multifont OCR postprocessing system. IBM Journal of Research and Development (July 1975).Google Scholar
- 9.Strassen, V., and Solovay, R., A fast Monte-Carlo test for primality, SIAM Journal on Computing (to appear).Google Scholar
Index Terms
- Universal classes of hash functions (Extended Abstract)
Recommendations
Universal Functions for Classes of Bilinear and Polylinear Boolean Functions
The following problem is considered: specify a Boolean function of n variables such that every bilinear (polylinear) function is reduced, on a certain number of tuples of the specified function, to a unique bilinear (polylinear) function that is ...
Evolving universal hash functions using genetic algorithms
GECCO '09: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking PapersIn this paper we explore the use of metaheuristic functions, namely Genetic Algorithms to construct Universal Hash Functions to efficiently hash a given set of keys. The Hash Functions generated in this way should give lesser number of collisions as ...
Three classes of balanced vectorial semi-bent functions
AbstractSemi-bent functions play an important role in symmetric ciphers and sequence designs. So far, there are few studies related to the construction of vectorial semi-bent functions even though lots of work has been done on single-output semi-bent ...
Comments