知识卡片
双重散列探测冲突位置
计数 ID 哈希到数组时发生冲突,可用两个哈希值生成一串探测位置:(h1 + h2*s) % tsize。查询沿与插入相同的序列寻找 ID,避免为每项保存额外链指针;容量与哈希质量仍决定探测长度和冲突概率。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 计数系统设计(一):面对海量数据的计数器要如何做? · 查看原书依据
pos = (h1 + h2*s) % tsize //如果发生冲突,就多算几次Hash2
参考来源
- 位置:《高并发系统设计40问》第37讲《计数系统设计(一):面对海量数据的计数器要如何做?》(源文件:_epub-src/text/part0042_split_003.html)
- 结论依据:原文给出 h1、h2 和探测序列公式,插入时寻找空位、查询时复用同一位置序列比对 ID,因此能推出双重散列用于解决哈希冲突。
- 原始内容:pos = (h1 + h2*s) % tsize //如果发生冲突,就多算几次Hash2