arxiv: cs/0608037 · v3 · pith:LEXJTXGBnew · submitted 2006-08-07 · 💻 cs.DS · cs.AI

Cascade hash tables: a series of multilevel double hashing schemes with O(1) worst case lookup time

Shaohua Li This is my paper

classification 💻 cs.DS cs.AI

keywords hashtablescascadedoublehashingcaselevellookup

0 comments p. Extension

Add this Pith Number to your LaTeX paper

\usepackage{pith}
\pithnumber{LEXJTXGB}

Prints a linked pith:LEXJTXGB badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more

read the original abstract

In this paper, the author proposes a series of multilevel double hashing schemes called cascade hash tables. They use several levels of hash tables. In each table, we use the common double hashing scheme. Higher level hash tables work as fail-safes of lower level hash tables. By this strategy, it could effectively reduce collisions in hash insertion. Thus it gains a constant worst case lookup time with a relatively high load factor(70%-85%) in random experiments. Different parameters of cascade hash tables are tested.

This paper has not been read by Pith yet.

Cascade hash tables: a series of multilevel double hashing schemes with O(1) worst case lookup time

discussion (0)