C++ 数据结构：哈希表原理与 STL 实现详解

C++ 数据结构：哈希表原理与 STL 实现详解

哈希表基础

首先需要明确哈希（Hash）与哈希表（Hash Table）的区别。哈希是一种映射算法思想，而哈希表则是基于这种思想构建的数据结构。

哈希表的核心流程是统一的：获取一个 Key，通过哈希函数计算 Hasher(Key)，得到存储位置并存放 Value；或者从该位置取出对应的 Value。

理解哈希表的三个层次

要深入理解哈希表，建议从以下三个层面递进学习：

1. 哈希值：这是最基础的整数表示。
2. 哈希函数：将哈希值映射到具体空间位置的方法。
3. 哈希冲突：当多个 Key 映射到同一位置时的处理机制。

STL 底层哈希函数的本质是对哈希值进行二次 Hash。无论 Key 是 string、vector 还是其他自定义类型，最终都需要转换为整形哈希值才能被处理。因此，先获得哈希值，再使用哈希函数确定映射位置，是理解的关键逻辑链。

此外，哈希表在逻辑上可视为数组。数组有大小限制，当数据量超过容量或不同自定义类型的哈希值相同，必然产生哈希冲突。哈希是功能，冲突是结果，两者存在因果关系。

哈希值与转换策略

哈希函数通常针对整形数据进行操作（如除留余数法）。在使用 STL 时，若要对自定义类型进行哈希，必须提供将其转换为哈希值的策略（仿函数）。

转换策略需满足速度快、离散度高的要求。常见的策略包括：

• BKDR 哈希：适用于字符串。
• 异或组合：适用于简单容器。
• hash_combine：适用于多成员复杂结构。

BKDR 哈希

优点是实现简单、计算快、离散度高。通过选取种子（如 131），对字符串每个字符进行处理。

size_t BKDRHash(const std::string &str) {
    size_t seed = 131; // 常用种子：31, 131, 1313...
    size_t hash = 1;
    for (auto e : str) {
        hash *= seed;
        hash += e;
    }
    return hash & 0x7FFFFFFF; // 确保返回正数
}

异或组合

适用于 vector<int> 等简单场景，实现简单但冲突率相对较高。

struct PointHash {
    size_t operator()(const std::vector<int> &vec) const {
        int hash = 0;
        for (auto e : vec) {
            hash ^= (e << 1);
        }
        return hash;
    }
};

hash_combine

推荐用于多成员结构体，冲突率低。

