知识卡片
哈希分桶不能消除碰撞
哈希函数把键映射到桶索引,帮助缩小候选范围;不同键仍可能落到同一桶。设计目标通常包括同一键的一致定位与合适的分布,而不是假定所有键都有不同哈希值。冲突处理和桶内比较属于查找的必要部分,增加桶数也不能替代它们。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 05.4 Go 语言中的哈希表 · 查看原书依据
严格来讲,哈希表这种数据结构会存储一至多个键值对,并使用一个哈希函数计算出存放正确值的桶或槽的索引。理想情况下,哈希函数应该将每个键分配到唯一的桶中,但通常你事先得有足够数量的桶。
参考来源
- 位置:《精通 Go(Mastering Go 中文版)》05.4 Go 语言中的哈希表,spine084(book-sources;extracted/精通 Go(Mastering Go 中文版)/_epub-src/05.4.html)。
- 结论依据:原文引入哈希函数与桶,后页用链表明确处理共享桶。
- 原始内容:严格来讲,哈希表这种数据结构会存储一至多个键值对,并使用一个哈希函数计算出存放正确值的桶或槽的索引。理想情况下,哈希函数应该将每个键分配到唯一的桶中,但通常你事先得有足够数量的桶。