浅入哈希表

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

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

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

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

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

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

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)带来空间占用的降低，但却提高了 查找/插入/删除 的时间花费

Java 的 HashMap 的默认负载系数是 0.75，作为空间和时间的折中。