Hash Table 与 AVLTrees 等其他数据结构
Hash Table vs Other data structures like AVLTrees
我正在研究 Hash Table 和 AVLTree 的复杂性。从理论上讲，在 Hash Tables 上插入和删除元素的复杂性是 O(1)，对于 AVLTree O(log(n))（研究工作流的复杂性是数据结构上的元素数量） ，看到这个结果 Hash Tables 似乎比 AVLTrees 更好，但是如果我们考虑到结构本身的大小和计算给定键的哈希函数所需的时间，AVLTrees 不是更好吗？
哈希 table 和 AVL 树提供根本不同的功能。简而言之，散列table用于查找，而树结构用于搜索和遍历。
散列 table 使您可以非常快速地检索与各个键关联的值。如果您使用 "xqj57" 键插入了一个值，那么您可以快速检索它。如果 "xqj57" 没有被插入，查找会说不存在这样的记录。插入和查找都是O(1)操作。
AVL 树和类似的结构非常适合按排序顺序存储内容。这使您可以按排序顺序遍历结构，还可以让您轻松地按顺序检索键以 "A" 开头的所有记录，或获取键大于或等于 [= 的第一条记录29=]，等等。插入和查找是O(log n)操作。遍历当然是O(n).
如果要按排序顺序遍历哈希 table，则必须先对其进行排序。
与树结构相比，散列 table 确实有一点额外的内存开销，但 没有那么多。
除非键特别长，或者您的散列函数非常复杂，否则计算键的散列值的成本比您必须进行的 log(n) 键比较的成本低在树结构中找到一些东西。
如果您只想快速插入和查找，那么很难击败哈希 table。如果您想使用排序列表，那么散列 table 绝对不是正确的选择。 AVL 树、红黑树、跳跃列表或其他此类排序结构的性能会更好。
我正在研究 Hash Table 和 AVLTree 的复杂性。从理论上讲，在 Hash Tables 上插入和删除元素的复杂性是 O(1)，对于 AVLTree O(log(n))（研究工作流的复杂性是数据结构上的元素数量） ，看到这个结果 Hash Tables 似乎比 AVLTrees 更好，但是如果我们考虑到结构本身的大小和计算给定键的哈希函数所需的时间，AVLTrees 不是更好吗？
哈希 table 和 AVL 树提供根本不同的功能。简而言之，散列table用于查找，而树结构用于搜索和遍历。
散列 table 使您可以非常快速地检索与各个键关联的值。如果您使用 "xqj57" 键插入了一个值，那么您可以快速检索它。如果 "xqj57" 没有被插入，查找会说不存在这样的记录。插入和查找都是O(1)操作。
AVL 树和类似的结构非常适合按排序顺序存储内容。这使您可以按排序顺序遍历结构，还可以让您轻松地按顺序检索键以 "A" 开头的所有记录，或获取键大于或等于 [= 的第一条记录29=]，等等。插入和查找是O(log n)操作。遍历当然是O(n).
如果要按排序顺序遍历哈希 table，则必须先对其进行排序。
与树结构相比，散列 table 确实有一点额外的内存开销，但 没有那么多。
除非键特别长，或者您的散列函数非常复杂，否则计算键的散列值的成本比您必须进行的 log(n) 键比较的成本低在树结构中找到一些东西。
如果您只想快速插入和查找，那么很难击败哈希 table。如果您想使用排序列表，那么散列 table 绝对不是正确的选择。 AVL 树、红黑树、跳跃列表或其他此类排序结构的性能会更好。