c - 使用 AVL 树进行哈希处理

Question

我当时正在用 C 编写一个搜索程序。我使用了散列数据结构。我只存储了一个词一次，然后从那个词我指向了该词存在的字符串。因此，每当用户输入一个词时，将给出包含该词的所有字符串。

但是我没有使用链表，而是在散列中使用了 AVL 树。简而言之，键中的下一个节点指向 AVL 树的根。这可以将时间复杂度从 O(n) 降低到 O(log n)。

假设一个节点有数千个字符串连接在一起。将散列与 AVL 树一起使用是否好。 (我也为此尝试了 Tries 数据结构。)

有没有更好的算法？

Answer 1

Suppose one node has thousands of strings connected together. Is it good to use hashing with AVL tree.

没有。到那时，您甚至几乎不再使用哈希表了——如果您对 O(log n) 性能感到满意，请直接使用树，顶部没有哈希表。

如果您在单个哈希桶下有“数千个字符串”，那么您的哈希表就太小了——理想情况下，大多数桶中最多应该有一个对象。使用更大的哈希表来获得哈希表可以提供的 O(1) 插入/查找性能。