按年被提到
20102013 · 1 次2026
算法与数据结构›哈希、压缩与向量化·arXiv:1011.5200 · cs.DS

The Power of Simple Tabulation Hashing

Mihai Patrascu, Mikkel Thorup · 2010
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2013-07-31 · 最近 2023-04-30
2不同的人
2活跃月份
2讨论串
1被引(OpenAlex)
arXiv 摘要(候选层不写导读)

Randomized algorithms are often enjoyed for their simplicity, but the hash functions used to yield the desired theoretical guarantees are often neither simple nor practical. Here we show that the simplest possible tabulation hashing provides unexpectedly strong guarantees. The scheme itself dates back to Carter and Wegman (STOC'77). Keys are viewed as consisting of c characters. We initialize c tables T_1, ..., T_c mapping characters to random hash codes. A key x=(x_1, ..., x_q) is hashed to T_1[x_1] xor ... xor T_c[x_c]. While this scheme is not even 4-independent, we show that it provides many of the guarantees that are normally obtained via higher independence, e.g., Chernoff-type concentration, min-wise hashing for estimating set intersection, and cuckoo hashing.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论csom · 2013-07

“how does it compare to, say, tabulation as in Mihai Patrascu, Mikkel Thorup: The Power of Simple Tabulation Hashing. J. ACM 59(3): 14 (2012) http://doi.acm.org/10.1145/2220357.2220361 (free version: http://arxiv.org/abs/1011.5200) or also Mihai Patrascu, Mikkel Thorup: Twisted Tabulation Hashing. SODA 2013: 209-228 http://knowledgecenter.siam.org/0236-…”

Reversing Bits in C原评论 ↗
评论tinus_hn · 2023-04

“So here’s a paper where the author has run the experiment: https://arxiv.org/pdf/1011.5200.pdf And the answer is that the speed is comparable to other functions that however produce worse results.”

Fibonacci Hashing: An Optimization the World Forgot (Better Than Integer Modulo)原评论 ↗