为什么人们都说 Hash 表查找的时间复杂度是 O(1)?

下面是我在 Stackoverflow 上看到的回答

https://stackoverflow.com/questions/730620/how-does-a-hash-table-work

我翻译了一部分,又对一些缺少的概念添加了解释

哈希表经常通过数组与链表实现。我们设想一张存储姓名的表,在经过几次的插入之后,他可能会在内存中有如下形式。

() 中代表的是姓名的 哈希值

1
2
3
4
5
6
7
8
9
10
11
12
bucket#  bucket content / linked list

[0] --> "sue"(780) --> null
[1] null
[2] --> "fred"(42) --> "bill"(9282) --> "jane"(42) --> null
[3] --> "mary"(73) --> null
[4] null
[5] --> "masayuki"(75) --> "sarwar"(105) --> null
[6] --> "margaret"(2626) --> null
[7] null
[8] --> "bob"(308) --> null
[9] null

关键的几点:

  1. 每一个数组元素都是一个桶(bucket),刚开始是空的,引用着链表,其中包含着值(在这个例子中是名字)
  2. 每个值 (比如 fred ,哈希值是 42)都连接着 [hash % 桶的数量] 这个桶,比如 42 % 10 == [2]%取余操作符,余数是桶的编号
  3. 在同一个桶中的多个值的值可能冲突(相同),这往往是由于他们取余之后的 hash 值相同导致的(比如 42 % 10 == 2, 9282 % 10 == 2)
    • 大多数的 哈希表 都会通过比较早己经插入桶中的完整的值来处理冲突(虽然这会降低性能,却保证了没有逻辑上的错误)

链表的长度与负载系数(load factor)相关,与值的数量无关

当存储的元素增多时,表会自动扩大(创建一个更大的数组,存放更多的桶,删除旧的数组),以此来保证值的数量与桶的数量比例在 0.5 到 1.0 之前。

对于负载系数为1的加密级哈希函数, 1/e (~36.8%) 的桶是空的 另外 1/e (~36.8%)的桶有一个元素, 1/(2e) 或者 ~18.4% 的桶有连个元素, 6.1% 的桶有三个元素,1.5% 的桶有四个元素 3% 的桶有五个元素,不管元素数量多少,链表的平均长度大约是 1.58(100 个元素对应着 100 个桶,或者一亿个元素对应着一亿个桶),这也就是为什么我们 查找/插入/删除O(1) 常数的时间复杂度

什么是 负载系数(load factor)?

哈希表中的元素超过某一个限度时会自动扩张,扩张之后的数组更大,同时每个链表的长度也会更短,那么我们的 查找/插入/删除 操作就越接近与常数

更大的负载系数(0 < load factor <= 1)带来空间占用的降低,但却提高了 查找/插入/删除 的时间花费

JavaHashMap 的默认负载系数是 0.75,作为空间和时间的折中。