C++ 哈希表模拟实现：闭散列与冲突处理

2.2 哈希表插入数据

在插入过程中，元素需要通过除留余数法找到对应位置进行插入，期间可能会出现哈希冲突的问题，我们需要以该位置向后寻找状态标记为空的位置进行插入。

在向后寻找位置途中可能存在越界情况，这里采用处理循环队列方式进行取模操作，保证数据在合法范围进行查找。这里存在一个大前提，空间是充足的，不然找半天都找不到位置。

bool Insert(const pair<K, V>& kv) {
    size_t hashi = kv.first % _tables.size();
    // 如何判断是否删除，是否继续查找，通过标记
    while (_tables[hashi]._state == EXIST) {
        hashi++;
        hashi %= _tables.size();
    }
    _tables[hashi]._kv = kv;
    _tables[hashi]._state = EXIST;
    _n++;
    return true;
}

2.3 哈希表扩容逻辑

由于哈希表特殊的结构，在进行哈希表扩容操作时，并不采用空位置被填满才进行扩容，而是采用载荷因子的概念进行控制，否则用于空间过少，发生哈希冲突问题频繁，导致效率降低。

可以理解为：负载因子越小，冲突率越低，效率就越高，空间利用率就越低。

【扩容条件判断的问题】: if (_n / _tables.size() >= 0.7)

这里涉及类型问题，可以采用类型转换或者乘个十：

1. (double)_n / _tables.size() >= 0.7
2. _n * 10 / _tables.size() >= 7

【问题】：这里 n 是除以 size 还是 capacity？ 如果选择除以 capacity 空间容量，可能会导致越界访问。当然如果不知道除以 size 还是 capacity，可以在构造函数先为 _tables 开辟空间，避免了这个问题的发生，同时防止了 size 出现等于零的风险。

2.4 哈希表扩容需要换表

当哈希表进行扩容逻辑时，导致了散列表长度发生了变换。这也意味着通过哈希函数 (开发定址法) 得到的位置需要重新安排插入。在哈希进行扩容操作时，整个过程中消耗最大的时候，需要开辟空间和插入数据，重新进行映射到新表中。

2.5 复用插入逻辑

在扩容操作需要插入数据，需要进行哈希函数的处理，但是在插入操作中已经存在哈希函数进行处理的逻辑，如果选择重新书写哈希函数显得有点冗余。

bool Insert(const pair<K, V>& kv) {
    // 建立在空间充足及其目前不存在该数据基本上
    size_t hashi = kv.first % _tables.size();
    
    // 扩容逻辑，这里涉及到负载因子拉
    if (_n * 10 / _tables.size() >= 7) {
        HashTable<K, V> NewHT;
        // 插入逻辑，但是这里我们选择复用，不用我们去判断
        NewHT._tables.resize(_tables.size() * 2);
    }
    
    // 如何判断是否删除，是否继续查找，通过标记
    while (_tables[hashi]._state == EXIST) {
        hashi++;
        hashi %= _tables.size();
    }
    _tables[hashi]._kv = kv;
    _tables[hashi]._state = EXIST;
    _n++;
    return true;
}

2.6 哈希表查找元素

关于哈希表进行查找逻辑是比较容易的，其中我想分享一个在设计遇到的问题。在设计状态标记时，只考虑了存在 EXIST 和空 EMPTY 两个状态，这导致了当删除某个元素时，查找过程中无法判断找到数据及其是否需要继续前进，需要 DELETE 标记。

HashData<K, V>* Find(const K& key) {
    size_t hashi = key % _tables.size();
    // 这里本身就是一个循环判断语句
    while (_tables[hashi]._state == EXIST) {
        if (key == _tables[hashi]._kv.first && _tables[hashi]._state == EXIST) {
            return &_tables[hashi];
        }
        hashi++;
        hashi %= _tables.size();
    }
    return nullptr;
}

2.7 哈希表删除数据

哈希表删除数据是我们遇到最简单的删除逻辑，只需要改变位置状态就可以了。

bool Erase(const K& key) {
    HashData<K, V>* ret = Find(key);
    if (ret) {
        ret->_state = DELETE;
        _n--;
        return true;
    } else {
        return false;
    }
}

三、除留余数法出现类型问题

【除留余数法】: size_t hashi = key % _tables.size();

3.1 类型问题分析

对于 key 进行取模查找，是建立在 key 属于无符号整型类型来考虑的，但是我们设计属于泛型编程，key 需要去适应不同种类型：string 类型，自定义类型，负数。

这种场景需要使用仿函数进行解决，key 不支持强转整型取模，那么就要自己提供换成整型仿函数。

