C++ 进阶：哈希表原理与实战实现

指不同的关键字通过哈希函数计算后，得到相同的哈希地址的情况。这是哈希表设计中无法避免的核心问题，主要源于哈希函数的'压缩映射'特性以及鸽巢原理。

四、冲突处理

方法一：开放定址法 所有元素都存储在哈希表数组本身中，通过探测序列寻找可用的空槽位。

• 线性探测：h_i(key) = (h(key) + i) % m。容易产生聚集现象。
• 二次探测：h_i(key) = (h(key) + c1 * i + c2 * i * i) % m。减少聚集，但不能探测所有位置。
• 双重散列：h_i(key) = (h1(key) + i * h2(key)) % m。探测序列更均匀，需保证偏移量与表长互质。

方法二：链地址法 用数组 + 链表的组合，让冲突元素'链'在一起。每个数组元素对应一个链表。

• 优点：冲突处理简单，空间灵活，无聚集问题。
• 缺点：遍历开销大，额外空间开销。

基本操作与实现细节

解决键 Key 不能取模的问题

如果关键字不是整数（如 string、Date 等类型），无法直接取模。这时需要增加一个仿函数（哈希函数对象），将 key 转换成一个可用于取模的整数。若 key 本身能方便转换，使用默认仿函数；否则需自行实现特化版本。

C++ 模板实现

以下代码展示了基于 C++ 模板的哈希表实现，涵盖开放定址法和链地址法两种方案。

1. 通用头文件与哈希函数

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

// 通用哈希函数模板
template<class K>
struct HashFunc {
    size_t operator()(const K& key) {
        return (size_t)key; // 默认为直接转换，适用于 int、long 等
    }
};

// 字符串特化：BKDR 算法
template<>
struct HashFunc<string> {
    size_t operator()(const string& s) {
        size_t hash = 0;
        for (auto it : s) {
            hash += it;
            hash *= 131; // 乘以质数以减少冲突
        }
        return hash;
    }
};

// 获取下一个 >=n 的质数（用于扩容）
inline unsigned long _stl_next_prime(unsigned long n) {
    static const int __stl_num_primes = 28;
    static const unsigned long _stl_prime_list[__stl_num_primes] = {
        53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
        49157, 98317, 196613, 393241, 786433, 1572869, 3145739,
        6291469, 12582917, 25165843, 50331653, 100663319, 201326611,
        402653189, 805306457, 1610612741, 3221225473, 4294967291
    };
    const unsigned long* first = _stl_prime_list;
    const unsigned long* last = _stl_prime_list + __stl_num_primes;
    const unsigned long* pos = lower_bound(first, last, n);
    return pos == last ? *(last - 1) : *pos;
}

2. 开放定址法实现（线性探测）

开放定址法中，删除操作不能直接清空内存，否则会破坏探测链。因此需要引入状态标识（EXIST, EMPTY, DELETE）。

#pragma once
#include "HashTable.h"
namespace open_address {

enum State { EXIST, EMPTY, 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 {
private:
    vector<HashData<K, V>> _tables;
    size_t _n;

public:
    HashTable() : _tables(_stl_next_prime(0)), _n(0) {}

    // 查找
    HashData<K, V>* Find(const K& key) {
        Hash hash;
        size_t hash_0 = hash(key) % _tables.size();
        size_t hash_i = hash_0;
        size_t i = 1;
        while (_tables[hash_i]._state != EMPTY) {
            if (_tables[hash_i]._state == EXIST && _tables[hash_i]._kv.first == key) {
                return &_tables[hash_i];
            }
            hash_i = (hash_0 + i) % _tables.size();
            ++i;
        }
        return nullptr;
    }

    // 删除：标记为 DELETE 状态
    bool Erase(const K& key) {
        HashData<K, V>* ret = Find(key);
        if (ret) {
            ret->_state = DELETE;
            --_n;
            return true;
        }
        return false;
    }

