基数树与哈希表

Question

我想比较哈希表和基数树。对于固定长度的键，当然，考虑到我们不关心排序顺序，哈希表总是最好的选择，但是对于可变长度的键，事情要复杂得多，所以问题将假设可变长度的键。

时间复杂度：

1. 由于哈希函数，哈希表插入时间为 O(n)。
2. 基数树插入时间据说也有 O(n)。

我尝试了以下操作，其中 data1 是“testtesttest...”，data2 是“testtesttest...2”（它们各自的长度为 40000，并且 data2 最后只有一个字符串与 data1 不同）。对于哈希表插入，唯一耗时的是哈希函数，所以我只使用哈希函数，尽管这不是大多数语言使用的 has 函数。

console.time();
radixTree.addWord(data1);
radixTree.addWord(data2);
console.timeEnd();

console.time();
keccak256(data1);
keccak256(data2);
console.timeEnd();

基本上，在基数树中添加 2 个这样的字符串需要 9 毫秒，而在哈希函数中需要 2 毫秒。您可以添加额外的开销来实际将其存储在哈希表中（因为我在这里没有使用它），但最多需要 3 毫秒。所以 9 毫秒 vs 3 毫秒。为什么说这两种算法的插入时间都是O(n)？

如果我们不关心有序集而只是构建字典，我就看不到raddix树在性能方面胜过哈希表。就内存而言，第一次创建哈希表可能会占用更多内存，但就时间复杂度而言，哈希表总是会带来更好的性能。你的想法？

只有当您将基数树与其他树进行比较并且需要有序列表时，基数树才是好的，这不是真的吗？

Answer 1

使用某种基数树（通常是大型扇出 B 树变体）而不是可变长度键的哈希表的常见原因：

• 您需要订购（正如您所指出的）
• 哈希表的复杂性是“预期的”。有时您需要限制真正最坏情况的复杂性。
• 随着哈希表的增长，有时您需要重新分配整个表。有时这是不可接受的。您可以制作增量增长的哈希表，但这很痛苦。
• 在磁盘或闪存等块结构介质上，通常使用类似 B 树的数据结构来跟踪组成文件的块。如果您可以直接访问媒体，那么您可以创建一个基数树，将 B 树块直接映射到媒体块，并且不需要这个额外的 B 树层。