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() 方法

[shinehhht]

hash_map_chaining 中 extend函数在每一个桶的链表循环中要释放内存，但在put函数中为什么不需要了？Node *cur = hashMap->buckets[index];
while(cur){
if(cur->pair->key == key){
strcpy(cur->pair->val, val);
}
cur = cur->next;
}

[Gonglja]

Hi, 个人理解
extend 是扩容，是要将原有哈希表中的内容搬至扩容后的哈希表中（创建新表，释放旧表）
而 put 则是将val添加至桶中

[shinehhht]

pair->val = (char *)malloc(sizeof(strlen(val) + 1));
strcpy(pair->val, val);
pair->val[strlen(val)] = '\0';
strcpy没记错的话已经把'\0'也拷贝进去了吧？不需要 pair->val[strlen(val)] = '\0'了吧？

[Gonglja]

感谢纠正，strcpy 一种可能的实现如下，在该实现中，使用mempcpy把src中的数据拷贝到dst，并在返回的dst的末尾地址处添加\0

 char *
 stpcpy(char *restrict dst, const char *restrict src)
 {
     char  *p;

     p = mempcpy(dst, src, strlen(src));
     *p = '\0';

     return p;
 }

 char *
 strcpy(char *restrict dst, const char *restrict src)
 {
     stpcpy(dst, src);
     return dst;
 }

详见man strcpy

[Fulin-Gao]

链式地址中print好像没判断是否包含键值对，[]也会被打印

[krahets]

Hi，是哪个语言呢？

[GL0224]

python的

[]
['15937 -> 小啰']
[]
[]
['13276 -> 小法']
[]
['16750 -> 小算']
['10583 -> 小鸭']

[krahets]

这个是特意这么做的，我们将所有的桶都打印了出来

[KennyCaty]

作者您好，在链式地址中的负载因子计算，使用size/capacity，这里的capacity定义是桶数组数量是否合理？假设capacity是4，那么在一个桶中扎堆挂了四个链节点也会导致扩容，而另外三个桶其实是空着的。

[krahets]

Hi～扩容因子是常用且有效的判断依据。在你提到的例子中，虽然其他三个桶是空的，但一个桶的扎堆（哈希冲突多）也会导致性能的裂化，假设 capacity 和该桶内的元素都为 n ，那么此时这个哈希表的查询效率已经劣化至 O(n) 了，恰恰也说明需要扩容

总的来看，扩容因子反映了哈希表冲突的“整体程度”，只要这个整体程度比较高（即扩容因子比较大），无论是平均分布还是偏态分布，哈希表的性能都会变差

[KennyCaty]

感谢解答！！！

[joengtou]

大佬你好，golang溢出桶过多时会触发等量扩容，怎么保证紧凑排列后溢出桶个数一定小于再次等量扩容的条件呢，如果有桶个数无穷大，某个哈希对应的bucket存满，溢出桶也存满超出2^15个

[lys849]

g

[lys849]

打错了，我想问下：hash_map_open_addressing.py中会不会出现太过频繁删除，tombstone积累太多，导致实际储存空间减小，最后导致扩容

[krahets]

不会，添加元素时，遇到 TOMBSTONE 会覆盖，所以这部分空间仍然是可用的

[leeyiding]

线性探测部分，Go代码的put方法中，如果遇到带有删除标记的桶就插入键值，存在一种情况，即相同的键可能已经存在于该被删除桶位置之后。这种情况下，如果不继续探测以确认该键是否已存在于哈希表中，就可能会导致重复键的插入，造成空间浪费。

        // 若遇到空桶、或带有删除标记的桶，则将键值对放入该桶
        if m.buckets[j] == (pair{}) || m.buckets[j] == m.removed {
            m.buckets[j] = pair{
                key: key,
                val: val,
            }
            m.size += 1
            return
        }

测试代码

func main() {
	m := newHashMapOpenAddressing()
	m.put(0, "a")
	m.put(4, "b")
	m.put(8, "c")
	m.remove(4)
	m.put(8, "d")
	m.print()
}

$ go run hash_map_open_addressing.go
0 -> a
8 -> d
8 -> c
nil

优化之后的代码

