C++ 哈希表原理与线性探测、哈希桶模拟实现

核心操作实现

插入与扩容

插入前检查负载因子。若 _n * 10 / _table.size() >= 7，则触发扩容。扩容时递归调用 Insert 将旧数据迁移至新表，注意避免重复扩容。

template<class K, class V, class HashFunc = DefaultHashFunc<K>>
class HashTable {
public:
    HashTable() { _table.resize(10); }

    bool Insert(const pair<K, V>& kv) {
        if (_n * 10 / _table.size() >= 7) {
            size_t newSize = _table.size() * 2;
            HashTable<K, V, HashFunc> newHT;
            newHT._table.resize(newSize);
            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;
    }

    // Find 和 Erase 实现略，遵循线性探测规则
private:
    vector<HashData<K, V>> _table;
    size_t _n = 0;
};

删除逻辑

删除不能直接置空，否则会切断后续元素的探测路径。采用惰性删除，将状态设为 DELETE。查找时遇到 DELETE 继续探测，插入时可复用该位置。

哈希桶（链地址法）模拟实现

哈希桶将每个槽位视为链表头。冲突时直接将新节点插入对应桶的链表中。相比开放寻址，它永远不会填满，但内存开销稍大。

节点与类结构

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

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

插入与扩容

当负载因子达到 1（节点数等于桶数）时扩容。遍历旧表，重新计算哈希地址并将节点头插到新表。注意保存 next 指针以防丢失。

bool Insert(const pair<K, V>& kv) {
    if (Find(kv.first)) return false;
    
    if (_n == _table.size()) {
        size_t newSize = _table.size() * 2;
        vector<Node*> newTable(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.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;
}

删除操作

在链表中定位目标节点，修改前驱节点的 next 指针跳过当前节点，并释放内存。无需特殊标记。

模拟 STL 容器

C++ STL 中的 unordered_map 和 unordered_set 底层均基于哈希表。我们通过引入迭代器来封装底层细节。

迭代器设计

迭代器需支持跨桶遍历。当当前桶链表遍历完后，需自动跳转到下一个非空桶。模板参数区分普通迭代器和 const 迭代器。

template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
struct HTIterator {
    typedef HashNode<T> Node;
    Node* _node;
    const HashTable<K, T, KeyOfT, HashFunc>* _pht;

    Self& operator++() {
        if (_node->_next) {
            _node = _node->_next;
        } else {
            KeyOfT kot;
            HashFunc hf;
            size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
            ++hashi;
            while (hashi < _pht->_table.size()) {
                if (_pht->_table[hashi]) {
                    _node = _pht->_table[hashi];
                    return *this;
                }
                ++hashi;
            }
            _node = nullptr;
        }
        return *this;
    }
    // ... operator!=, operator* 等省略
};

unordered_map 实现

使用 pair<const K, V> 存储数据，通过仿函数提取键。insert 返回 pair<iterator, bool>，operator[] 支持默认构造值的插入。

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

unordered_set 实现

类似地，存储类型即为键本身 K，使用 SetKeyOfT 提取键。迭代器统一为 const 版本，因为 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) {
        auto ret = _ht.Insert(key);
        return pair<iterator, bool>(ret.first, ret.second);
    }
private:
    hash_bucket::HashTable<K, K, SetKeyOfT> _ht;
};
}

通过上述步骤，我们完整实现了从底层哈希表到上层 STL 容器的模拟，涵盖了冲突解决、动态扩容及迭代器协议，深入理解了 C++ 标准库背后的设计逻辑。