dictionary - 哪个更快：“基数树”或“b树”

Question

对于处理语言，如在常规字典单词中，哪个在阅读时会更快，基数树还是常规 b 树？有没有更快的方法，例如带有桶和散列的字典？

Answer 1

与往常一样，您需要在应用程序上下文中进行基准测试以确定。

但是，我希望在这种情况下，一个实现良好的哈希表可能会被证明是最快的。这基本上需要：

• 一次扫描字符串以计算哈希值，通常使用非常快速的操作，例如位移/异或
• 基于哈希值的一次哈希表查找
• 一个字符串比较以确认您有正确的单词
• 在存在哈希冲突的情况下进行一些额外处理 - 但是您可以调整哈希表大小以最小化这种情况

基数树也将非常快，由于需要遍历多个级别的树节点，因此会有一点额外的开销。如果您的树相对稀疏，则可能查找可能只需要向下少数级别即可找到唯一答案。基数树的一个优点是，如果您没有可能的匹配项，它会很早就告诉您（例如，以“qq”开头的树的空分支）

二叉树可能是最慢的，因为它平均必须搜索相当多的树节点级别。但是，对于大多数用途，它仍然足够快。