就技术而言，根据我在这里阅读的帖子，哈希表在最坏情况下确实需要O(n)时间来查找。但我不理解内部机制如何保证平均情况下是O(1)时间。
我的理解是，对于给定的n个元素，理想情况是有n个桶，这样可以得到O(1)的空间复杂度。这就是我卡住的地方。假设我想要查找字典中是否存在某个键，这肯定需要O(n)的时间。那么当我想要通过使用其键的哈希值来搜索哈希表中的元素时，为什么会产生差异呢？简单来说，使用原始键值进行搜索需要O(n)时间，但是使用哈希值则需要O(1)时间。为什么？
我难道不仍然需要一个一个地查找哈希值才能看到哪一个匹配吗？为什么哈希让我立即知道要检索哪个元素或是否存在这样的元素？
我认为您混淆了术语，并且通过考虑桶（buckets）使问题变得更加复杂。
让我们想象一个哈希表，它实现为长度为n的数组a。同时假设我们有n个可能的键和一个完美的哈希函数H，将每个键k映射到数组a中的唯一索引i。
我们可以通过将a中的每个值设置为nil来初始化哈希表。
我们可以通过将值放置在数组中的适当位置来将键值对(k1, v1)插入到哈希表中:
a[H(k1)] = v1
现在假设我们之后忘了 k1 是否已经在哈希表中，我们想要检查它是否在里面。为了实现这个目的，我们只需要查找 a[H(k1)] 并查看其中是否有 任何 值，即 a[H(k1)] != nil。这显然是一个常数时间的查找。
但是如果我们想要查找 v1，或者甚至一些其他的 v2 是否在哈希表中呢？这并不容易，因为我们没有函数将 vi 映射到数组中的位置，它可能与任何键相关联。所以唯一的方法是扫描整个数组，检查每个值：
for i in 0..n-1:
if a[i] == v2:
return true
return false
好问题！
假设
string 映射到 valuehashFunction(string) => hashedIndex : int 在 O(1) 的时间内完成valueArray : [any] 存储 valuevalueIndex : int 是 valueArray 中第一个空的索引lookupArray : [int] 存储每个 hashedIndex 上的 valueIndex// Setting a value
valueArray[valueIndex] = value
hashedIndex = hashFunction(string)
lookupArray[hashedIndex] = valueIndex
// Looking up a value
hashedIndex = hashFunction(string) // O(1)
valueIndex = lookupArray[hashedIndex]; // O(1) array lookup
value = valueArray[valueIndex]; // O(1) array lookup
我认为“哈希”这个词吓到了人们。在幕后，哈希表是一种数据结构，它将键/值对存储在数组中。
唯一的区别在于，我们不关心键值对的位置。这里没有索引。查找数组项O(1)。它与数组大小和位置无关。您只需输入索引号，即可检索项目。
那么查找需要多长时间才能完成呢？它是O(1)。
在哈希表中，当您存储键/值对时，键值会被哈希并存储在相应的内存槽中。
{name:"bob"} //name will be hashed
hash(name) = ab1234wq //this is the memory address
[["name","bob"]] // will be store at memory adress ab1234wq
index = hashFunction(key) % number_of_buckets（这是概念性的，实际上在现实世界中计算索引会更加复杂） - fps