    // 插入：包含扩容逻辑
    bool Insert(const pair<K, V>& kv) {
        if (Find(kv.first)) return false;

        // 负载因子 >= 0.7 时扩容
        if (_n * 10 / _tables.size() >= 7) {
            HashTable<K, V, Hash> newHt;
            newHt._tables.resize(_stl_next_prime(_tables.size() + 1));
            for (auto& htData : _tables) {
                if (htData._state == EXIST) {
                    newHt.Insert(htData._kv);
                }
            }
            _tables.swap(newHt._tables);
        }

        Hash hashFunc;
        size_t hash_0 = hashFunc(kv.first) % _tables.size();
        size_t hash_i = hash_0;
        size_t i = 1;
        while (_tables[hash_i]._state == EXIST) {
            hash_i = (hash_0 + i) % _tables.size();
            ++i;
        }
        _tables[hash_i]._kv = kv;
        _tables[hash_i]._state = EXIST;
        ++_n;
        return true;
    }
};
} // namespace open_address

3. 链地址法实现（哈希桶）

链地址法结构更清晰，每个桶是一个链表头指针。析构时需要手动释放节点内存。

#pragma once
#include "HashTable.h"
namespace hash_bucket {

template<class K, class V>
struct HashNode {
    pair<K, V> _kv;
    HashNode<K, V>* _next;
    HashNode(const pair<K, V>& kv) : _kv(kv), _next(nullptr) {}
};

template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
private:
    typedef HashNode<K, V> Node;
    vector<Node*> _tables;
    size_t _n;

public:
    HashTable() : _tables(_stl_next_prime(0)), _n(0) {}

    ~HashTable() {
        for (size_t i = 0; i < _tables.size(); ++i) {
            Node* current = _tables[i];
            while (current) {
                Node* next = current->_next;
                delete current;
                current = next;
            }
            _tables[i] = nullptr;
        }
    }

    Node* Find(const K& key) {
        Hash hashFunc;
        size_t hash_i = hashFunc(key) % _tables.size();
        Node* current = _tables[hash_i];
        while (current) {
            if (current->_kv.first == key) return current;
            current = current->_next;
        }
        return nullptr;
    }

    bool Erase(const K& key) {
        Hash hashFunc;
        size_t hash_i = hashFunc(key) % _tables.size();
        Node* curr = _tables[hash_i];
        Node* prev = nullptr;
        while (curr) {
            if (curr->_kv.first == key) {
                if (prev == nullptr) {
                    _tables[hash_i] = curr->_next;
                } else {
                    prev->_next = curr->_next;
                }
                delete curr;
                --_n;
                return true;
            }
            prev = curr;
            curr = curr->_next;
        }
        return false;
    }

    bool Insert(const pair<K, V>& kv) {
        if (Find(kv.first)) return false;

        // 负载因子 >= 1 时扩容
        if (_n == _tables.size()) {
            vector<Node*> newVector(_tables.size() * 2);
            for (size_t i = 0; i < _tables.size(); i++) {
                Node* current = _tables[i];
                while (current) {
                    Node* next = current->_next;
                    Hash hashFunc;
                    size_t hash_i = hashFunc(current->_kv.first) % newVector.size();
                    current->_next = newVector[hash_i];
                    newVector[hash_i] = current;
                    current = next;
                }
                _tables[i] = nullptr;
            }
            _tables.swap(newVector);
        }

        Node* newNode = new Node(kv);
        Hash hashFunc;
        size_t hash_i = hashFunc(kv.first) % _tables.size();
        newNode->_next = _tables[hash_i];
        _tables[hash_i] = newNode;
        ++_n;
        return true;
    }
};
} // namespace hash_bucket

测试与验证

在实际使用中，建议编写单元测试覆盖插入、查找、删除及扩容场景。特别是针对自定义类型（如 Date 结构体），需重载相等运算符并实现对应的哈希仿函数。

示例测试逻辑：

1. 创建哈希表实例。
2. 执行多次插入操作，验证重复键返回失败。
3. 执行查找操作，验证存在性与值正确性。
4. 执行删除操作，验证状态变更及后续查找行为。
5. 大量插入数据以触发扩容，验证数据迁移后的可访问性。