template <typename T>
void hash_combine(std::size_t& seed, const T& val) {
    seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

struct Person {
    std::string name;
    int age;
    bool operator==(const Person& p) const {
        return name == p.name && age == p.age;
    }
};

struct PersonHash {
    std::size_t operator()(const Person& p) const {
        std::size_t seed = 0;
        hash_combine(seed, p.name);
        hash_combine(seed, p.age);
        return seed;
    }
};

常见哈希函数

直接定址法

数学上的单调函数，每个哈希值对应唯一映射位置，无冲突。但仅适用于数据集中的情况，若数据分散则浪费空间。

除留余数法

最常用的方法。取模运算 key % p，其中 p 为不大于表长且接近表长的质数。例如表长为 10，可选 p=7。

平方取中法

取关键字平方后的中间几位作为地址。例如 key=1234，平方为 1522756，取中间三位 227 作为地址。此法能较好打散连续键值。

基数转换法

将十进制转为其他进制（如十六进制），视作新数字后取模。若含字母则转 ASCII 码。

哈希冲突解决

负载因子（已插入数据个数 / 表大小）越大，冲突概率越高。负载因子通常控制在 0.7 以下。常见解决方案有两种：开放定址法和哈希桶。

开放定址法

冲突时向后偏移寻找空位。探测方式包括线性探测（逐个遍历）和二次探测（按平方数间隔）。

删除操作需注意标记状态。若直接清空，查找时会误判结束。因此需要 EMPTY（空）、EXIST（存在）、DELETE（已删除）三种状态。查找时需跳过 DELETE 继续向后，直到遇到 EMPTY。

template <class K, class V>
class HashData {
public:
    enum State { EMPTY, EXIST, DELETE };
    std::pair<K, V> _kv;
    State _state;
};

template <class K, class V>
class HashTable {
private:
    std::vector<HashData<K, V>> _tables;
    size_t _n = 0;

public:
    bool insert(const std::pair<K, V> &kv) {
        if (_tables.empty() || (_n * 10) / _tables.size() >= 7) {
            UpMemory();
        }
        if (Find(kv.first)) return false;

        int hashi = kv.first % _tables.size();
        while (_tables[hashi]._state == HashData<K, V>::State::EXIST) {
            hashi++;
            hashi %= _tables.size();
        }
        _tables[hashi]._kv = kv;
        _tables[hashi]._state = HashData<K, V>::State::EXIST;
        _n++;
        return true;
    }

    HashData<K, V>* Find(const K &key) {
        int hashi = key % _tables.size();
        int tmp = hashi;
        while (_tables[hashi]._state != HashData<K, V>::EMPTY) {
            if (_tables[hashi]._state == HashData<K, V>::EXIST && 
                _tables[hashi]._kv.first == key) {
                return &_tables[hashi];
            }
            hashi++;
            hashi %= _tables.size();
            if (hashi == tmp) return nullptr;
        }
        return nullptr;
    }

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

private:
    void UpMemory() {
        int newsize = _tables.empty() ? 5 : _tables.size() * 2;
        HashTable<K, V> NewHT;
        NewHT._tables.resize(newsize);
        for (int i = 0; i < _tables.size(); ++i) {
            if (_tables[i]._state == HashData<K, V>::State::EXIST) {
                NewHT.insert(_tables[i]._kv);
            }
        }
        _tables.swap(NewHT._tables);
    }
};

哈希桶（链地址法）

哈希桶本质上是一个数组，每个元素挂接一个链表。冲突时创建节点链入该位置。STL 的 unordered_map 和 unordered_set 均基于此结构。

在负载因子为 1 时，随机数据的桶长度通常保持在常数级别，效率优于开放定址法。

unordered_map 与 unordered_set 的复用

为了共用底层哈希桶模板类，设计者巧妙利用了模板参数：

• unordered_set 传入的 Value 类型为 Key。
• unordered_map 传入的 Value 类型为 pair<Key, T>。

这样，查找和删除只需 Key，而插入时根据 Value 类型不同自然适配。

// 哈希桶定义
template<class Key, class Value, class Alloc, class ExtractKey, class Hash, class __Pred>
class HashBucket {
    // ... Find, Erase, Insert 实现 ...
};

// unordered_set 封装
template<class Key, class Hash, class Pred>
class unordered_set {
    typedef HashBucket<Key, Key, ..., KeyOfValue, Hash, Pred> HT;
    HT _ht;
    struct KeyOfValue { const Key& operator()(const Key& key) { return key; } };
    // ... 调用 _ht.Insert(data) ...
};

// unordered_map 封装
template<class Key, class T, class Hash, class Pred>
class unordered_map {
    typedef HashBucket<Key, std::pair<Key, T>, ..., KeyOfValue, Hash, Pred> HT;
    HT _ht;
    struct KeyOfValue { const Key& operator()(const std::pair<Key, T>& kv) { return kv.first; } };
    // ... 调用 _ht.Insert(data) ...
};

自定义类型键的处理

对于自定义类型，无法直接取模。需通过第五个模板参数 Hash 提供哈希值计算策略。同时，查找时需要比较两个对象是否相等，因此提供第六个模板参数 Pred（Equal 仿函数）。

底层插入伪代码如下：

insert(const Value &data) {
    KeyOfT key;
    int hashi = key(data) % _tables.size(); // 利用提取的 Key 计算哈希
    Node* newnode = new Node(data);
    newnode->_next = _tables[hashi];
    _tables[hashi] = newnode;
}

综上，哈希表的设计核心在于平衡空间与时间复杂度，而 STL 的实现则通过泛型编程最大化了复用性与灵活性。