知识卡片

问题卡 · 2274.e.1.a.6.e.19.a.10

双重散列探测冲突位置

理解等级:未标注

计数 ID 哈希到数组时发生冲突,可用两个哈希值生成一串探测位置:(h1 + h2*s) % tsize。查询沿与插入相同的序列寻找 ID,避免为每项保存额外链指针;容量与哈希质量仍决定探测长度和冲突概率。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《高并发系统设计40问》第37讲《计数系统设计(一):面对海量数据的计数器要如何做?》(源文件:_epub-src/text/part0042_split_003.html) - 结论依据:原文给出 h1、h2 和探测序列公式,插入时寻找空位、查询时复用同一位置序列比对 ID,因此能推出双重散列用于解决哈希冲突。 - 原始内容:pos = (h1 + h2*s) % tsize //如果发生冲突,就多算几次Hash2