C++ STL 哈希表原理与模拟实现

使用两个哈希函数，第二个函数提供偏移量。只要 h2(key) 与表长互质，就能覆盖整个表。这是开放定址法中性能较好的方案。

链地址法

哈希表底层是一个数组，每个元素指向一个链表。冲突的元素挂在同一个桶的链表上。

• 优点：逻辑简单，支持动态扩容，无聚集问题。
• 缺点：存在额外指针开销，链表过长时查找退化为 O(n)。

STL 中的 unordered_map 在 C++11 之后针对某些情况（如红黑树转换）做了优化，但基础结构仍基于链地址法思想。

关键实现细节

非整数 Key 的处理

哈希函数通常要求输入为整数。对于字符串或其他类型，需要定义仿函数（Functor）将其转换为 size_t 类型的哈希值。例如，BKDR 算法常用于字符串哈希，通过累加字符 ASCII 值并乘以质数（如 131）来减少冲突。

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

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

开放定址法的删除操作

在开放定址法中，不能简单地清空位置，否则会导致后续查找中断。因此需要引入状态标记：EXIST（存在）、EMPTY（空）、DELETE（已删除）。查找时遇到 DELETE 继续探测，直到遇到 EMPTY 停止；插入时可将 DELETE 视为可用位置。

扩容与质数表

为了保证哈希分布均匀，哈希表容量通常选择质数。SGI 版本的实现维护了一个预定义的质数表，扩容时通过二分查找找到大于当前容量的最小质数。

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 = std::lower_bound(first, last, n);
    return pos == last ? *(last - 1) : *pos;
}

代码实战

开放定址法实现

enum State { EXIST, EMPTY, DELETE };

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

template<class K, class V, class Hash = HashFunc<K>>
class HashTableOpenAddress {
private:
    std::vector<HashData<K, V>> _tables;
    size_t _n;
public:
    HashTableOpenAddress() : _tables(_stl_next_prime(0)), _n(0) {}

    bool Insert(const std::pair<K, V>& kv) {
        if (Find(kv.first)) return false;
        if (_n * 10 / _tables.size() >= 7) {
            // 扩容逻辑
            HashTableOpenAddress 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 hash;
        size_t hash_0 = hash(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;
    }

    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;
    }

    bool Erase(const K& key) {
        auto ret = Find(key);
        if (ret) {
            ret->_state = DELETE;
            --_n;
            return true;
        }
        return false;
    }
};

链地址法实现

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

template<class K, class V, class Hash = HashFunc<K>>
class HashTableChaining {
private:
    std::vector<HashNode<K, V>*> _tables;
    size_t _n;
public:
    HashTableChaining() : _tables(_stl_next_prime(0)), _n(0) {}

    ~HashTableChaining() {
        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;
        }
    }

    bool Insert(const std::pair<K, V>& kv) {
        if (Find(kv.first)) return false;
        if (_n == _tables.size()) {
            // 扩容逻辑
            std::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 = Hash()(current->_kv.first) % newVector.size();
                    current->_next = newVector[hash_i];
                    newVector[hash_i] = current;
                    current = next;
                }
            }
            _tables.swap(newVector);
        }
        Hash hashFunc;
        size_t hash_i = hashFunc(kv.first) % _tables.size();
        HashNode<K, V>* newNode = new HashNode(kv);
        newNode->_next = _tables[hash_i];
        _tables[hash_i] = newNode;
        ++_n;
        return true;
    }

    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;
    }
};

测试验证

在实际开发中，建议编写单元测试覆盖插入、查找、删除及扩容场景。特别是针对负数 Key、字符串 Key 以及自定义结构体 Key 的哈希行为进行测试，确保仿函数正确实现了转换逻辑。

通过上述实现，我们可以清晰地看到哈希表如何在内存中组织数据，以及在不同冲突策略下如何维持性能。掌握这些底层原理，有助于在面对复杂业务需求时做出更合理的数据结构选型。