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

[zmkm11]

您好，在Java示例中，这样这样遍历 list 过程中删除 list 的元素，是可能会报错 ConcurrentModificationException 异常的(当删除的是 list 的最后一个元素时)，可以使用迭代器 iterator 删除。
// 遍历桶，从中删除键值对
for (Pair pair : bucket) {
if (pair.key == key) {
bucket.remove(pair);
size--;
break;
}
}

[zmkm11]

/**

• 数组 + 链表实现哈希表
• 每个数组元素都是一条链表；

/
/ 链式地址哈希表 */
public class HashMapLinkedListChaining {

/* 键值对 */
class Pair {
    private int key;
    private String value;

    public Pair(int key, String value) {
        this.key = key;
        this.value = value;
    }
}

class ListNode {
    private Pair pair;
    private ListNode next;

    public ListNode(int key, String value) {
        this.pair = new Pair(key, value);
        next = null;
    }

}

// 键值对数量
private int size;
// 哈希表容量
private int capcaity;
// 触发扩容的负载因子阈值
private final double loadThres = 2.0 / 3.0;
// 扩容倍数
private final int extendRatio = 2;
// 桶数组
private ListNode[] buckets;


/* 构造方法 */
public HashMapLinkedListChaining() {
    size = 0;
    capcaity = 4;
    buckets = new ListNode[capcaity];
}

/* 哈希函数 */
private int hashFunc(int key) {
    return key % capcaity;
}

/* 负载因子 */
private double loadFactor() {
    return (double) size / capcaity;
}

/* 查询操作 */
public String get(int key) {
    int index = hashFunc(key);
    ListNode node = buckets[index];
    // 先根据 key 找到对应的 index 下标链表 ListNode，然后判断该链表上是否有该 key
    while (node != null) {
        Pair pair = node.pair;
        if (pair.key == key) {
            return pair.value;
        }
        node = node.next;
    }
    return null;
}



/* 添加操作 */
public void put(int key, String val) {
    // 第一步，判断哈希表是否需要扩容
    if (loadFactor() > loadThres) {
        extend();
    }
    int index = hashFunc(key);
    ListNode node = buckets[index];
    // 先根据 key 找到对应的 index 下标链表，然后判断该链表上是否有该 key，
    // 如果有，则更新 value 即可，此时不需要修改 size
    // 如果没有，则新增该 key, value 键值对，size++
    // 这里由于如果要新增节点，需要将该节点加入到链表尾部，因为是单向链表，为了减少一次遍历，这里在本次遍历中就记录链表尾节点；
    ListNode rearNode = null;
    while (node != null) {
        Pair pair = node.pair;
        // 找到对应的 key：更新即可
        if (pair.key == key) {
            pair.value = val;
            return;
        }
        // 链表尾节点的 next == null
        if (node.next == null) {
            rearNode = node;
        }
        node = node.next;
    }
    // 当执行到这说明前面没有找到对应的 key，所以新增节点，可以选择将新增节点加入到链表头部或者链表尾部
    // 我们这里选择将链表加入到链表尾部，虽然加到链表头部的实现会更简单，但是还是同 jdk 8 的 hashMap 一样加入到尾部吧
    ListNode putNode = new ListNode(key, val);
    // 注意：这里还得判断尾节点是否为 null，因为可能存在该数组下标位置上原本不存在元素，此时是空链表
    // 此时直接将新节点，放置在数组 index 下标位置上即可
    if (rearNode == null) {
        buckets[index] = putNode;
        size++;
        return;
    }
    // 走到这，说明此时存在尾节点
    rearNode.next = putNode;
    size++;
}



/* 删除操作 */
public void remove(int key) {
    int index = hashFunc(key);
    ListNode node = buckets[index];
    // 先根据 key 找到对应的 index 下标链表，然后判断该链表上是否有该 key，
    // 如果有，则删除该节点，size--
    // 如果没有，不操作
    // 由于是链表，要删除一个节点需要找对该节点的前一个节点，所以在遍历过程中需要记录前一个节点
    ListNode prev = null;
    while (node != null) {
        Pair pair = node.pair;
        // 当找到删除节点时，
        if (pair.key == key) {
            // 如果该节点的前一个节点 == null，说明此时该要删除的节点 = 链表的头节点，
            // 则赋值该数组下标位置为该节点的下一个节点即可
            if (prev == null) {
                buckets[index] = node.next;
            } else {
                // 该要删除的节点不为链表的头节点：
                prev.next = node.next;
            }
            size--;
            return;
        }
        // 当走到这，说明本轮遍历的节点不是要删除的节点，继续向后遍历
        // 向后遍历之前，先记录前一个节点；
        prev = node;
        node = node.next;
    }
    // 当走到这说明，哈希表中不存在该 key，所以不需要操作
}

/* 扩容哈希表 */
private void extend() {
    // 暂存原哈希表
    ListNode[] bucketsTmp = buckets;
    capcaity = capcaity * extendRatio;
    buckets = new ListNode[capcaity];
    // 将原哈希表中的键值对加入到新哈希表中
    // size 不需要改变，因为扩容只是增加容量，没有增加键值对
    for (ListNode node : bucketsTmp) {
        while (node != null) {
            Pair pair = node.pair;
            put(pair.key, pair.value);
            node = node.next;
        }
    }
}

/* 打印哈希表 */
public void print() {
    List<String> list = new ArrayList<>(size);
    int count = 0;
    for (ListNode node : buckets) {
        while (node != null) {
            Pair pair = node.pair;
            list.add(pair.key + "->" + pair.value);
            count++;
            if (count == size) {
                System.out.println(list);
                return;
            }
            node = node.next;
        }
    }

}

}

