Two-Way Chaining with Reassignment
Two-Way Chaining with Reassignment
复制标题
带重新分配的双向链接
DOI：
10.1137/s0097539704443240
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
E. McLeish
中科院分区：
文献类型：
--
作者：
Ketan Dalal;L. Devroye;Ebrahim Malalla;E. McLeish
我们提出一种算法，用于将$\lfloor\alpha n\rfloor$个元素散列到具有$n$个独立链表的表中，对于常数$\alpha$，该算法在确定性最坏情况下的插入时间为$O(1)$，在期望最坏情况下的搜索时间为$O(1)$。我们在技术中利用了双向链表和随机图论之间的联系。
We present an algorithm for hashing $\lfloor \alpha n \rfloor$ elements into a table with n separate chains that requires O(1) deterministic worst-case insert time and O(1) expected worst-case search time for constant $\alpha$. We exploit the connection between two-way chaining and random graph theory in our techniques.