de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

#### Fast and Reliable Parallel Hashing

##### MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44076

Bast,  Holger
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44564

Hagerup,  Torben
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

Bast, H., & Hagerup, T. (1991). Fast and Reliable Parallel Hashing. In 3rd Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA'91) (pp. 50-61). New York, NY, USA: ACM.

A perfect hash function for a (multi)set $X$ of $n$ integers is an injective function $h:X\to\{1,\ldots,s\}$, where $s=O(n)$, that can be stored in $O(n)$ space and evaluated in constant time by a single processor. We show that a perfect hash function for a given multiset of $n$ integers can be constructed optimally in $O(\log^* n)$ time using $O(n/\log^* n)$ processors. Our algorithm is faster than all previously published methods. More significantly, it is highly reliable: Whereas analyses of previous fast parallel hashing schemes provided bounds on the expected resource requirements only, our algorithm is guaranteed to stay within the bounds given with overwhelming probability.