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

[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复制操作

[Aldebaran-ls]

’pair->val‘’在定义结构体时为数组不需要申请内存操作

[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 了。

[YourYongKing]

def find_bucket(self, key: int) -> int:
"""搜索 key 对应的桶索引"""
index = self.hash_func(key)
first_tombstone = -1
# 记录遍历的起始位置，避免无限循环
start_index = index
# 线性探测，当遇到空桶时跳出
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 # 返回移动后的桶索引
return index # 返回桶索引
# 记录遇到的首个删除标记
if first_tombstone == -1 and self.buckets[index] is self.TOMBSTONE:
first_tombstone = index
# 计算桶索引，越过尾部则返回头部
index = (index + 1) % self.capacity
# 如果回到起始位置，说明哈希表已满且未找到 key
if index == start_index:
break
# 若 key 不存在，则返回添加点的索引
return index if first_tombstone == -1 else first_tombstone
如果哈希表满了且没有要找的key这段代码就会死循环，可以改成
def find_bucket(self, key: int) -> int:
"""搜索 key 对应的桶索引"""
index = self.hash_func(key)
first_tombstone = -1
# 记录遍历的起始位置，避免无限循环
start_index = index
# 线性探测，当遇到空桶时跳出
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 # 返回移动后的桶索引
return index # 返回桶索引
# 记录遇到的首个删除标记
if first_tombstone == -1 and self.buckets[index] is self.TOMBSTONE:
first_tombstone = index
# 计算桶索引，越过尾部则返回头部
index = (index + 1) % self.capacity
# 如果回到起始位置，说明哈希表已满且未找到 key
if index == start_index:
break
# 若 key 不存在，则返回添加点的索引
return index if first_tombstone == -1 else first_tombstone

[elk-9527]

C++中的unordered_map采用的是链式地址

[Zero-JC]

hash_map_chaining.java 中打印哈希表方法会打印空集合，应该增加集合为空判断。
修改后的方法如下：

/* 打印哈希表 */
    void print() {
        for (List<Pair> bucket : buckets) {
            if (!bucket.isEmpty()) {
                List<String> res = new ArrayList<>();
                for (Pair pair : bucket) {
                    res.add(pair.key + " -> " + pair.val);
                }
                System.out.println(res);
            }   
        }
    }

[jiuerya7]

关于开放寻址，第一次看，看了好久≡(▔﹏▔)≡，我自己写的代码，标注很详细。各种情况我都考虑了，比如，先遇到空；没有遇到空，然后向下遍历，遇到空桶之前遇到0个，1个，或者更多个被标记为空桶的键值对。写的代码在这了，希望你看了能帮助到你( •̀ ω •́ )✧ 。
class Pair
{
public int Key { get; set; }
public string Value { get; set; }

public Pair(int key, string value)
{
    this.Key = key;
    this.Value = value;
}

}

/* 开放寻址 实现哈希表 */
class HashMapOpenAddressing
{
public int size = 0; //哈希表的元素数量
public int capacity = 10; //哈希表的容量
public double threShold = 2.0 / 3.0; //扩容阈值
private int extendRadio = 2; //扩容系数
private List buckets; //桶数组
private Pair TOMBSTONE = new Pair(-1, "-1"); //用于将删除元素标记的 键值对

//初始化桶数组
public HashMapOpenAddressing()
{
    buckets = new List<Pair>(capacity);
}

//负载因子
public double LoadFactor()
{
    return (double)size / capacity;
}

//哈希函数
public int HashFunc(int key)
{
    return key % capacity;
}

//返回正确的桶索引
int FindKey(int key)
{
    int index = HashFunc(key);
    int firstTombStone = -1;            //用于记录第一个被标记为空桶的键值对 的所在位置的索引
    
    //没有遇到空桶,就向下遍历,寻找合适的可插入的位置
    while (buckets[index] != null)
    {
        //检查键,
        if (buckets[index].Key == key)
        {
            //如果在遇到匹配的键之前,遇到了被标记为空桶的键值对,则交换这个键值对 和 被标记为空桶的键值对,并返回标记位置的索引
            if (firstTombStone != -1)
            {
                buckets[firstTombStone] = buckets[index];
                buckets[index] = TOMBSTONE;
                return firstTombStone;
            }

            //遇到匹配的键之前,没有遇到被标记为空桶的键值对
            return index;
        }
    }
    
    // 记录首个被标记为空桶的键值对 的索引(只会记录一次,因为一旦记录之后,firstTombStone就会改变,该if语句将不再执行)
    if (firstTombStone == -1 && buckets[index] == TOMBSTONE)
    {
        firstTombStone = index;
    }
    
    //如果遇到空桶,则返回该index
    //如果在遇到空桶之前,遇到1个及以上的 被标记为空桶的键值对,返回首个标记索引
    return firstTombStone == -1 ? index : firstTombStone;
}

//查询操作
public string Find(int key)
{
    //先计算index
    int index = FindKey(key);
    
    //如果索引位置不为空,且未被标记,则返回值
    if (buckets[index] != null && buckets[index] != TOMBSTONE)
        return buckets[index].Value;
    
    //否则返回null
    return null;
}

//添加操作
public void Put(int key, string value)
{
    //先计算index
    int index = FindKey(key);
    
    //超过阈值,扩容哈希表
    if(LoadFactor()>threShold)
        ExtendHashMap();
    
    //如果遇到已经存在的key,仅更改值即可
    if (buckets[index] != null && buckets[index] != TOMBSTONE)
    {
        buckets[index].Value = value;
        //size++;
        return;
    }
    
    //没有遇到则添加
    buckets[index] = new Pair(key, value);
    size++;
}

//删除操作
public void Remove(int key)
{
    int index = FindKey(key);
    
    //仅索引位置不为空,且未被标记,才删除(懒删除)
    if (buckets[index] != null && buckets[index] != TOMBSTONE)
    {
        buckets[index] = TOMBSTONE;
        size--;
    }
}

//扩容
void ExtendHashMap()
{
    //新哈希表,且扩容
    List<Pair> bucketsTmp = buckets;     //把原来的哈希表赋给新哈希表,可以同时更改原来的哈希表,方法结束之后,新哈希表会被回收
    
    capacity *= extendRadio;
    buckets = new List<Pair>(capacity);
    
    //转移
    foreach (var pair in bucketsTmp)
    {
        if (pair != null && pair != TOMBSTONE)
        {
            //bucketsTmp.Add(pair);
            Put(pair.Key, pair.Value);
        }
    }
}

//打印哈希表
public void Print()
{
    foreach (var pair in buckets)
    {
        if (pair == null)
        {
            Console.WriteLine("null");
        }
        else if (pair == TOMBSTONE)
        {
            Console.WriteLine("TOMBSTONE");
        }
        else
        {
            Console.WriteLine($"{pair.Key} -> {pair.Value}");
        }
    }
}

}

[jiuerya7]

少了一步≡(▔﹏▔)≡

// 计算桶索引，越过尾部则返回头部
index = (index + 1) % capacity;

[jiuerya7]

还有一个扩容的时候，重置size，也忘了UwU

[xiaozhuge123]

day05

[Limit1996]

C#简单hashtable

namespace HashTable.Console;

public class Map<TKey, TValue>
{

    private readonly KeyValuePair<TKey, TValue>[] _buckets = new KeyValuePair<TKey, TValue>[100];

    private int _count;


    public int Capacity => _buckets.Length;

    public int Count => _count;
    
    public TKey[] Keys => GetKeys();
    
    public TValue[] Values => GetValues();


    public void Put(TKey key, TValue value)
    {
        var index = GetIndex(key);
        _buckets[index] = new KeyValuePair<TKey, TValue>(key, value);
        _count++;
    }

    public void Remove(TKey key)
    {
        var index = GetIndex(key);
        _buckets[index] = null!;
        _count--;
    }

    public TValue Get(TKey key)
    {
        var index = GetIndex(key);
        return _buckets[index].Value;
    }

    private TKey[] GetKeys()
    {
        var res = _buckets.Where(x => x is not null).Select(x => x.Key).ToArray();
        return res;
    }
    
    private TValue[] GetValues()
    {
        var res = _buckets.Where(x => x is not null).Select(x => x.Value).ToArray();
        return res;
    }

    private int GetIndex(TKey key)
    {
        if (key is null)
            throw new ArgumentNullException(nameof(key));
        var hashCode = key.GetHashCode() & Int32.MaxValue;
        var index = hashCode % Capacity;
        return index;
    }
}

[Limit1996]

C#链式地址

public class LinkedListMapPlus<TKey, TValue>
{
    private List<KeyValuePair<TKey, TValue>>[] _buckets;

    private const float LoadFactor = 0.75f;

    private int _capacity = 10;

    private int _count;
    public int Count => _count;
    
    public TKey[] Keys => GetKeys();
    
    public TValue[] Values => GetValues();
    
    private readonly Action _addBucket;

    public LinkedListMapPlus()
    {
        _buckets = new List<KeyValuePair<TKey, TValue>>[_capacity];

        _addBucket = () =>
        {
            if (_count + 1 <= _capacity * LoadFactor)
                return;

            _capacity = _capacity * 2;

            var newBuckets = new List<KeyValuePair<TKey, TValue>>[_capacity];

            for (int i = 0; i < _buckets.Length; i++)
            {
                if (_buckets[i] is null)
                    continue;
                foreach (var pair in _buckets[i])
                {
                    var index = GetIndex(pair.Key);
                    newBuckets[index] ??= new();
                    newBuckets[index].Add(pair);
                }
            }
            _buckets = newBuckets;
        };
    }

    public void Put(TKey key, TValue value)
    {
        _addBucket();
        var index = GetIndex(key);
        var pair = new KeyValuePair<TKey, TValue>(key, value);

        _buckets[index] ??= new();

        _buckets[index].Add(pair);

        _count++;
    }

    public TValue Get(TKey key)
    {
        var index = GetIndex(key);
        var bucket = _buckets[index];
        if (bucket is null)
            throw new KeyNotFoundException($"'{key}'键不存在");

        foreach (var pair in bucket)
        {
            if (pair.Key!.Equals(key))
            {
                return pair.Value;
            }
        }
        throw new KeyNotFoundException($"'{key}'键不存在");
    }

    public void Remove(TKey key)
    {
        var index = GetIndex(key);
        var bucket = _buckets[index];
        if (bucket is null)
            throw new KeyNotFoundException($"'{key}'键不存在");
        for (int i = 0; i < bucket.Count; i++)
        {
            if (bucket[i].Key!.Equals(key))
            {
                bucket.RemoveAt(i);
                _count--;
                return;
            }
        }
        throw new KeyNotFoundException($"'{key}'键不存在");
    }

    private int GetIndex(TKey key)
    {
        if (key is null)
            throw new ArgumentNullException(nameof(key));

        var hash = key.GetHashCode() & Int32.MaxValue;

        var index = hash % _capacity;

        return index;
    }

    private TKey[] GetKeys()
    {
        var foo = _buckets.Where(x => x is not null);
        var bar = foo.SelectMany(x => x).ToArray();
        
        return bar.Select(x => x.Key).ToArray();
    }

    private TValue[] GetValues()
    {
        var foo = _buckets.Where(x => x is not null);
        var bar = foo.SelectMany(x => x).ToArray();
        
        return bar.Select(x => x.Value).ToArray();
    }
}

[SentoMK]

C++ 链式地址哈希表

#pragma once
#include <vector>
#include <functional>
#include <stdexcept>

template<typename K, typename V>
class HashMap
{
private:
    struct HashNode
    {
        K key;
        V value;
        HashNode *next;

        HashNode(const K &k, const V &v) : key(k), value(v), next(nullptr){}
    };

    std::vector<HashNode *> table;
    int capacity;
    int size;
    const double LOAD_FACTOR = 0.75;

    int hashFunc(const K &key)
    {
        std::hash<K> hasher;
        return hasher(key) % capacity;
    }

public:
    HashMap(int initCapacity = 11) : capacity(initCapacity), size(0)
    {
        table.resize(capacity, nullptr);
    }

    ~HashMap()
    {
        for(int i = 0; i < capacity; ++i)
        {
            HashNode *entry = table[i];
            while (entry)
            {
                HashNode *prev = entry;
                entry = entry->next;
                delete prev;
            }
        }
    }

    void put(const K &key, const V &val)
    {
        if(static_cast<double>(size) / capacity >= LOAD_FACTOR)
        {
            resize();
        }

        int index = hashFunc(key);
        HashNode *entry = table[index];

        if(!entry)
        {
            table[index] = new HashNode(key, val);
            size++;
            return;
        }

        HashNode *prev = nullptr;
        while (entry)
        {
            if(entry->key == key)
            {
                entry->value = val;
                return;
            }
            prev = entry;
            entry = entry->next;
        }

        prev->next = new HashNode(key, val);
        size++;
    }

    void resize()
    {
        int oldCapacity = capacity;
        capacity = oldCapacity * 2 + 1;
        std::vector<HashNode *> newTable(capacity, nullptr);

        for (int i = 0; i < oldCapacity; ++i)
        {
            HashNode *entry = table[i];
            while (entry)
            {
                HashNode *next = entry->next;
                int newIndex = hashFunc(entry->key);

                entry->next = newTable[newIndex];
                newTable[newIndex] = entry;

                entry = next;
            }
            table[i] = nullptr;
        }

        table = std::move(newTable);
    }
    
    V get(const K &key)
    {
        int index = hashFunc(key);
        HashNode *entry = table[index];

        while (entry)
        {
            if (entry->key == key)
            {
                return entry->value;
            }
            entry = entry->next;
        }

        throw std::runtime_error("Key not found");
    }

    void remove(const K &key)
    {
        int index = hashFunc(key);
        HashNode *entry = table[index];
        HashNode *prev = nullptr;

        while (entry)
        {
            if (entry->key == key)
            {
                if (!prev)
                {
                    table[index] = entry->next;
                }
                else
                {
                    prev->next = entry->next;
                }
                delete entry;
                size--;
                return;
            }
            prev = entry;
            entry = entry->next;
        }

        throw std::runtime_error("Key not found");
    }
};

[NonMirror]

开放寻址的这个函数
/* 搜索 key 对应的桶索引 */
int findBucket(int key) {
int index = hashFunc(key);
int firstTombstone = -1;
// 线性探测，当遇到空桶时跳出
while (buckets[index] != nullptr) {
// 若遇到 key ，返回对应的桶索引
if (buckets[index]->key == key) {
// 若之前遇到了删除标记，则将键值对移动至该索引处
if (firstTombstone != -1) {
buckets[firstTombstone] = buckets[index];
buckets[index] = TOMBSTONE;
return firstTombstone; // 返回移动后的桶索引
}
return index; // 返回桶索引
}
// 记录遇到的首个删除标记
if (firstTombstone == -1 && buckets[index] == TOMBSTONE) {
firstTombstone = index;
}
// 计算桶索引，越过尾部则返回头部
index = (index + 1) % capacity;
}
// 若 key 不存在，则返回添加点的索引
return firstTombstone == -1 ? index : firstTombstone;
}

[NonMirror]

如果哈希表是满的，又找不到key，会死循环。这里有点问题吧

[easypinex]

我想, 考慮到:
if (loadFactor() > loadThres) {
extend();
}
如果 1 < loadThres 成立, 基本不會死循環
當然我想加上防止死循環的條件更好.

[NonMirror]

我想, 考慮到: if (loadFactor() > loadThres) { extend(); } 如果 1 < loadThres 成立, 基本不會死循環 當然我想加上防止死循環的條件更好.

是哦，我看的比较粗略没注意到

[bzanniupiswadwas]

基于链表的链式地址（python版）
class hashListNode:
'''由于哈希表中对链表要求不大，所以实现一个简单的链表'''

def __init__(self, key, value):
    self.val = value
    self.key = key
    self.next = None

class hashLinkedList:

def __init__(self):
    self.head = None

def is_empty(self) -> bool:
    """判断链表是否为空"""
    return self.head is None

def add(self, key, value):
    """在链表尾部添加一个节点（值为 val,键为key）"""
    new_node = hashListNode(key, value)
    if self.is_empty():
        self.head = new_node
        return
    cur = self.head
    while cur.next:
        cur = cur.next
    cur.next = new_node

def remove(self, key):
    cur = self.head
    prev = None
    while cur:
        if cur.key == key:
            if prev:
                prev.next = cur.next
            else:
                self.head = cur.next
            return True
        prev = cur
        cur = cur.next
    return False

class HashMapChaining:

def __init__(self):
    self.size = 0  # 存放了链表数量
    self.capacity = 4  # 哈希表容量
    self.load_thres = 2.0 / 3.0  # 触发扩容的负载因子阈值
    self.extend_ratio = 2  # 扩容倍数
    self.links = [None] * self.capacity  # 链表数组

def hash_func(self, key):
    return key % self.capacity

def load_factor(self):
    return self.size / self.capacity

def get(self, key):
    index = self.hash_func(key)
    if self.links[index] is None:
        return None
    head = self.links[index].head
    while head:
        if head.key == key:
            return head.val
        head = head.next
    # 若未找到 key ，则返回 None
    return None

def put(self, key, val):
    index = self.hash_func(key)

    if self.load_factor() > self.load_thres:
        self.extend()

    if self.links[index] is None:
        # 创建新链表并添加节点
        new_list = hashLinkedList()
        new_list.add(key, val)
        self.links[index] = new_list
        self.size += 1
    else:
        # 查找是否已存在 key
        cur = self.links[index].head
        while cur:
            if cur.key == key:
                cur.val = val  # 更新值
                return
            cur = cur.next
        # 没找到 key，添加新节点
        self.links[index].add(key, val)

def pop(self, key):
    index = self.hash_func(key)
    link = self.links[index]
    if link is None:
        return False

    removed = link.remove(key)
    if removed:
        # 如果链表为空，清空该桶
        if link.is_empty():
            self.links[index] = None
            self.size -= 1
        return True
    return False

def extend(self):
    old_links = self.links
    self.capacity *= self.extend_ratio
    self.links = [None] * self.capacity
    self.size = 0

    for link in old_links:
        if link is not None:
            cur = link.head
            while cur:
                self.put(cur.key, cur.val)
                cur = cur.next

[solink7]

这里没看懂啥意思，感觉奇奇怪怪，后续再来看吧