C++ 哈希表实现：unordered_map/set、位图与布隆过滤器

使用 EXIST, EMPTY, DELETE 状态标记。删除时将状态设为 DELETE 而非 EMPTY，以便线性探测查找能继续穿过已删除位置。扩容时跳过 DELETE 状态节点。

负载因子越大，冲突概率越高但空间利用率越高；反之亦然。需控制负载因子避免性能下降。

开散列的模拟实现

开散列又称链地址法，每个桶是一个链表。

template<class K, class T, class KeyOfT, class HashFunc = DefaultHashFunc<K>>
class HashTable {
    typedef HashNode<T> Node;
    template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
    friend struct HTIterator;

public:
    typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;
    typedef HTIterator<K, T, const T*, const T&, KeyOfT, HashFunc> const_iterator;

    iterator begin() {
        for (size_t i = 0; i < _table.size(); i++) {
            Node* cur = _table[i];
            if (cur) return iterator(cur, this);
        }
        return iterator(nullptr, this);
    }

    iterator end() { return iterator(nullptr, this); }

    const_iterator begin() const {
        for (size_t i = 0; i < _table.size(); i++) {
            Node* cur = _table[i];
            if (cur) return const_iterator(cur, this);
        }
        return const_iterator(nullptr, this);
    }

    const_iterator end() const { return const_iterator(nullptr, this); }

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

    bool Insert(const T& data) {
        KeyOfT kot;
        iterator it = Find(kot(data));
        if (it != end()) return make_pair(it, false);

        HashFunc hf;
        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(kot(cur->_data)) % newSize;
                    cur->_next = newTable[hashi];
                    newTable[hashi] = cur;
                    cur = next;
                }
                _table[i] = nullptr;
            }
            _table.swap(newTable);
        }

        size_t hashi = hf(kot(data)) % _table.size();
        Node* newnode = new Node(data);
        newnode->_next = _table[hashi];
        _table[hashi] = newnode;
        ++_n;
        return make_pair(iterator(newnode, this), true);
    }

    Node* Find(const K& key) {
        HashFunc hf;
        KeyOfT kot;
        size_t hashi = hf(key) % _table.size();
        Node* cur = _table[hashi];
        while (cur) {
            if (kot(cur->_data) == key) return iterator(cur, this);
            cur = cur->_next;
        }
        return end();
    }

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

private:
    vector<Node*> _table;
    size_t _n = 0;
};

负载因子达到 1 时扩容。扩容时将旧表节点逐个拆下挂到新表。删除节点时需处理前驱指针。若链表长度过长可优化为红黑树结构。

哈希桶里面迭代器的模拟实现

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;
    typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> Iterator;

    Node* _node;
    HashTable<K, T, KeyOfT, HashFunc>* _pht;

    HTIterator(Node* node, const HashTable<K, T, KeyOfT, HashFunc>* pht)
        : _node(node), _pht(pht) {}

    HTIterator(const Iterator& it) : _node(it._node), _pht(it._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;
                } else {
                    ++hashi;
                }
            }
            _node = nullptr;
        }
        return *this;
    }

    bool operator!=(const Self& s) { return _node != s._node; }
    bool operator==(const Self& s) { return _node == s._node; }
};

迭代器需访问哈希表内部结构，使用前向声明解决循环依赖问题。

unordered_set 的封装

namespace renshen {
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;
    typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::const_iterator const_iterator;

    iterator begin() { return _ht.begin(); }
    iterator end() { return _ht.end(); }

    pair<const_iterator, bool> insert(const K& key) {
        pair<typename hash_bucket::HashTable<K, K, SetKeyOfT>::iterator, bool> ret = _ht.Insert(key);
        return pair<const_iterator, bool>(ret.first, ret.second);
    }

private:
    hash_bucket::HashTable<K, K, SetKeyOfT> _ht;
};
}

unordered_map 的封装

namespace renshen {
template<class K, class V>
class unordered_map {
    struct MapKeyOfT {
        const K& operator()(const pair<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(); }
    const_iterator begin() const { return _ht.begin(); }
    const_iterator end() const { 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;
};
}

位图

位图利用比特位表达信息，标准库中有 bitset 实现，常用接口包括 test, set, reset。

应用

面试题：给定 40 亿个不重复无符号整数，快速判断某整数是否存在。

使用 set 或排序 + 二分查找空间开销过大。位图方案：一个 int 占 32 比特位，可用比特位表示数值存在性。

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

    void reset(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;
};

位图可用于求交集：将两个文件映射到位图，对应位置均为 1 则为交集。内存限制下可使用哈希切割配合位图。

布隆过滤器

布隆过滤器利用多个独立哈希函数 + 位图实现高效存在性判断。若所有哈希位置均为 1，则可能存在；否则一定不存在。

应用场景：快速判断昵称是否注册过。精确场景需二次查询数据库。

布隆过滤器的模拟实现

template<size_t N, class K, class Hash1, class Hash2, class Hash3>
class BloomFilter {
public:
    void Set(const K& key) {
        size_t hash1 = Hash1()(key) % N;
        _bs.set(hash1);
        size_t hash2 = Hash2()(key) % N;
        _bs.set(hash2);
        size_t hash3 = Hash3()(key) % N;
        _bs.set(hash3);
    }

    bool Test(const K& key) {
        size_t hash1 = Hash1()(key) % N;
        if (_bs.test(hash1) == false) return false;
        size_t hash2 = Hash2()(key) % N;
        if (_bs.test(hash2) == false) return false;
        size_t hash3 = Hash3()(key) % N;
        if (_bs.test(hash3) == false) return false;
        return true;
    }

private:
    bitset<N> _bs;
};

布隆过滤器一般不支持删除操作，否则会导致误判。如需删除需引入引用计数。优化参数涉及哈希函数个数 k、位图长度 m 和元素个数 n。

哈希切割

运用哈希函数将大文件数据分片到多个小文件。

哈希切割的应用

问题：两个 100 亿 query 文件，1G 内存，找交集。

• 近似算法：布隆过滤器。
• 精确算法：哈希切割。两文件用相同哈希函数分片，相同 query 进入同编号文件，分别比对。

若内存不足，说明冲突过多，需更换哈希函数二次切分。

作业部分

1. 散列函数有一个共同性质，即函数值应按（）取其值域的每一个值。

   • 答案：C. 同等概率

2. 解决散列法中出现冲突问题常采用的方法是（D）

   • A. 数字分析法、除余法、平方取中法
   • B. 数字分析法、除余法、线性探测法
   • C. 数字分析法、线性探测法、多重散列法
   • D. 线性探测法、多重散列法、链地址法

3. 已知关键字序列：（19，14,23,1,68,20,84,27,55,11,10,79），H（key）=key%7，链地址法，平均查找长度为（A）

   • 答案：A. 1.5

4. 关于位图说法错误的是（D）

   • D. 位图可以很方便的进行字符串的映射以及查找
   • 解析：一般不用位图处理字符串，字符串转整型易冲突。

5. 力扣 350. 两个数组的交集 II

   • 核心：防止重复统计，统计后记为 0。

6. 力扣 884. 两句话中的不常见单词

   • 引申：只有 multi_map 和 multi_set 的 count 返回出现次数，其他容器返回 1 或 0。

7. 关于 unordered_map 和 unordered_set 说法错误的是（D）

   • D. 它们在进行元素插入时，都得要通过 key 的比较去找待插入元素的位置
   • 解析：插入时通过哈希值定位，无需 key 比较。