C++ STL 哈希表原理与实现详解

底层为数组，每个位置指向一个链表（或红黑树）。

• 原理：冲突元素挂在对应桶的链表尾部。
• 优点：逻辑清晰，负载因子可大于 1，无聚集问题。
• 缺点：遍历开销随链表长度增加而增大，存在额外指针内存开销。

4. 自定义 Key 类型适配

若 Key 不是整数（如 string 或结构体），需通过仿函数（Functor）将其转换为可用于取模的整数。例如针对 string 类型，可使用 BKDR 算法累加字符 ASCII 值并乘以质数（如 131）来生成哈希值。

5. 代码实现细节

以下展示基于模板的哈希表实现框架，涵盖开放定址法与链地址法。

基础组件：哈希函数与质数表

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

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

// String 特化示例
template<>
struct HashFunc<string> {
    size_t operator()(const string& s) {
        size_t hash = 0;
        for (auto it : s) {
            hash += it;
            hash *= 131; // BKDR 算法常用质数
        }
        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;
}

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

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;

            // 负载因子检查，触发扩容
            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 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:
        vector<HashNode<K, V>*> _tables;
        size_t _n;

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

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

        HashNode<K, V>* Find(const K& key) {
            Hash hashFunc;
            size_t hash_i = hashFunc(key) % _tables.size();
            HashNode<K, V>* 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();
            HashNode<K, V>* curr = _tables[hash_i];
            HashNode<K, V>* prev = nullptr;
            while (curr) {
                if (curr->_kv.first == key) {
                    if (!prev) _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<HashNode<K, V>*> newVector(_tables.size() * 2);
                for (size_t i = 0; i < _tables.size(); i++) {
                    HashNode<K, V>* current = _tables[i];
                    while (current) {
                        HashNode<K, V>* next = current->_next;
                        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);
            }

            HashNode<K, V>* newNode = new HashNode(kv);
            Hash hashFunc;
            size_t hash_i = hashFunc(kv.first) % _tables.size();
            newNode->_next = _tables[hash_i];
            _tables[hash_i] = newNode;
            ++_n;
            return true;
        }
    };
}

6. 测试验证

在实际使用中，建议编写单元测试覆盖插入、查找、删除及扩容场景，特别是针对自定义 Key 类型（如日期结构体）的哈希适配。测试时应关注扩容后数据的完整性以及负数 Key 的处理逻辑。