## Abstract

Many algorithms and

Udgivelsesdato: 2008

^{ }data structures employing hashing have been analyzed under the*uniform*assumption, i.e., the assumption that hash functions behave like^{ }hashing^{ }truly random functions. Starting with the discovery of universal hash^{ }functions, many researchers have studied to what extent this theoretical^{ }ideal can be realized by hash functions that do not^{ }take up too much space and can be evaluated quickly.^{ }In this paper we present an almost ideal solution to^{ }this problem: a hash function $h: U\rightarrow V$ that, on^{ }any set of $n$ inputs, behaves like a truly random^{ }function with high probability, can be evaluated in constant time^{ }on a RAM and can be stored in $(1+\epsilon)n\log |V|^{ }+ O(n+\log\log |U|)$ bits. Here $\epsilon$ can be chosen to^{ }be any positive constant, so this essentially matches the entropy^{ }lower bound. For many hashing schemes this is the first^{ }hash function that makes their uniform hashing analysis come true,^{ }with high probability, without incurring overhead in time or space.^{ }Udgivelsesdato: 2008

Original language | English |
---|---|

Journal | SIAM Journal on Computing |

Volume | 38 |

Issue number | 1 |

Pages (from-to) | 85-96 |

Number of pages | 12 |

ISSN | 0097-5397 |

DOIs | |

Publication status | Published - 2008 |