哈希表-为什么比数组快？
如果我对每个元素都有一个键，但又不知道该元素在数组中的索引，则哈希表的性能要优于数组（O（1）vs O（n））。
这是为什么？我的意思是：我有一个密钥，我对其进行了哈希处理。.我具有哈希处理..算法不应该将此哈希与每个元素的哈希进行比较吗？我认为内存配置背后有一些技巧，不是吗？
回答：
如果我对每个元素都有一个键，但又不知道该元素在数组中的索引，则哈希表的性能要优于数组（O（1）vs O（n））。
哈希表搜索在平均情况下执行O（1）。在最坏的情况下，哈希表搜索将执行O（n）：发生冲突时，哈希函数始终返回相同的插槽。有人可能会认为“这是一个遥远的局面”，但应该经过认真分析。在这种情况下，您应该遍历数组或链接列表（O（n））中的所有元素。
这是为什么？我的意思是：我有一个密钥，我对其进行了哈希处理。.我具有哈希处理..算法不应该将此哈希与每个元素的哈希进行比较吗？我认为内存配置背后有一些技巧，不是吗？
您有一个键，您对其进行了哈希处理..您具有了哈希处理：元素存在的哈希表的索引（如果以前位于该位置）。此时，您可以访问O（1）中的哈希表记录。如果负载系数较小，则在那里看不到一个以上的元素。因此，您看到的第一个元素应该是您要寻找的元素。否则，如果您有多个元素，则必须将在该位置找到的元素与所需的元素进行比较。在这种情况下，您有O（1）+
O（number_of_elements）。
在一般情况下，哈希表搜索复杂度为O（1）+ O（load_factor）= O（1 + load_factor）。
请记住，在最坏的情况下，load_factor = n。因此，在最坏的情况下，搜索复杂度为O（n）。
我不知道“内存配置背后的技巧”是什么意思。从某些角度来看，哈希表（具有其结构和通过链接解决的冲突）可以被视为“智能技巧”。
当然，哈希表分析结果可以通过数学证明。
以上是 哈希表-为什么比数组快？ 的全部内容， 来源链接： utcz.com/qa/418201.html