3.2 简单类型做 key

对于简单的整数类型，可以直接转换为 size_t 进行取模。

3.3 string 类型做 key

关于 string 类型转化为整型类型，这里不推荐使用 stoi 函数，从编码角度上，对于中文字符底层是通过多个字符对应一个编码表里面的汉字，一旦不采用这张表会出现乱码的情况。

虽然拿 string 首字母转化伪 ASCII 码值可行，但是很容易发生哈希冲突。

BKDR 算法

最初考虑将字符串中所有字符的 ASCII 码值相加，以优于仅考虑首字母的效果。然而，这种方法存在缺陷：不同字符组合可能具有相同的 ASCII 码总和。因此，我们将采用 BKDR 算法进行优化。

// BKDR 算法核心思想示例
size_t hash = 0;
for (auto ch : key) {
    hash *= 131; 
    hash += ch;
}
return hash;

string 模板特化

由于 string 作 key 是很常见的情况，这里我们可以对 string 模板特殊化。（模板特化建立在存在模板的情况下）

template<>
struct HashFunc<string> {
    size_t operator()(const string& key) {
        size_t hash = 0;
        for (auto ch : key) {
            hash *= 131;
            hash += ch;
        }
        return hash;
    }
};

3.4 复杂类型做 key

如果出现复杂类型做 key，这种情况一般是自定义类型，比如容器类、学生信息，我们都可以考虑将类中成员相加起来或者独特项，出来的数据不太唯一。

struct Person {
    string _name;
    int _age;
};

散列表头文件

下面是整合后的完整代码示例，包含哈希函数特化及测试逻辑。

#pragma once
#include <iostream>
using namespace std;
#include <vector>

template<class K>
struct HashFunc {
    size_t operator()(const K& key) {
        return (size_t)key;
    }
};

template<>
struct HashFunc<string> {
    size_t operator()(const string& key) {
        size_t hash = 0;
        for (auto ch : key) {
            hash *= 131;
            hash += ch;
        }
        return hash;
    }
};

namespace HashTable {
    enum State { EMPTY, EXIST, DELETE };

    template<class K, class V>
    struct HashData {
        pair<K, V> _kv;
        State _state = EMPTY;
    };

    template<class K, class V, class Hash = HashFunc<K>>
    class HashTable {
    public:
        // 这里只能构造成空的容器，等待数据插入。我们需要进入的元素是 pair 类型，K 和 V 是明面上的
        HashTable() {
            // 避免 size 和 capacity 问题
            _tables.resize(10);
        }

        bool Insert(const pair<K, V>& kv) {
            if (Find(kv.first) != nullptr) {
                return false;
            }
            Hash hs;
            // 建立在空间充足及其目前不存在该数据基本上
            size_t hashi = hs(kv.first) % _tables.size();
            
            // 扩容逻辑，这里涉及到负载因子拉
            if (_n * 10 / _tables.size() >= 7) {
                HashTable<K, V> NewHT;
                // 插入逻辑，但是这里我们选择复用，不用我们去判断
                NewHT._tables.resize(_tables.size() * 2);
            }
            
            // 如何判断是否删除，是否继续查找，通过标记
            while (_tables[hashi]._state == EXIST) {
                hashi++;
                hashi %= _tables.size();
            }
            _tables[hashi]._kv = kv;
            _tables[hashi]._state = EXIST;
            _n++;
            return true;
        }

        HashData<K, V>* Find(const K& key) {
            Hash hs;
            size_t hashi = hs(key) % _tables.size();
            // 这里本身就是一个循环判断语句
            while (_tables[hashi]._state == EXIST) {
                if (key == _tables[hashi]._kv.first && _tables[hashi]._state == EXIST) {
                    return &_tables[hashi];
                }
                hashi++;
                hashi %= _tables.size();
            }
            return nullptr;
        }

        bool Erase(const K& key) {
            HashData<K, V>* ret = Find(key);
            if (ret) {
                ret->_state = DELETE;
                _n--;
                return true;
            } else {
                return false;
            }
        }

    private:
        vector<HashData<K, V>> _tables;
        size_t _n = 0;
    };

    void TestHT1() {
        int a[] = { 10001, 11, 55, 24, 19, 12, 31 };
        HashTable<int, int> ht;
        for (auto e : a) {
            ht.Insert(make_pair(e, e));
        }
        cout << ht.Find(55) << endl;
        cout << ht.Find(31) << endl;
        ht.Erase(55);
        cout << ht.Find(55) << endl;
        cout << ht.Find(31) << endl;
    }
}

以上就是本篇文章的所有内容，希望对你在学习 C++ 语言旅途中有所帮助！