algorithm - 在什么情况下我应该使用尝试而不是二叉树/哈希表？

Question

键通常是字符串这一事实是否使其对string数据集合更有用？我知道哈希表使用的空间更少，因为它分配了一块内存，而不是为每个字符串的每个字符分配内存。

在搜索方面，O(m) 是最坏的情况，其中 m 是密钥的长度。二叉树搜索是 O(log n)，所以我想我应该根据情况比较哪个更有效？

PS 在您投票结束之前，这不是一个意见问题。我需要有关数据结构的真实事实来做出最佳选择。

谢谢

Answer 1

您必须根据用例来决定要查找的内容。就事实而言，我们应该牢记以下几点。

1. HashTable 存储 key 的数据，只有当你想搜索特定的字符串时才可以使用它。因此，如果要搜索所有以 K 开头的字符串，则必须迭代整个 Hashtable，并且在向 table 中插入数据时，顺序信息也会丢失。

2. 就 BST 的考虑而言，在其中存储字符串很容易，并且它会按照自然顺序存储字符串，但是在每个节点上都必须匹配所有字符，从搜索时间的角度来看，这并不好.

3. 现在来到 Trie，不像 Hashtable 和 BST，Trie 从存储的角度来看并不好，而且会占用太多空间，但从搜索的角度来看，它要快得多。

再一次，这完全取决于你想买什么以及以什么价格购买，基于此，你可以选择 Hashtable、BST、Trie 或 SuffixTree。