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

哈希冲突的影响

• 性能下降：冲突都会增加一次操作的时间。理想情况下哈希表操作是 O(1)，冲突后可能退化为 O(n)。
• 设计权衡：好的哈希函数应尽量让元素分布均匀，减少冲突概率。

1.4 哈希函数

哈希函数负责将关键码（Key）映射为一个数组下标（哈希地址）。

一个好的哈希函数应当满足以下原则：

1. 定义域与值域的匹配：值域必须正好是数组索引区间。
2. 均匀分布：计算出的地址应该尽可能均匀地分布在整个空间中。
3. 简单高效：计算应该足够简单、快速。

两种常见的哈希函数构造方法

1. 直接定址法

公式：Hash(Key) = A * Key + B

直接使用关键码本身（或它的线性变换）作为哈希地址。适用于关键码是整数且取值范围较小且连续的情况。

2. 除留余数法

公式：Hash(Key) = Key % p

其中 p 是一个不大于哈希表长度 m 的质数。这种方法能将任意整数关键码压缩到 0 ~ p-1 的范围内。

1.5 解决哈希冲突的常用方法

我们来深入探讨哈希冲突解决的两种常用方法：线性探测法和哈希桶（即链地址法）。

1.5.1 线性探测法

1. 原理：属于开放寻址法的一种。当发生哈希冲突时，它会依次检查冲突位置的下一个位置，直到找到一个空闲的槽位。
2. 操作过程：
   • 插入：计算哈希地址，若被占用则向后探测，直到找到空位。
   • 查找：计算哈希地址，若不相等则继续线性探测，直到遇到空槽或遍历一圈。
   • 删除：不能简单地将槽位置空，通常采用惰性删除：将删除的槽位标记为'已删除'，查找时遇到'已删除'标记继续探测。
3. 优点：实现简单，无需额外指针，缓存友好。
4. 缺点：容易产生聚集现象，删除麻烦，对负载因子敏感。

1.5.2 哈希桶

1. 原理：将哈希表的每个槽位设置为一个链表的头节点。所有哈希地址相同的元素都放入对应槽位的链表中。
2. 操作过程：
   • 插入：找到对应桶的链表，将新节点插入链表。
   • 查找：计算索引，然后在对应链表中顺序查找。
   • 删除：在链表中找到目标节点并删除。
3. 优点：简单直接，删除方便，哈希表永远不会填满。
4. 缺点：需要额外的指针空间，缓存不友好。

二、使用线性探测法模拟实现哈希表

使用开放地址法中的线性探测法，需要借助状态标记。

首先，要实现哈希表，我们得定义出一些东西出来：

// 哈希表中每个位置的状态标记
enum STATE { 
    EXIST, // 当前位置有有效数据 
    EMPTY, // 当前位置为空 
    DELETE // 当前位置的数据已被删除（逻辑删除） 
}; 

// 哈希表存储的数据节点结构
template<class K, class V>
struct HashData {
    pair<K, V> _kv; // 存储的键值对
    STATE _state = EMPTY; // 当前节点的状态，默认为空
};

2.1 哈希函数

我们需要定义哈希函数对象。对于不同类型（如整数、字符串），可以使用模板特化。

// 默认的哈希函数对象（适用于整数等可直接转换为 size_t 的类型）
template<class K>
struct DefaultHashFunc {
    size_t operator()(const K& key) {
        return (size_t)key;
    }
};

// 对 string 类型的特化哈希函数（使用 BKDR 算法）
template<>
struct DefaultHashFunc<string> {
    size_t operator()(const string& str) {
        size_t hash = 0;
        for (auto ch : str) {
            hash *= 131;
            hash += ch;
        }
        return hash;
    }
};

2.2 哈希表类

// 哈希表类，使用开放地址法（线性探测）解决冲突
template<class K, class V, class HashFunc = DefaultHashFunc<K>>
class HashTable {
public:
    // 构造函数：初始化哈希表大小（默认 10）
    HashTable() {
        _table.resize(10);
    }
private:
    vector<HashData<K, V>> _table;
    size_t _n = 0; // 当前哈希表中有效数据的个数
};

2.2.1 插入操作

整个插入操作分为两步：判断是否需要扩容，以及通过线性探测法插入新元素。

bool Insert(const pair<K, V>& kv) {
    // 扩容判断：负载因子 >= 0.7 时扩容
    if (_n * 10 / _table.size() >= 7) {
        size_t newSize = _table.size() * 2;
        HashTable<K, V, HashFunc> newHT;
        newHT._table.resize(newSize);
        // 遍历旧表，将所有状态为 EXIST 的节点重新插入到新表
        for (size_t i = 0; i < _table.size(); i++) {
            if (_table[i]._state == EXIST) {
                newHT.Insert(_table[i]._kv);
            }
        }
        _table.swap(newHT._table);
    }

    // 线性探测法寻找插入位置
    HashFunc hf;
    size_t hashi = hf(kv.first) % _table.size();
    while (_table[hashi]._state == EXIST) {
        ++hashi;
        hashi %= _table.size();
    }
    _table[hashi]._kv = kv;
    _table[hashi]._state = EXIST;
    ++_n;
    return true;
}

