Twisted Tabulation Hashing
Twisted Tabulation Hashing
复制标题
扭曲制表哈希
DOI：
10.1137/1.9781611973105.16
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
M. Thorup
中科院分区：
文献类型：
--
作者：
M. Patrascu;M. Thorup
我们引入了一种新的基于制表的哈希方案，称为“扭曲制表”。
（1）如果我们具有任意可能性的键，则具有很高的概率，任何子集中的样本数量是指数的，我们只能获得多项式的浓度，即使在基本的列表中也没有良好的限制为每个键扔（公正）硬币的情况。
（2）使用诸如线性探测和碰撞链的经典散布表，b操作的窗口需要o（b）时间，b =ω（lg n）都有较高的概率（lg n）。相当于在线系统通过大小B的缓冲区（例如，Internet路由器）处理流的在线系统。
We introduce a new tabulation-based hashing scheme called "twisted tabulation". It is essentially as simple and fast as simple tabulation, but has some powerful distributional properties illustrating its promise:
(1) If we sample keys with arbitrary probabilities, then with high probability, the number of samples inside any subset is concentrated exponentially. With bounded independence we only get polynomial concentration, and with simple tabulation, we have no good bound even in the basic case of tossing an (unbiased) coin for each key.
(2) With classic hash tables such as linear probing and collision-chaining, a window of B operations takes O(B) time with high probability, for B = Ω(lg n). Good amortized performance over any window of size B is equivalent to guaranteed throughput for an on-line system processing a stream via a buffer of size B (e.g., Internet routers).
DOI：
10.1007/978-3-642-02927-1_30
发表时间：
2009
期刊：
影响因子：
--
作者：
Martin Dietzfelbinger;Michael Rink
通讯作者：
Michael Rink
影响因子：
1.1
作者：
Martin Aumüller;Martin Dietzfelbinger;Philipp Woelfel
通讯作者：
Martin Aumüller;Martin Dietzfelbinger;Philipp Woelfel
关于使用带有简单通用哈希类的布谷鸟哈希的风险
DOI：
10.1137/1.9781611973068.87
发表时间：
2009
期刊：
影响因子：
--
作者：
Martin Dietzfelbinger;Ulf Schellbach
通讯作者：
Ulf Schellbach