本文讨论了B树和哈希表在不同编程语言中的性能比较。点击标题
哈希表的一些缺点，比如
- 易受哈希洪水影响。
- 容易受到哈希洪水攻击、如果使用随机种子来防止哈希洪水，迭代顺序就会变得不确定，这对快照测试和可重现的构建等来说很不方便。
- 迭代顺序的不确定性、可能不得不在插入时重新散列，这对大型哈希映射会产生可怕的最坏情况延迟。
- 在 wasm 目标上，很难在不分片的情况下重复增长大型分配，因为虚拟内存技巧不可用，页面也无法解除映射。
- wasm 上的矢量指令有限，而且没有 AES 指令。 这使得许多哈希函数的运算速度大大降低。
有序数据结构（如 B 树）不存在上述任何缺点。它们通常比哈希map慢，但令我惊讶的是，人们对慢多少的预期差异很大。让我们比较一下：
- rust 的std::collections::HashMap与 siphash
- rust 的std::collections::BTreeMap
- zig 的std.HashMap与 siphash
- zig 的std.HashMap与 wyhash
- 我自己的bptree具有针对不同实验的各种编译时选项。
测试结果表明，在某些情况下，B树的性能看起来相当糟糕，但在其他情况下，B树和哈希表的性能差异要小得多。作者还探讨了为什么会出现这样的差异，并提出了一些关于如何优化B树性能的想法。
上述所有基准测试基本上都是最佳情况，即我们连续进行大量查找。如果我们只是在其他工作中间进行一次查找，那么 btree 可能根本不在缓存中，并且每级 2.5 次缓存查找都会一直转到主内存。这是灾难性的。而开放地址哈希map通常每次查找只会命中 1 或 2 个缓存行，无论大小如何。
尽管 btree 避免了 hashmap 的许多性能边缘情况，但随着比较变得更加昂贵并且占用更多内存，它们也会出现一些自身的问题，就像我们在上面看到的随机字符串一样。
文章还讨论了在wasm上的性能，由于wasm上没有像x86那样的快速向量指令，哈希函数通常会更慢。作者还提到了一些关于B树调整的实验，包括节点大小、键值存储方式、搜索算法等。
对于小型Map来说，空间使用率也确实很糟糕。我需要添加一些额外的调整，以允许 Btree 根节点从小处开始并逐渐增大，而不是为只有 1 个键的Map支付全部 512 字节。
最后，作者得出结论，对于他正在设计的语言来说，继续探索B树可能不值得，他可能会坚持使用哈希表。要么按插入顺序进行迭代，要么在迭代之前对条目进行排序。