chapter_hashing/hash_collision/

[giscus[bot]]

chapter_hashing/hash_collision/

动画图解、一键运行的数据结构与算法教程

https://www.hello-algo.com/chapter_hashing/hash_collision/

[iron-irax]

大佬，为什么这一页看不见图啊。

[krahets]

呜呜 这章的图会尽快更新的～

[Phoenix0415]

线性探测的图感觉多少有一点点confusing，感觉加一个实际的例子会好理解一点

[gltianwen]

而实际上，往往存在不同 key 对应相同 value 的情况， 这里的描述是不是容易引起歧义，应该是不同的key会产生相同的哈希值，而导致出现的问题

[krahets]

谢谢反馈！确实，可否请你点击文章右上角 铅笔图标，更新本文内容，谢谢！

[Letter24]

好像少了个平方探测

[krahets]

哈哈是的，本文只列举了两个最常见的，平方探测和线性探测的比较类似

[hakinanako]

大佬你好，我不理解为什么哈希扩容也能解决哈希冲突。
我们通过哈希函数得到索引，那不管这个数组有多大，一个key对应的索引也不会变吧，那这样扩容后不还是哈希冲突的吗

[hakinanako]

懂了谢谢！ヾ(✿ﾟ▽ﾟ)ノ

[EveningOwl]

楼主应该是认为扩容是不能解决当前遇到的某个特定key-value的哈希冲突。
但是作者的意思是扩容能从整体上降低哈希冲突出现的概率。

[krahets]

@EveningOwl 扩容可以解决几乎一切冲突，如果没解决，那就是扩容的不够多。但扩容操作太昂贵了

[yangzkalone]

扩容后，key 对应的索引也会变化，那么岂不是扩容前后通过key查询对应的桶也就不一致了么

[krahets]

@yangzkalone 扩容的时候，所有 key 的索引都需要重新计算的。

[superfeimao]

你好，冲突处理这一块没有代码实现吗？只需要知道这个结论就好了吗

[krahets]

Hi！这部分内容重点是理解优化思路和方法。加上代码可能有助于理解透彻，我后面找时间写个简易版的吧～

[GarveyH]

大佬您好，请问链式地址插入元素那里，“再将结点（即键值对）添加到链表头部即可”，为什么要插入到头部呢？尾部不可以吗？插入到链表的尾部，不是保证链表的顺序与插入顺序一致吗？

[krahets]

Hi 这个应该都行，插入到尾部的话需要额外保存一下尾结点指针，头插法相对方便。插入到头部也是有序的（倒序）。

[sunsonghao]

你好，线性探测中：“查找元素：若出现哈希冲突“。这里没太明白查找元素的时候怎么会出现冲突呢？ 输入一个key哈希函数的结果不是只有一个吗？！是插入的时候会把数组（桶）中已存在的的key的hash结果缓存，然后查找的时候先对比有冲突吗？
麻烦解答下吧，谢谢。

[krahets]

Hi～查找的时候通过哈希函数找到第一个键值对，发现 key 对不上（代表有哈希冲突，正确的键值对在下面），就根据预先设定的步长依次向下查找～

[sunsonghao]

恍然大悟，感谢！！！脑子没转过来圈

[sunsonghao]

这个书写的是真不错，逻辑清晰、图文并茂看着太舒服了，很容易就看明白了。感谢作者的辛苦付出。

[EveningOwl]

请问哈希函数一般怎么设计，比如多次哈希方法中，每个函数有什么设计思路嘛？会不会遇到一个插入操作，针对这个key所有哈希函数都冲突了情况呢？

[krahets]

这部分的内容比较多。考虑添加ing

[fallenleavesguy]

开头可以简单补充一下什么是桶，要不萌新很迷惑，我就是萌新。谢谢大佬

[fallenleavesguy]

好桶

[UFO583]

绝世好桶

[HZBTakeoff]

好好好

[rookiexxj]

大佬牛逼，清楚得一批

[blxzer77]

好桶

[Choukoo]

大佬好(●'◡'●)。请问多次哈希应该也会有不能直接删除元素的缺陷吧？另外对于标记已删除的空间，这个空间还能再次使用吗？

[krahets]

是的，多次哈希是开放寻址的一种，开放寻址法都会有不能直接删除元素的缺陷。关于你的第二个问题，被标记为已删除的空间是可以再次被使用的。当新的元素需要插入哈希表，并且通过哈希函数找到了被标记为已删除的位置时，该位置可以被新的元素使用。这样做既能保持哈希表的探测序列不变，又能保证哈希表的空间使用率。

