在我为每个元素都有一个键并且我不知道数组中元素的索引的情况下，哈希表的性能优于数组（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)。
我不知道您所说的“内存配置背后的技巧”是什么意思。在某些观点下，哈希表（具有其结构和通过链接解决冲突）可以被认为是一种“聪明的技巧”。
当然，哈希表的分析结果可以用数学来证明。