Parallel and External-Memory Construction of Minimal Perfect Hash Functions With PTHash
Parallel and External-Memory Construction of Minimal Perfect Hash Functions With PTHash
A function <inline-formula><tex-math notation="LaTeX">$f : U \to \lbrace 0,\ldots,n-1\rbrace$</tex-math></inline-formula> is a <i>minimal perfect hash function</i> for a set <inline-formula><tex-math notation="LaTeX">$S \subseteq U$</tex-math></inline-formula> of size <inline-formula><tex-math notation="LaTeX">$n$</tex-math></inline-formula> , if <inline-formula><tex-math notation="LaTeX">$f$</tex-math></inline-formula> bijectively maps <inline-formula><tex-math notation="LaTeX">$S$</tex-math></inline-formula> into the first <inline-formula><tex-math notation="LaTeX">$n$</tex-math></inline-formula> natural numbers. These functions are important for many practical applications in …