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

线性探测实现简单，但容易产生'堆积'现象，导致搜索效率下降。二次探测虽缓解此问题，但对空间利用率要求较高。

2.4.2 开散列（链地址法）

开散列将哈希地址相同的元素挂在同一链表上。每个桶指向一个单链表头结点。

优势：相比闭散列，开散列不需要预留大量空闲空间，空间利用率更高，且扩容时只需重新分配桶数组，链表节点复用。

namespace hash_bucket { 
    template<class T> struct HashNode { 
        T _data; 
        HashNode<T>* _next; 
        HashNode(const T& data) :_data(data), _next(nullptr) {} 
    }; 
    
    template<class K, class T, class KeyOfT, class HashFunc> 
    class HashTable; 
    
    template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc> 
    struct HTIterator { 
        typedef HashNode<T> Node; 
        typedef HTIterator Self; 
        Node* _node; 
        const HashTable<K, T, KeyOfT, HashFunc>* _pht; 
        
        HTIterator(Node* node, const HashTable<K, T, KeyOfT, HashFunc>* pht) 
            :_node(node), _pht(pht) {} 
        
        Ref operator*() { return _node->_data; } 
        Ptr operator->() { return &_node->_data; } 
        
        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; 
        } 
        bool operator!=(const Self& s) { return _node != s._node; } 
    }; 
}

扩容策略：当负载因子达到 1 时触发扩容。为了保持哈希均匀性，新表大小应选取大于原大小的最小质数。

size_t GetNextPrime(size_t prime) { 
    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 
    }; 
    for (size_t i = 0; i < __stl_num_primes; ++i) { 
        if (__stl_prime_list[i] > prime) return __stl_prime_list[i]; 
    } 
    return __stl_prime_list[__stl_num_primes - 1]; 
}

2.5 闭散列与开散列对比

开散列需要额外的指针空间，但闭散列为保证效率必须保留大量空闲槽位。综合来看，开散列在大多数实际场景中更节省内存且性能稳定。

三、模拟实现总结

基于上述原理，我们可以封装出完整的 unordered_map 和 unordered_set。

3.1 模板改造

引入 KeyOfT 提取器以支持自定义类型作为 Key，同时增加迭代器支持以便范围遍历。

3.2 unordered_map 封装

利用 HashTable 存储 pair<const K, V>，通过 MapKeyOfT 提取 Key。operator[] 重载简化了插入与访问逻辑。

#include"HashTable.h"
namespace lxp {
    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;
        typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT>::const_iterator const_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;
    };
}

3.3 unordered_set 封装

本质上是 Key 与 Value 均为 Key 的 map，SetKeyOfT 直接返回自身。

四、哈希进阶应用

4.1 位图（Bitmap）

场景：40 亿个无符号整数中判断某数是否存在。

传统方法耗时耗力，位图利用二进制位表示存在状态，仅需 40 亿 bits（约 500MB），空间效率极高。

#include<vector>
#include<iostream>
using namespace std;
namespace lxp {
    template<size_t N> class bitset {
    public:
        bitset() { _a.resize(N / 32 + 1); }
        void set(size_t x) {
            size_t i = x / 32; size_t j = x % 32;
            _a[i] |= (1 << j);
        }
        bool test(size_t x) {
            size_t i = x / 32; size_t j = x % 32;
            return _a[i] & (1 << j);
        }
    private:
        vector<int> _a;
    };
}

4.2 布隆过滤器（Bloom Filter）

提出背景：新闻客户端推荐去重。用户历史记录海量，用哈希表太占空间，位图仅支持整形。

原理：结合多个哈希函数将元素映射到位图中。若所有对应位均为 1，则认为可能存在；只要有一位为 0，则一定不存在。

优缺点：

• 优点：O(K) 时间复杂度，不存元素本身，空间极省。
• 缺点：有假阳性率（误判），不支持删除（除非扩展为计数位图）。

template<size_t N, size_t X = 5, class K = string, 
     class HashFunc1 = BKDRHash, class HashFunc2 = APHash, class HashFunc3 = DJBHash> 
class BloomFilter {
public:
    void Set(const K& key) {
        size_t len = X * N;
        _bs.set(HashFunc1()(key) % len);
        _bs.set(HashFunc2()(key) % len);
        _bs.set(HashFunc3()(key) % len);
    }
    bool Test(const K& key) {
        size_t len = X * N;
        if (!_bs.test(HashFunc1()(key) % len)) return false;
        if (!_bs.test(HashFunc2()(key) % len)) return false;
        if (!_bs.test(HashFunc3()(key) % len)) return false;
        return true;
    }
private:
    bitset<X* N> _bs;
};

布隆过滤器在分布式系统缓存、垃圾邮件过滤等场景非常实用，但需注意其不可逆的特性。