[mastermiiind]

你好，请问 // size 不需要改变，因为扩容只是增加容量，没有增加键值对 size还是需要置为0的吧？执行put函数不是size++了，不置为零的话size等于二倍了对吗

[huih99]

请问下，上面说到线性探测方法的查找元素的情况：
查找元素：若发现哈希冲突，则使用相同步长向后进行线性遍历，直到找到对应元素，返回 value 即可；如果遇到空桶，说明目标元素不在哈希表中，返回 None 。

在插入元素时如果发现对应的桶已经有值，则向后插入，那么在查找元素时，是怎么知道这个元素有哈希冲突的呢？

[Asce-ops]

桶里面不是光存一个值的，是存储一个键值对对象，把要查找的键和桶里存储的键比较一下不一致就说明冲突了要继续查找 | | 谈惟强 | | ***@***.*** | ---- Replied Message ---- | From | ***@***.***> | | Date | 9/20/2024 16:43 | | To | ***@***.***> | | Cc | ***@***.***> , ***@***.***> | | Subject | Re: [krahets/hello-algo] chapter_hashing/hash_collision/ (Discussion #89) | 请问下，上面说到线性探测方法的查找元素的情况： 查找元素：若发现哈希冲突，则使用相同步长向后进行线性遍历，直到找到对应元素，返回 value 即可；如果遇到空桶，说明目标元素不在哈希表中，返回 None 。 在插入元素时如果发现对应的桶已经有值，则向后插入，那么在查找元素时，是怎么知道这个元素有哈希冲突的呢？ — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you commented.Message ID: ***@***.***>

[huih99]

明白了，感谢

[FrierenGreatDemonLord]

链式地址也叫拉链法：多个元素通过链表的形式“拉”在一起，形成一条“链子”

[EurFelux]

能否讲讲开放寻址在访问元素时是怎么处理的？查找元素是已知键也已知值才能够这样做，但是访问元素的时候常常是不知道值，只知道键。
比如多次哈希法的时候，如何知道要使用哪个哈希函数才能得到正确的值，而不会得到发生冲突的位置的值？我想的是可以通过记录索引对应的哈希函数来处理，但这又会产生额外的开销。
线性探测和平方探测也有类似的问题。我用键去找值，结果发生很多冲突，我怎么知道哪个值才是对的？

[EurFelux]

哦我明白了，每个位置存储的既有键又有值，而不是只有值本身，所以能够判断跟哪里能对上。

[yitaoxianyu]

/* 析构方法 */
~HashMapChaining() {
for (auto &bucket : buckets) {
for (Pair *pair : bucket) {
// 释放内存
delete pair;
}
}
},在这个析构函数中，我可以不使用bucket的引用吗

[FrierenGreatDemonLord]

链式地址法的遍历，有些桶可能是空的，所以可以在外层循环（遍历桶）判断该链表不为空，再进行内层循环（遍历链表），以免在本桶为空时还要操作和打印res 数组 ，如：

def print(self):
    for bucket in self.buckets:
        if not bucket:
            continue
        res = []
        for pair in bucket:
            res.append(f'{pair.key} -> {pair.val}')
        print(res)

[FrierenGreatDemonLord]

也可用memset(void* _Dst, inv _Val, size_t _Size) 来替代遍历实现桶的初始化，如：

memeset() 在string.h 头文件中

// for (int i = 0; i < map->capacity; i++)
// 		map->buckets[i] = NULL;
memset(map->buckets, 0, map->capacity * sizeof(Node*));

[FrierenGreatDemonLord]

数据库中标记记录被删除，而不是真的将其从存储中移除，也被称为“懒删除”。除了在数据结构方面提高操作效率外，在某些应用场景中也方便进行数据恢复或审计。

[ffmm520]

最后一小节关于 JDK 1.8 中链表转红黑树的链表长度表述不准确。应该数组长度达到64（源码中是 <64）且链表长度超过 8，即元素个数达到 9 个时，才会转红黑树。文中链表长度达到 8 个是不对的

[zllrcl]

在hash_map_open_addressing.java中在 findBucket 方法中，循环的跳出条件是遇到空桶 (buckets[index] == null)。然而，由于 TOMBSTONE 不计入 size，在哈希表大量使用删除标记后，表中可能会没有任何空桶，即所有桶都被占用或被标记为 TOMBSTONE。如果在这种情况下插入新的键值对，findBucket 将会一直循环，因为没有空桶供跳出。

[ValMobYKang]

        // 当负载因子超过阈值时，执行扩容
        if (loadFactor() > loadThres) {
            extend();
        }

[zllrcl]

TOMBSTONE不计入size，负载因子的计算中没有考虑TOMBSTONE，

[zllrcl]

做一个简单的测试在hash_map_open_addressing中对hashmap，put0和1再remove0和1，在put2remove2，最后put3和13就会进入死循环，这就是大量删除可能产生的

[Aldebaran-ls]

在hash_map_chaining.c添加操作void put(HashMapChaining *hashMap, int key, const char *val)中，应该为newPair->val申请内存newPair->val = (char *)malloc(strlen(val) + 1);后再执行srtcpy复制操作

[FreakWwjh]

在 hash_map_open_addressing.cpp 中：
/* 添加操作 */void put(int key, string val)
该操作似乎无法实现“开放寻址（线性探测）”的功能。
该功能是：插入元素：通过哈希函数计算桶索引，若发现桶内已有元素，则从冲突位置向后线性遍历，直至找到空桶，将元素插入其中。
但这里的put()函数：int index = findBucket(key);// 若找到键值对，则覆盖 val 并返回

[0101qwe]

first_tombstone = -1
# 线性探测，当遇到空桶时跳出
while self.buckets[index] is not None:
# 若遇到 key ，返回对应的桶索引
if self.buckets[index].key == key:
# 若之前遇到了删除标记，则将键值对移动至该索引处
if first_tombstone != -1:
self.buckets[first_tombstone] = self.buckets[index]
self.buckets[index] = self.TOMBSTONE
return first_tombstone # 返回移动后的桶索引
开放寻址这里这个 first_tombstone 赋值为-1了，后面判断他first_tombstone != -1 这是为什么没看懂，前面已经赋值为-1了 ，那这个 if first_tombstone != -1: 的if语句不就实现不了吗，我这里没看懂，求解释

[JunxiangP]

这个 if 语句在第一次循环内不会执行，但是在整个 while 循环内，下一条语句是：
if first_tombstone == -1 and self.buckets[index] is self.TOMBSTONE:
first_tombstone = index
index = (index + 1) % self.capacity
这条语句就可能对 first_tombstone 重新赋值使其不等于-1，之后再循环就可能满足 if first_tombstone != -1 了。