Maintaining External Memory Efficient Hash Tables
Maintaining External Memory Efficient Hash Tables
复制标题
维护外部内存高效哈希表
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Philipp Woelfel
中科院分区：
文献类型：
--
作者：
Philipp Woelfel
在哈希算法的典型应用中，要存储的数据量通常太大，无法适应内部记忆。内存。扩展PAGH的静态方案[11]我们获得了用于维护哈希表的新随机算法，可以通过恒定时间评估哈希功能o（1）连续的外部存储单元。数据结构可以在预期的摊销时间内进行更新。在静态版本（因此是最小的完美哈希函数）和动态情况中的1 – E利用率。
In typical applications of hashing algorithms the amount of data to be stored is often too large to fit into internal memory. In this case it is desirable to find the data with as few as possible non-consecutive or at least non-oblivious probes into external memory. Extending a static scheme of Pagh [11] we obtain new randomized algorithms for maintaining hash tables, where a hash function can be evaluated in constant time and by probing only one external memory cell or O(1) consecutive external memory cells. We describe a dynamic version of Pagh's hashing scheme achieving 100% table utilization but requiring (2+e)nlogn space for the hash function encoding as well as (3+e)nlogn space for the auxiliary data structure. Update operations are possible in expected constant amortized time. Then we show how to reduce the space for the hash function encoding and the auxiliary data structure to O(nloglogn). We achieve 100% utilization in the static version (and thus a minimal perfect hash function) and 1–e utilization in the dynamic case.