data-structures - 哈希表与其他数据结构，如 AVLTrees

Question

我正在研究 Hash Table 和 AVLTree 的复杂性。理论上，在 Hash Tables 上插入和删除元素的复杂度是 O(1)，对于 AVLTree O(log(n))（研究工作流的复杂性是数据结构上的元素数量），看到这个结果 Hash表似乎比 AVLTrees 更好，但如果我们考虑到结构本身的大小和计算给定键的散列函数所需的时间，难道 AVLTrees 不是更好吗？

标签： data-structureshashtableavl-tree

Answer 1

哈希表和 AVL 树具有根本不同的功能。简而言之，哈希表用于查找，而树结构用于搜索和遍历。

哈希表使您可以非常快速地检索与单个键关联的值。如果您使用键“xqj57”插入了一个值，那么您可以快速检索它。如果没有插入“xqj57”，查找将说不存在这样的记录。插入和查找都是 O(1) 操作。

AVL 树和类似结构非常适合按排序顺序存储事物。这使您可以按排序顺序遍历结构，还可以轻松地按顺序检索键以“A”开头的所有记录，或获取键大于或等于“foo”的第一条记录，等等。插入和搜索是 O(log n) 操作。当然，遍历是 O(n)。

如果要按排序顺序遍历哈希表，则必须先对其进行排序。

与树结构相比，哈希表确实有一点额外的内存开销，但没有那么多。

除非键特别长，或者您的散列函数非常复杂，否则计算键的散列值的成本与您必须执行的 log(n) 键比较的成本相比要便宜结构体。

如果您只想快速插入和查找，那么很难击败哈希表。如果您想使用排序列表，那么哈希表绝对不是要走的路。AVL 树、红黑树、跳过列表或其他此类排序结构将表现更好。