Open taikulawo opened 5 years ago
下面是我在 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
关键的几点:
桶(bucket)
(在这个例子中是名字)
fred
[hash % 桶的数量]
42 % 10 == [2]
%
取余操作符
(相同)
hash
(比如 42 % 10 == 2, 9282 % 10 == 2)
(虽然这会降低性能,却保证了没有逻辑上的错误)
当存储的元素增多时,表会自动扩大(创建一个更大的数组,存放更多的桶,删除旧的数组),以此来保证值的数量与桶的数量比例在 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) 常数的时间复杂度
1/e (~36.8%)
1/(2e)
~18.4%
6.1%
1.5%
3%
1.58
查找/插入/删除
O(1)
哈希表中的元素超过某一个限度时会自动扩张,扩张之后的数组更大,同时每个链表的长度也会更短,那么我们的 查找/插入/删除 操作就越接近与常数
更大的负载系数(0 < load factor <= 1)带来空间占用的降低,但却提高了 查找/插入/删除 的时间花费
(0 < load factor <= 1)
Java 的 HashMap 的默认负载系数是 0.75,作为空间和时间的折中。
Java
HashMap
0.75
啊哈哈哈哈哈
哦耶,测试测试
为什么人们都说 Hash 表查找的时间复杂度是 O(1)?
下面是我在 Stackoverflow 上看到的回答
https://stackoverflow.com/questions/730620/how-does-a-hash-table-work
我翻译了一部分,又对一些缺少的概念添加了解释
哈希表经常通过数组与链表实现。我们设想一张存储姓名的表,在经过几次的插入之后,他可能会在内存中有如下形式。
()
中代表的是姓名的 哈希值关键的几点:
桶(bucket)
,刚开始是空的,引用着链表,其中包含着值(在这个例子中是名字)
fred
,哈希值是 42)都连接着[hash % 桶的数量]
这个桶,比如42 % 10 == [2]
,%
是取余操作符
,余数是桶的编号(相同)
,这往往是由于他们取余之后的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
,作为空间和时间的折中。