哈希表查找时间

Question

10

当我们在哈希表中插入/查找键时，教科书上说它的时间复杂度为O(1)。然而，如何可能实现O(1)的查找时间呢？如果哈希表将键存储在向量中，则需要O(N)的时间，如果存储在二叉树中，则需要O(logN)的时间。我就是无法想象某些数据结构可以具有O(1)的访问时间。

谢谢！

- Mark5907

3个回答

13

最基本的哈希表由数组和哈希函数组成。将对象添加到表中时，计算对象的哈希函数，并将其存储在该值对应的索引处的数组中。例如，如果hash(obj) = 2，则arr[2] = obj。

哈希表上的平均插入/查找时间为O(1)。

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

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

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

- Chris Dargis

2

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

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

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

- hegel5000

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ggbranch · Accepted Answer

哈希表会将您的键进行哈希处理，并放入数组中。

例如，假设哈希(x) = 3，其中x是您的键。然后哈希表会将其放入array[3]中。从数组访问的时间复杂度为O(1)。