chapter_hashing/hash_collision/ #89
Replies: 124 comments 161 replies
|
大佬,为什么这一页看不见图啊。 |
|
而实际上,往往存在不同 key 对应相同 value 的情况, 这里的描述是不是容易引起歧义,应该是不同的key会产生相同的哈希值,而导致出现的问题 |
|
好像少了个平方探测 |
|
大佬你好,我不理解为什么哈希扩容也能解决哈希冲突。 |
|
你好,冲突处理这一块没有代码实现吗?只需要知道这个结论就好了吗 |
|
大佬您好,请问链式地址插入元素那里,“再将结点(即键值对)添加到链表头部即可”,为什么要插入到头部呢?尾部不可以吗?插入到链表的尾部,不是保证链表的顺序与插入顺序一致吗? |
|
你好,线性探测中:“查找元素:若出现哈希冲突“。这里没太明白查找元素的时候怎么会出现冲突呢? 输入一个key哈希函数的结果不是只有一个吗?!是插入的时候会把数组(桶)中已存在的的key的hash结果缓存,然后查找的时候先对比有冲突吗? |
|
请问哈希函数一般怎么设计,比如多次哈希方法中,每个函数有什么设计思路嘛?会不会遇到一个插入操作,针对这个key所有哈希函数都冲突了情况呢? |
|
开头可以简单补充一下什么是桶,要不萌新很迷惑,我就是萌新。谢谢大佬 |
|
大佬好(●'◡'●)。请问多次哈希应该也会有不能直接删除元素的缺陷吧?另外对于标记已删除的空间,这个空间还能再次使用吗? |
|
线性探测标志位是指DEFUNCT object吗?后续会更新Cockoo Hashing吗,这个也挺常见的。 |
|
请问在“hash_map_chaining.cpp”中的remove函数中:
之所以需要第一行和第三行的原因是不是因为vector在创建的时候是申请的动态内存?所以在这里需要delete掉,对于STL不是很熟悉,希望能得到解答 |
|
链式地址哈希表 扩容部分没懂 标记一下下次看 |
|
HashMapChaining 的扩容方法 extend 好像有点问题,似乎没有考虑到相同 key 在扩容后对应的实际 index 会发生改变 |
|
请问在 “hash_map_chaining.cpp” 的 extend() 函数中为什么将键值对从原哈希表搬运至新哈希表需要delete pair,这里的pair不是属于临时哈希表中的数据吗,它难道不是随代码块持续性的嘛,不太懂这个。 |
|
感谢你的耐心回复,本人已经更正了表述,并且简单的介绍一下我理解的布隆过滤器,思想是与你的描述是一致的,不过关于认为布隆过滤器是一个大型数组我觉得还是存疑的是上布隆过滤器使用的应该是位图的结构,用来减少空间的开销,而且布隆过滤器只是负责判断数据是否在特定的容器当中,并不真实的存储数据
…---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: ***@***.***>
|
|
添加函数那里为什么是直接覆盖?不是要向后找空桶或者TOMBSTONE吗?🤧🤧跟前面文字描述的不一样欸?前面说的是“插入元素:通过哈希函数计算桶索引,若发现桶内已有元素,则从冲突位置向后线性遍历(步长通常为 1),直至找到空桶,将元素插入其中。” |
|
哈希表的Pair中val的类型是char *,在基于数组的哈希表put时还会使用malloc先为val申请内存,为什么到后面基于链表的哈希表就不申请了,直接使用strcpy应该是错误的吧? |
|
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);
} |
|
好抽象呀 |
|
2025/12/7日 打卡 |
|
rust 代码看得头大。包括前面几章的代码在内,建议表达一个无效索引不要用 另外说到代码一致性的问题,我觉得还是按各语言自己的范式来写吧,可读比一致重要。 |
|
2026.1.11打卡 |
|
我怎么感觉线性探测的findBucket方法的while循环有可能会死循环呢 |
|
好难 |
|
感觉链式地址那里进行扩容时候,最后直接进行bucket.append( ) 可能会更好一些?再调用put的话会重复进行很多运算。 |
|
加油 |
|
线性探测章节find_bucket方法在哈希表中没有None桶,其余桶要么是TOMBSTONE要么是非key的情况下会出现死循环,应该维护一个tombstone定期清理的机制。 |
|
您的邮件,我已收到,谢谢!
|
|
这个用链表实现的哈希表有缺点。在添加pair的时候。是把旧的value更新成新的value。这明显是把旧value给覆盖了。那链表的存在就没有意义了啊。 |
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
chapter_hashing/hash_collision/
动画图解、一键运行的数据结构与算法教程
https://www.hello-algo.com/chapter_hashing/hash_collision/
All reactions