Ideal Hash Trees
Ideal Hash Trees
复制标题
理想的哈希树
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
P. Bagwell
中科院分区：
文献类型：
--
作者：
P. Bagwell
描述了具有接近理想特性的哈希树。这些哈希树不需要初始根哈希表，但速度更快，比链式或双哈希树占用的空间少得多。插入，搜索和删除的时间是小的和恒定的，独立于关键字集的大小，操作是O（1）。可以保证插入、搜索和删除操作的最坏情况时间较小，并且未命中的成本低于成功的搜索。数组映射Tries（AMT），首先在Fast and Space Efficient Trie Tries，Bagwell [2000]中描述，形成底层数据结构。然后将该概念应用于外部磁盘或分布式存储，以获得实现单次访问搜索、接近单次访问插入和大于80%的磁盘块负载因子的算法。与线性散列，Litwin，Neimat和Schneider [1993]以及B树，R.Bayer和E.M.McCreight [1972]进行了比较。此外，还简要介绍了AMT的另外两个应用，即类/类调度表和IP路由表。每个算法的性能和空间使用率与当代实现相当，但更简单。
Hash Trees with nearly ideal characteristics are described. These Hash Trees require no initial root hash table yet are faster and use significantly less space than chained or double hash trees. Insert, search and delete times are small and constant, independent of key set size, operations are O(1). Small worst-case times for insert, search and removal operations can be guaranteed and misses cost less than successful searches. Array Mapped Tries(AMT), first described in Fast and Space Efficient Trie Searches, Bagwell [2000], form the underlying data structure. The concept is then applied to external disk or distributed storage to obtain an algorithm that achieves single access searches, close to single access inserts and greater than 80 percent disk block load factors. Comparisons are made with Linear Hashing, Litwin, Neimat, and Schneider [1993] and B-Trees, R.Bayer and E.M.McCreight [1972]. In addition two further applications of AMTs are briefly described, namely, Class/Selector dispatch tables and IP Routing tables. Each of the algorithms has a performance and space usage that is comparable to contemporary implementations but simpler.