On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A mechanism is provided for constructing log-n--wise-independent hash functions that can be evaluated in O(1) time. A probabilistic argument shows that for fixed ε < 1, a table of nε random words can be accessed by a small O(1)-time program to compute one important family of hash functions. An explicit algorithm for such a family, which achieves comparable performance for all practical purposes, is also given. A lower bound shows that such a program must take Ω(k/ε) time, and a probabilistic argument shows that programs can run in O(k22) time. An immediate consequence of these constructions is that double hashing using these universal functions has (constant factor) optimal performance in time, for suitably moderate loads. Another consequence is that a T-time PRAM (parallel random-access machine) algorithm for n log n processors (and nk memory) can be emulated on an n-processor machine interconnected by an n × log n Omega network with a multiplicative penalty for total work that, with high probability, is only O(1).

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherPubl by IEEE
Pages20-25
Number of pages6
ISBN (Print)0818619821, 9780818619823
DOIs
StatePublished - 1989
Event30th Annual Symposium on Foundations of Computer Science - Research Triangle Park, NC, USA
Duration: Oct 30 1989Nov 1 1989

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

Other

Other30th Annual Symposium on Foundations of Computer Science
CityResearch Triangle Park, NC, USA
Period10/30/8911/1/89

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications'. Together they form a unique fingerprint.

Cite this