14

我需要知道三叉树是否比哈希表更好。

我在回答另一个问题时遇到了这个问题，有人说三叉树通常比哈希表快。我发现这很难相信，所以我决定研究一下。

普林斯顿的这个网站似乎是这种信念的来源。我查看了描述为 O(log n + k) 的算法，其中 n 是存储的单词数，k 是密钥的长度。

在我看来，这可能更快的唯一方法是如果您经常搜索尚未存储的元素。另一件困扰我的事情是，不连续爬取 trie 往往会导致您点击已换出的页面，但这是否是主要影响只能通过基准测试才能看到。

现在我知道它们可能各有利弊，如果是这样，我想知道它们是什么。基准测试也很有帮助。

4

5 回答 5

7

以下是我从您提供的普林斯顿链接可访问的Dobbs 博士文章中收集到的内容：

  1. 在某些搜索问题上，三叉搜索树比哈希表快 10%。它们有时速度较慢 - 很大程度上取决于所使用的机器。
  2. TRT 是一种自定义数据结构，由计算机科学界的两位最优秀的头脑 - Jon Bentley 和 Robert Sedgewick 调整，他们都编写了很好的 教科书，并在实际编程方面做了他们的贡献。哈希表被认为是普通的。
  3. 正如 Hao Wooi Lin 所说，所涉及的常数很重要。
  4. 总的来说，这取决于您要解决的问题。在许多编程语言中，更快的开发时间和对哈希表的几乎无处不在的支持通常比运行时间提高 10% 更重要。
于 2009-05-05T07:53:56.400 回答
4

回答这个问题的唯一方法是凭经验。答案取决于您的实现细节、您执行的搜索类型、您拥有的硬件以及您使用的编译器。您可以从普林斯顿复制 C 代码。如果你想尝试一种函数式语言，标准 ML 有哈希表（查看SML/NJ），这里有一些用于三元搜索树的 ML：

type key = Key.ord_key
type item = Key.ord_key list

datatype set = NODE of { key : key, lt : set, eq : set, gt : set }
             | LEAF

val empty = LEAF

fun member (_, LEAF) = false
  | member (h::t, NODE {key, lt, eq, gt}) =
      (case Key.compare (h, key)
         of EQUAL   => member(t, eq)
          | LESS    => member(h::t, lt)
          | GREATER => member(h::t, gt))
  | member ([], NODE {key, lt, eq, gt}) =
      (case Key.compare (Key.sentinel, key)
         of EQUAL   => true
          | LESS    => member([], lt)
          | GREATER => member([], gt))

exception AlreadyPresent

fun insert(h::t, LEAF) =
      NODE { key = h, eq = insert(t, LEAF), lt = LEAF, gt = LEAF }
  | insert([], LEAF) =
      NODE { key = Key.sentinel, eq = LEAF, lt = LEAF, gt = LEAF }
  | insert(h::t, NODE {key, lt, eq, gt}) =
      (case Key.compare (h, key)
         of EQUAL   => NODE {key = key, lt = lt, gt = gt, eq = insert(t, eq)}
          | LESS    => NODE {key = key, lt = insert(h::t, lt), gt = gt, eq = eq}
          | GREATER => NODE {key = key, lt = lt, gt = insert(h::t, gt), eq = eq})
  | insert([], NODE {key, lt, eq, gt}) =
      (case Key.compare (Key.sentinel, key)
         of EQUAL   => raise AlreadyPresent
          | LESS    => NODE {key = key, lt = insert([], lt), gt = gt, eq = eq}
          | GREATER => NODE {key = key, lt = lt, gt = insert([], gt), eq = eq})

fun add(l, n) = insert(l, n) handle AlreadyPresent => n
于 2009-05-07T03:16:22.553 回答
1

log(n) 增长得足够慢，因此在考虑常数因素时，它通常需要大量数据才能比 O(1) 算法慢。

于 2009-05-05T08:02:56.220 回答
0

这对我来说也很有趣。但是从我阅读的 wiki 中，它声称三叉树在大多数搜索问题上都更快。这并不奇怪，因为即使哈希表具有 O(1) 查找，您仍然需要时间进行哈希处理。所以它不是真正的 O(1)，而是更像 O(k)，其中 k 不依赖于 N（数据结构中的项目数）。这可能会给人一种哈希表更快的印象。但是，如果您正在处理大型结构，k 很快就会加起来，并且会出现哈希表的搜索速度变得比三叉树慢的点。

于 2009-05-05T07:45:38.057 回答
0

你可以看看 tstdb：http ://code.google.com/p/tstdb/

这个 kv-store 基于三元搜索树，它与 Memcached 兼容。此外，tstdb 支持前缀搜索和范围查询，这些都是由三元搜索树提供的。

于 2012-03-04T06:57:48.167 回答