[isotope131]

线性探测标志位是指DEFUNCT object吗？后续会更新Cockoo Hashing吗，这个也挺常见的。

[krahets]

是的，可以用一个特定的实例来标记已删除颜色。Cockoo Hashing 是开放寻址的一个变种，是个非常有趣的解决思路。我找时间加上

[kissthe]

请问在“hash_map_chaining.cpp”中的remove函数中：

1. Pair *tmp = bucket[i];
2. bucket.erase(bucket.begin() + i); // 从中删除键值对
3. delete tmp; // 释放内存

之所以需要第一行和第三行的原因是不是因为vector在创建的时候是申请的动态内存？所以在这里需要delete掉，对于STL不是很熟悉，希望能得到解答

[krahets]

Hi ，tmp 指向的 Pair 对象是存储在堆上的，需要手动释放内存。因此我们在将这个 Pair 从 bucket 中删除后，需要将它的内存释放。

[baiqinwen279]

链式地址哈希表 扩容部分没懂 标记一下下次看

[alwaysCry]

HashMapChaining 的扩容方法 extend 好像有点问题，似乎没有考虑到相同 key 在扩容后对应的实际 index 会发生改变

[alwaysCry]

合理的方法应该是：

1. 创建新 buckets
2. 双重循环遍历原 buckets，把每次得到的 pair 按重新计算的 index 插入到新 buckets 里去

[alwaysCry]

惭愧~ 看错了，作者这样的写法是没有问题的

[XiaChuerwu]

请问在 “hash_map_chaining.cpp” 的 extend() 函数中为什么将键值对从原哈希表搬运至新哈希表需要delete pair，这里的pair不是属于临时哈希表中的数据吗，它难道不是随代码块持续性的嘛，不太懂这个。

[krahets]

Hi，由于 pair 是 new 新建出来的，其存储在堆上，因此需要手动释放内存。

[Zuto-fish]

您好，这里的话可以重载一个put，直接使用原来地址，然后避免重新分配空间吗

[krahets]

@PXR-code 可以呀，实现一个复用现有 Pair 的 put() 方法

[guanshangshui]

感谢你的耐心回复，本人已经更正了表述，并且简单的介绍一下我理解的布隆过滤器，思想是与你的描述是一致的，不过关于认为布隆过滤器是一个大型数组我觉得还是存疑的是上布隆过滤器使用的应该是位图的结构，用来减少空间的开销，而且布隆过滤器只是负责判断数据是否在特定的容器当中，并不真实的存储数据

…

