知识卡片
负载因子限定平均链长
若 n 个元素较均匀地分散在 k 个桶,平均链长是 n/k,一次查找的期望工作量可按 O(1+n/k) 理解,还要计入哈希和比较成本。该估计不是查找全部 n 个键的总成本,也不是最坏保证;若全落一桶,单次扫描可达 O(n)。原例 120 个连续整数对 15 取模均分,只说明这组输入。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 05.4.3 哈希表的优点 · 查看原书依据
,查找 n 个键的时间复杂度将从使用线性查找的 O(n) 下降至 O(n/k)!尽管这点改进看起来不起眼,你也必须意识到对于一个有 20 个槽的哈希数组,查找的次数将会下降为原来的 1/20!这让哈希表非常适合用于搭建词典或者其他这类需要大量数据查找的应用。
参考来源
- 位置:《精通 Go(Mastering Go 中文版)》05.4.3 哈希表的优点,spine087(book-sources;extracted/精通 Go(Mastering Go 中文版)/_epub-src/05.4.3.html)。
- 结论依据:原文 n/k 估计结合120值15桶例子,明确平均、单次及最坏情况边界。
- 原始内容:,查找 n 个键的时间复杂度将从使用线性查找的 O(n) 下降至 O(n/k)!尽管这点改进看起来不起眼,你也必须意识到对于一个有 20 个槽的哈希数组,查找的次数将会下降为原来的 1/20!这让哈希表非常适合用于搭建词典或者其他这类需要大量数据查找的应用。