func (m *hashMapOpenAddressing) put(key int, val string) {
    if m.loadFactor() > m.loadThres {
        m.extend()
    }

    idx := m.hashFunc(key)
    firstRemovedIdx := -1 // 记录首次遇到的被删除桶的索引，初始化为-1表示未找到

    for i := 0; i < m.capacity; i++ {
        j := (idx + i) % m.capacity

        // 如果是空桶，检查是否有遇到过被删除的桶
        if m.buckets[j] == (pair{}) {
            // 如果有，则在首次遇到的被删除的桶位置插入
            if firstRemovedIdx != -1 {
                j = firstRemovedIdx
            }
            m.buckets[j] = pair{key: key, val: val}
            m.size++
            return
        } else if m.buckets[j].key == key && m.buckets[j] != m.removed {
            // 如果找到相同的键且不是被删除的，更新值
            m.buckets[j].val = val
            return
        } else if m.buckets[j] == m.removed && firstRemovedIdx == -1 {
            // 如果是被删除的桶且是首次遇到，记录索引
            firstRemovedIdx = j
        }
    }
}

$ go run hash_map_open_addressing_opt.go 
0 -> a
-1 -> -1
8 -> d
nil

[krahets]

谢谢指出！Go 的代码不是最新的实现，我更新一下

[kkkkkLLLLLL]

发现了一个小bug

int main()
{
    HashMapOpenAddressing hoa;  // 默认4个位置

    hoa.put(0, "0"); hoa.remove(0);
    hoa.put(1, "1"); hoa.remove(1);
    hoa.put(2, "2"); hoa.remove(2);
    hoa.put(3, "3"); hoa.remove(3);
    
    // 四个 "TOMBSTONE" 在 buckets 中
    hoa.print();
    
    // forever in findBucket()
    hoa.get(0);
    
    return 0;
}

findBucket()函数需要稍微修改一下, 避免出现死循环. 例如, 在while()中判断至多将整个buckets遍历一遍.

[krahets]

确实，谢谢指出！这个简易实现的稳健性仍需提升

[bodaq99]

为啥java开放寻址的查询操作没有做线性探测

[fufu39]

对本小白来说有些晦涩难懂😭我先看看书再回来

[tron-robin]

hi，是里面的专有名词造成了障碍吗，我也有这种感觉，请问你看什么书呢

[1435646097]

习惯就好了，不理解就上网查一下概率或者问chat-gpt都是可以的

[Le1027]

您好，线性探测的目的是给键值对找个空桶放入吧？那js代码里添加键值对为什么是覆盖之前的呢？

[krahets]

Hi，如果该键值对在哈希表中已存在，则覆盖原来的

[1435646097]

相同的键，直接覆盖就好了

[shaoruijie]

链式hash C代码有个疑问（不确定是不是我理解错了）：
bucket数组大小我理解应该是对应索引数量，但是实现里我看每添加一个节点后，都会size++，那就有可能因为某些索引下挂接了多个节点，导致其他索引没用到就开始进行扩容
--- 这个是不是利用率低了呢，按我理解下挂的next节点不占数组空间吧

[krahets]

那就有可能因为某些索引下挂接了多个节点，导致其他索引没用到就开始进行扩容

是的，虽然其他索引没用到，但单条链表过长也会导致查询效率劣化（在链表中查询的时间复杂度是 O(n) ）。因此，在这种情况下扩容也是合理的

[sevenzard]

K大，有个理解问题，如图6-7，和上面的描述“删除元素会在数组内产生一个空桶 None”，
删除桶中元素后，这个桶实际上成为了空桶而不是None呀（若用列表实现桶，空桶对应空列表），当然在查询元素遍历到这个空桶时，会返回 None 作为查询结果，
我在第一遍阅读时，读到这里，就理解为“删除了元素，这个桶会被置为 None”，但实际的实现中不是这样的，所以这里的表述及图6-7是否有歧义呢？

[sevenzard]

好吧，我来自问自答了😂😂 ，是我理解错了，我以为开放寻址中哈希表中的每个桶还像链式地址那样初始化为空列表，但实际上不是，而是初始化为 None，
所以，若不考虑异常情况，删除元素的默认方式就是把对应桶置为 None，这样看，书中的描述“删除元素会在数组内产生一个空桶 None”，这句话没有错，开放寻址中，空桶的初始状态就是存放 None

[SuraRengoku]

线性寻址哈希表在扩容时，被标记为TOMBSTONE的空位应该一起搬过去吧，不然每次扩容都相当于恢复初始状态，寻址的效率和空间利用率都会变低

[zhuyihuan68]

/* 删除操作 */
public void Remove(int key) {
int index = HashFunc(key);
// 遍历桶，从中删除键值对
foreach (Pair pair in buckets[index].ToList()) {
if (pair.key == key) {
buckets[index].Remove(pair);
size--;
break;
}
}
}
其中Pair pair in buckets[index].ToList()，buckets本来就是列表 为什么还要在调用.ToList呢