---Original--- From: ***@***.***> Date: Sat, Jun 28, 2025 18:57 PM To: ***@***.***>; Cc: ***@***.******@***.***>; Subject: Re: [krahets/hello-algo] chapter_hashing/hash_collision/ (Discussion#89) 从本质上来说，布隆过滤器和哈希表其实都只是一个数组而且，布隆过滤器是一个非常非常大的数组，可能长度是1000w，或者1亿，他的具体原理其实是，把一个元素，经过比如说五次哈希，得到了五个值，可能得到的值分别为，0、10、100、1000、10000，假如说是这样，然后把这个数组中对应的下标置为1，而判断布隆过滤器中是否存在一个元素，也是通过这几个哈希函数，得到五个值，然后判断这五个值对应数组中的下标是否都为1，如果都为1，那么认为布隆过滤器中存在这个元素，如果有任意一个不为1，则不存在，由于哈希冲突的存在，可能会导致两个不同的元素，经过这五次哈希得到的结果是完全一致的，也就是说，如果我判断一个数是否存在，可能会出现其实不存在，但是判断存在，也就是所谓的“误判”，而多次哈希，按照我的理解来说，是把一个数经过一次哈希函数，可能得到的结果是100，然后判断100对应的下标是否有元素，如果有，也就是发生了哈希冲突，那我就换一个哈希函数，这个时候可能得到的结果就是10，再去判断10对应的下标是否有元素，如此往复 — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you commented.Message ID: ***@***.***>

[Liul0217]

添加函数那里为什么是直接覆盖？不是要向后找空桶或者TOMBSTONE吗？🤧🤧跟前面文字描述的不一样欸？前面说的是“插入元素：通过哈希函数计算桶索引，若发现桶内已有元素，则从冲突位置向后线性遍历（步长通常为 1），直至找到空桶，将元素插入其中。”

[metahy]

findBucket()方法已经确保返回的index是和目标key相等的bucket的index了，所以添加函数中直接把目标key的新的值塞进返回的index的位置覆盖旧值即可。记住这一点：只有根据目标key计算出来的index对应的bucket中的key和目标key不同的情况才会向后找空桶或TOMBSTONE。

[crossfire6]

因为插入的key相同，可不就是要覆盖原来的值么，要不然你怎么知道你要找的元素是哪个。

[AlgoTide]

我也觉得是有问题的。C++实现方法里，https://github.com/krahets/hello-algo/discussions/89#discussioncomment-12862223这位老哥写的才正确

[yixiu2332]

哈希表的Pair中val的类型是char *，在基于数组的哈希表put时还会使用malloc先为val申请内存，为什么到后面基于链表的哈希表就不申请了，直接使用strcpy应该是错误的吧？

[yixiu2332]

对了，我说的是C语言版本

[CheShiping]

对，有误，AI叫我加上

[gqge101]

hash_map_chaining.c，put函数：

Pair *newPair = (Pair *)malloc(sizeof(Pair));
newPair->key = key;
//newPair->val未初始化，是否要加上  newPair->val= malloc(strlen(val) + 1);
strcpy(newPair->val, val);

delHashMapChaining函数：

        while (cur) {
            Node *tmp = cur;
            cur = cur->next;
           //对应上面 malloc，此处是否加上 free(tmp->pair->val);
            free(tmp->pair);
            free(tmp);
        }

[zhengads]

好抽象呀

[zhengads]

开放寻址（线性探测、平方探测和多次哈希）哈希表都存在“不能直接删除元素”的问题。

[dslh-real]

2025/12/7日 打卡

[Lingxuan-Ye]

rust 代码看得头大。包括前面几章的代码在内，建议表达一个无效索引不要用 -1_i32 了。从语义和可读性的角度，一个可能无效的索引应该用 Option<usize>，None 远比 -1 可读。如果想尽量和其它语言保持一致，至少也应该用 isize 而不是 i32。32 位最多寻址 4 GB，有符号再砍一半，文中 first_tombstone = index as i32; 在 64 位平台完全不可行。而 isize 不同，因为 rust 不允许分配超过 isize::MAX 字节，isize 是一定能寻址到所有元素的（零大小类型除外，但零大小类型不必寻址）。

另外说到代码一致性的问题，我觉得还是按各语言自己的范式来写吧，可读比一致重要。

[Lingxuan-Ye]

没仔细看代码，TOMBSTONE 是常量吗，那它应该被实现为关联常量，而不是字段。String::new 是 const fn，可以用来构建常量 TOMBSTONE。此外，这段代码怎么处理一个合法并等价于 TOMBSTONE 的键值对呢？

如果是我，我会添加一个类型来取代 Option<Pair>：

enum Bucket {
    Occupied(Pair),
    Empty,
    Tombstone,
}

[WesleyGuo-hi]

2026.1.11打卡

[shenzj0505]

我怎么感觉线性探测的findBucket方法的while循环有可能会死循环呢

[fairchild26]

不会。因为负载因子小于 1

[shenzj0505]

负载因子是size/capacity，但是size是不计算TOMBSTONE标志的。例如一个哈希数组，只有第一个元素有值，其他元素都是TOMBSTONE标志，这种情况下findBucket方法有可能会死循环的吧？

[RJH248]

我试了一下，真的会死循环！！😮😮😮

[liaoyuxia]

可以给 findBucket 加一个最多探测 capacity 次的限制，
不管有没有 null，到上限就强制退出。

[aftermathof]

index = (index + 1) % self.capacity 这一步确实有问题

[believebelief]

好难

[night-god-7158]

感觉链式地址那里进行扩容时候，最后直接进行bucket.append( ) 可能会更好一些？再调用put的话会重复进行很多运算。

[weidongweidong]

加油

[Jarvie76]

线性探测章节find_bucket方法在哈希表中没有None桶，其余桶要么是TOMBSTONE要么是非key的情况下会出现死循环，应该维护一个tombstone定期清理的机制。

[believebelief]

您的邮件，我已收到，谢谢！

[HYJ-star-del]

这个用链表实现的哈希表有缺点。在添加pair的时候。是把旧的value更新成新的value。这明显是把旧value给覆盖了。那链表的存在就没有意义了啊。

[HYJ-star-del]

哦是我理解错了，相同的key更新，不同的key放到列表（模拟链表）后面