在那里我有一个关键的每一个元素，我不知道该元素到一个数组的索引的情况下，哈希表进行比阵列更好（O（1）VS为O（n））。

这是为什么？我的意思是：我有钥匙，我哈希它..我有散..不应该的算法比较对每个元素的hash该哈希？我认为有内存配置背后的一些诀窍，是不是？

在那里我有一个关键的每个元素的情况下，我不知道   元素到一个数组的索引，哈希表的性能比好   阵列（O（1）VS为O（n））。

哈希表搜索执行O（1）在平均情况下。在最坏的情况下，哈希表搜索执行O（N）：当你有碰撞和散列函数总是返回相同的插槽。有人可能会认为这是一个远程的情况，但一个好的分析应该考虑它。在这种情况下，你应该遍历像数组中的所有元素或链表（为O（n））。

这是为什么？我的意思是：我有钥匙，我哈希吧..我有散..   应该不是这个算法对哈希每个元素的比较   哈希？我认为有内存配置背后的一些诀窍，是不是   它？

您有钥匙，你哈希吧..你有哈希：哈希表，其中的元素是present（如果已位于前）的指标。在这一点上，你可以访问哈希表的记录在O（1）。如果负载系数小，这是不太可能看到一个以上的元素存在。所以，你看到的第一要素应该是你正在寻找的元素。否则，如果你有一个以上的元素，你必须比较的元素，你会发现你正在寻找的元素的位置。在这种情况下，你有O（1）+ O（number_of_elements）。

在一般情况下，哈希表搜索复杂度为O（1）+ O（load_factor）= 0（1 + load_factor）。

记住，load_factor =正在最坏的情况下。所以，搜索复杂性为O（n）在最坏的情况下

我不知道你用内存配置背后的猫腻的意思。在某些观点，哈希表（由链结构和碰撞分辨率）可以被认为是一个聪明的把戏。

当然，哈希表的分析结果可以通过数学证明。

In cases where I have a key for each element and I don't know the index of the element into an array, hashtables perform better than arrays (O(1) vs O(n)).

Why is that? I mean: I have a key, I hash it.. I have the hash.. shouldn't the algorithm compare this hash against every element's hash? I think there's some trick behind the memory disposition, isn't it?

In cases where I have a key for each element and I don't know the index of the element into an array, hashtables perform better than arrays (O(1) vs O(n)).

The hash table search performs O(1) in the average case. In the worst case, the hash table search performs O(n): when you have collisions and the hash function always returns the same slot. One may think "this is a remote situation," but a good analysis should consider it. In this case you should iterate through all the elements like in an array or linked lists (O(n)).

Why is that? I mean: I have a key, I hash it.. I have the hash.. shouldn't the algorithm compare this hash against every element's hash? I think there's some trick behind the memory disposition, isn't it?

You have a key, You hash it.. you have the hash: the index of the hash table where the element is present (if it has been located before). At this point you can access the hash table record in O(1). If the load factor is small, it's unlikely to see more than one element there. So, the first element you see should be the element you are looking for. Otherwise, if you have more than one element you must compare the elements you will find in the position with the element you are looking for. In this case you have O(1) + O(number_of_elements).

In the average case, the hash table search complexity is O(1) + O(load_factor) = O(1 + load_factor).

Remember, load_factor = n in the worst case. So, the search complexity is O(n) in the worst case.

I don't know what you mean with "trick behind the memory disposition". Under some points of view, the hash table (with its structure and collisions resolution by chaining) can be considered a "smart trick".

Of course, the hash table analysis results can be proven by math.