hashtable - 哈希表查找时间

Question

当我们在哈希表中插入/查找键时，教科书说这是 O(1) 时间。然而，怎么可能有一个 O(1) 的查找时间呢？如果哈希表将键存储在向量中，它将花费 O(N)，如果在二叉树中，它将花费 O(logN)。我只是无法用 O(1) 访问时间来成像某些数据结构。

谢谢！

Answer 1

哈希表对您的密钥进行哈希处理并将其放入数组中。

例如，hash(x) = 3，其中 x 是您的密钥。然后该表将其放入数组 [3]。从数组访问是 O(1)。

Answer 2

哈希表至少由数组和哈希函数组成。当一个对象被添加到表中时，会对该对象计算哈希函数，并将其存储在数组中所计算的相应值的索引处。例如，如果hash(obj) = 2那么arr[2] = obj。

哈希表上的平均插入/查找是O(1).

但是，当对象计算相同的哈希值时，可能会发生冲突。

在一般情况下，数组的每个索引处都有“桶”来处理这些冲突。这意味着，所有三个对象都存储在哈希表索引处的某个其他数据结构（可能是链表或另一个数组）中。

因此，在哈希表上查找的最坏情况是O(n)因为存储在哈希表中的所有对象都可能发生冲突并存储在同一个桶中。

Answer 3

从技术上讲，哈希表查找，如果没有冲突，是 O(logn)。这是因为散列时间与标识符的大小（以字节为单位）成线性关系，并且添加到散列表中的新标识符可以是最小的，对于该标识符是唯一的，是 O(logn)。

然而，世界上所有计算机内存的日志只是一个很小的数字，这意味着我们对哈希表标识符大小有很好的上限。例如，可观测宇宙中粒子数的 log10 估计略高于 80；在 log2 中大约是 3.3 倍。对数增长非常缓慢。

因此，大多数对数项可以被视为常数项。只是传统上我们只将这个事实应用于哈希表，而不是搜索树，以便向学生教授递归关系。