2.2.2 查询操作

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

2.2.3 删除操作

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

2.3 完整代码 + 测试

（此处省略完整的头文件 test.cpp 代码展示，主要包含插入、查找、删除及扩容测试逻辑）

三、使用哈希桶模拟实现哈希表

哈希桶（Hash Bucket）就是链地址法的一种实现方式。每个桶对应一个链表，所有映射到同一索引的键值对都存储在这个桶所指向的链表中。

3.1 哈希函数

复用之前的哈希函数定义。

3.2 哈希表类

template <class K, class V, class HashFunc = DefaultHashFunc<K>>
class HashTable {
    typedef HashNode<K, V> Node;
public:
    HashTable() {
        _table.resize(10, nullptr);
    }
    ~HashTable() {
        for (size_t i = 0; i < _table.size(); i++) {
            Node *cur = _table[i];
            while (cur) {
                Node *next = cur->_next;
                delete cur;
                cur = next;
            }
            _table[i] = nullptr;
        }
    }
    // ... 其他成员函数
private:
    vector<Node *> _table;
    size_t _n = 0;
};

3.2.1 插入操作

bool Insert(const pair<K, V> &kv) {
    if (Find(kv.first)) {
        return false;
    }
    HashFunc hf;
    // 扩容：当负载因子达到 1 时，将桶数组大小扩大为原来的 2 倍
    if (_n == _table.size()) {
        size_t newSize = _table.size() * 2;
        vector<Node *> newTable;
        newTable.resize(newSize, nullptr);
        // 遍历旧表，将每个节点重新哈希并头插到新表
        for (size_t i = 0; i < _table.size(); i++) {
            Node *cur = _table[i];
            while (cur) {
                Node *next = cur->_next;
                size_t hashi = hf(cur->_kv.first) % newSize;
                cur->_next = newTable[hashi];
                newTable[hashi] = cur;
                cur = next;
            }
            _table[i] = nullptr;
        }
        _table.swap(newTable);
    }
    size_t hashi = hf(kv.first) % _table.size();
    Node *newnode = new Node(kv);
    newnode->_next = _table[hashi];
    _table[hashi] = newnode;
    ++_n;
    return true;
}

3.2.2 查询操作

Node *Find(const K &key) {
    HashFunc hf;
    size_t hashi = hf(key) % _table.size();
    Node *cur = _table[hashi];
    while (cur) {
        if (cur->_kv.first == key) {
            return cur;
        }
        cur = cur->_next;
    }
    return nullptr;
}

3.2.3 删除操作

bool Erase(const K &key) {
    HashFunc hf;
    size_t hashi = hf(key) % _table.size();
    Node *prev = nullptr;
    Node *cur = _table[hashi];
    while (cur) {
        if (cur->_kv.first == key) {
            if (prev == nullptr) {
                _table[hashi] = cur->_next;
            } else {
                prev->_next = cur->_next;
            }
            delete cur;
            --_n;
            return true;
        }
        prev = cur;
        cur = cur->_next;
    }
    return false;
}

3.3 完整代码 + 测试

（包含完整的 HashTable.hpp 和 test.cpp 实现，支持整型和字符串类型测试）

四、模拟实现 unordered_map 和 unordered_set

C++ STL 库里面的 unordered_map 和 unordered_set 的底层实现都是基于哈希表来模拟实现的。

4.1 引入迭代器

这段代码实现了一个哈希表的正向迭代器，支持普通迭代器和 const 迭代器。

template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
struct HTIterator {
    typedef HashNode<T> Node;
    typedef HTIterator<K, T, Ptr, Ref, KeyOfT, HashFunc> Self;
    Node* _node;
    const HashTable<K, T, KeyOfT, HashFunc>* _pht;
    // ... 构造函数及运算符重载
};

4.2 修改哈希表代码

引入迭代器后，需要修改哈希表类以支持 begin() 和 end() 接口，并修改 Insert 返回值为 pair<iterator, bool>。

4.3 模拟实现 unordered_map

namespace mySTL {
template<class K, class V>
class unordered_map {
    struct MapKeyOfT {
        const K& operator()(const pair<const K, V>& kv) {
            return kv.first;
        }
    };
public:
    typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
    iterator begin() { return _ht.begin(); }
    iterator end() { return _ht.end(); }
    pair<iterator, bool> insert(const pair<K, V>& kv) {
        return _ht.Insert(kv);
    }
    V& operator[](const K& key) {
        pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
        return ret.first->second;
    }
private:
    hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT> _ht;
};
}

4.4 模拟实现 unordered_set

namespace mySTL {
template<class K>
class unordered_set {
    struct SetKeyOfT {
        const K& operator()(const K& key) {
            return key;
        }
    };
public:
    typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator iterator;
    pair<iterator, bool> insert(const K& key) {
        pair<typename hash_bucket::HashTable<K, K, SetKeyOfT>::iterator, bool> ret = _ht.Insert(key);
        return pair<iterator, bool>(ret.first, ret.second);
    }
private:
    hash_bucket::HashTable<K, K, SetKeyOfT> _ht;
};
}

（测试程序验证了插入、查找、删除及迭代器遍历功能）