C++ 哈希（下）

本章是了解哈希模拟实现和哈希的应用场景，上一章我们了解哈希的使用和解决哈希冲突的方法：闭散列和开散列。

模拟实现

哈希表的改造

1. 模板参数列表的改造
   我们知道unordered_map 是<key,value> 结构，unordered_set是<key>结构，那么为了让其都能共享底层结构，就需要对模板进行改造处理。

改造时我们要考虑一个问题就是unordered_map存的是 pair<K, V>。节点里如果直接存 pair，那算哈希地址和比较的时候，怎么把 K 抽出来？
这里的解决方案和map的解决方法一样，通过仿函数给K给抽出来。

// 以 unordered_map 为例
struct KeyOfValue {
    const K& operator()(const pair<const K, V>& data) {
        return data.first; // 重点：只返回 first
    }
};

// 类模板变成：
template<class K, class V, class KeyOfValue, class HF>
class HashBucket {
    // 插入时调用：
    size_t HashFunc(const V& data) {
        return HF()(KeyOfValue()(data)) % _ht.size(); // 先用 KeyOfValue 拔出 key，再用 HF 算哈希
    }
};

2. 增加迭代器操作

template<class K, class V, class KeyOfValue, class HF>
struct HBIterator {
    typedef HashBucket<K, V, KeyOfValue, HF> HT;
    typedef HashBucketNode<V>* PNode;
    typedef HBIterator<K, V, KeyOfValue, HF> Self;

    PNode _pNode; // 当前节点
    HT* _pHt;     // 当前哈希表指针（为了跨桶找下一个元素）

    HBIterator(PNode pNode = nullptr, HT* pHt = nullptr) : _pNode(pNode), _pHt(pHt) {}

    // 核心：++ 操作
    Self& operator++() {
        if (_pNode->_pNext) {
            // 1. 当前桶还没走完，直接去下一个节点
            _pNode = _pNode->_pNext;
        }
        else {
            // 2. 当前桶走完了，去后面的桶找
            // 先算出当前所在的桶号（用 KeyOfValue 取出 K，再用 HF 算哈希）
            size_t bucketNo = _pHt->HashFunc(KeyOfValue()(_pNode->_data)) + 1;

            for (; bucketNo < _pHt->_ht.size(); ++bucketNo) {
                if (_pHt->_ht[bucketNo]) { // 找到了非空桶
                    _pNode = _pHt->_ht[bucketNo];
                    break;
                }
            }
            // 如果后面全空了，说明遍历结束
            if (bucketNo == _pHt->_ht.size()) _pNode = nullptr;
        }
        return *this;
    }

    V& operator*() { return _pNode->_data; }
    V* operator->() { return &_pNode->_data; }
    bool operator==(const Self& it) const { return _pNode == it._pNode; }
    bool operator!=(const Self& it) const { return _pNode != it._pNode; }
};

注意：哈希底层是单向链表，无法回头。所以哈希迭代器不需要实现–操作。
3. 补充通用函数接口

template<class K, class V, class KeyOfValue, class HF = DefHashF<K>>
class HashBucket {
    friend struct HBIterator<K, V, KeyOfValue, HF>;
    typedef HashBucketNode<V> Node;
    typedef Node* PNode;
public:
    typedef HBIterator<K, V, KeyOfValue, HF> Iterator;

    HashBucket(size_t capacity = 11) : _size(0) { _ht.resize(capacity, nullptr); }

    Iterator Begin() {
        for (size_t i = 0; i < _ht.size(); ++i) {
            if (_ht[i]) return Iterator(_ht[i], this);
        }
        return End(); // 全空，返回 end
    }
    Iterator End() { return Iterator(nullptr, this); }

    // 插入接口修改：返回 pair<Iterator, bool>，为了后续封装 operator[] 做准备
    pair<Iterator, bool> Insert(const V& data) {
        if (_size == _ht.size()) _CheckCapacity();

        size_t bucketNo = HashFunc(KeyOfValue()(data));
        PNode pCur = _ht[bucketNo];
        while (pCur) {
            if (KeyOfValue()(pCur->_data) == KeyOfValue()(data))
                return make_pair(Iterator(pCur, this), false); // 已存在
            pCur = pCur->_pNext;
        }
        // 头插法
        pCur = new Node(data);
        pCur->_pNext = _ht[bucketNo];
        _ht[bucketNo] = pCur;
        _size++;
        return make_pair(Iterator(pCur, this), true);
    }

    // 查找接口
    Iterator Find(const K& key) {
        size_t bucketNo = HashFunc(key);
        PNode pCur = _ht[bucketNo];
        while (pCur) {
            if (KeyOfValue()(pCur->_data) == key) return Iterator(pCur, this);
            pCur = pCur->_pNext;
        }
        return End();
    }

    // 删除接口：返回下一个节点的迭代器
    Iterator Erase(const K& key) {
        size_t bucketNo = HashFunc(key);
        PNode pCur = _ht[bucketNo];
        PNode pPrev = nullptr;
        while (pCur) {
            if (KeyOfValue()(pCur->_data) == key) {
                // 处理头删和中间删除
                if (pCur == _ht[bucketNo]) _ht[bucketNo] = pCur->_pNext;
                else pPrev->_pNext = pCur->_pNext;
                
                PNode pRet = pCur->_pNext; // 记录下一个节点
                delete pCur;               // 释放内存
                _size--;
                return Iterator(pRet, this); // 返回下一个节点的迭代器
            }
            pPrev = pCur;
            pCur = pCur->_pNext;
        }
        return End();
    }

};

解释一下这里find和erase为什么要有返回End()，因为当find的查找我们在之前的使用接口的时候展示过当== end()时就证明没有找到key，所以这里返回End()。erase就有两种情况一种是删完了，一种是key不存在为了方便统一返回End().

unordered_map

template<class K, class V, class HF = DefHashF<K>>
class unordered_map {
	typedef pair<const K, V> ValueType;

	// 告诉底层，如何从 pair 中提取 K
	struct KeyOfValue {
		const K& operator()(const ValueType& data) { return data.first; }
	};

	typedef HashBucket<K, ValueType, KeyOfValue, HF> HT;
public:
	typedef typename HT::Iterator iterator;

	unordered_map() : _ht() {}

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

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

	iterator find(const K& key) { return _ht.Find(key); }

	// 插入
	pair<iterator, bool> insert(const ValueType& val) { return _ht.Insert(val); }

	// 删除（支持迭代器遍历时删除）
	iterator erase(const K& key) { return _ht.Erase(key); }

	// operator[]
	V& operator[](const K& key) {
		// 如果 key 不存在，插入 (key, V())，返回该默认值的引用
		pair<iterator, bool> ret = _ht.Insert(ValueType(key, V()));
		return ret.first->second; // 返回 value
	}

private:
	HT _ht;
};

unordered_set

template<class K, class HF = DefHashF<K>>
class unordered_set {
    typedef K ValueType;

    // 提取 Key 的仿函数：set 存的不是 pair，就是 key，直接返回
    struct KeyOfValue {
        const K& operator()(const ValueType& data) { return data; }
    };

    typedef HashBucket<K, ValueType, KeyOfValue, HF> HT;

public:
    typedef typename HT::Iterator iterator;

    unordered_set() : _ht() {}

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


    // set 的 insert 只需传入 K
    pair<iterator, bool> insert(const ValueType& val) { return _ht.Insert(val); }

    iterator erase(const K& key) { return _ht.Erase(key); }

    iterator find(const K& key) { return _ht.Find(key); }

private:
    HT _ht;
};

哈希的应用

位图

位图概念

所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用
来判断某个数据存不存在的。

为什么需要位图
哈希有一个经典面试题：
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在
这40亿个数中。

1. 遍历一次：$O(N)$
2. 排序：$O(NlogN)$，二分查找$O(logN)$
3. 位图解决
   数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。比如：
   
   为什么不用unordered_set解决？
   因为一个整数我们算是4字节的大小，40亿个整肃就是 14GB左右的内存，这无疑是对内存一次巨大的考验，一般电脑还够呛。位图只需要512MB左右的内存空间

位图的实现

template<size_t N>
class bitset {
public:
	bitset() {
		// 向上取整，比如 N=10，10/32=0，其实需要 1 个 int
		_bits.resize(N / 32 + 1, 0);
	}

	// 置1
	void set(size_t x)
	{
		size_t index = x / 32;
		size_t bitPos = x % 32;

		_bits[index] |= (1 << bitPos);
	}

	// 置0
	void reset(size_t x)
	{
		size_t index = x / 32;
		size_t bitPos = x % 32;

		_bits[index] &= ~（1 << bitPos);
	}

	// 测试是0还是1
	bool test(size_t x)
	{
		size_t index = x / 32;
		size_t bitPos = x % 32;

		return (_bits[index] & (1 << bitPos)) != 0;
	}
private:
	vector<int> _bits;
};

位图的应用

1. 快速查找某个数据是否在一个集合中
2. 排序 + 去重
3. 求两个集合的交集、并集等
4. 操作系统中磁盘块标记

布隆过滤器

布隆过滤器提出

我们在使用新闻客户端时，推荐系统是如何过滤掉用户已经看过的内容？

1. 哈希表：记录所有历史记录，占用空间极大。
2. 位图：位图只能处理整形，如果是记录 URL 等字符串，无法处理。
3. 布隆过滤器：将哈希与位图结合。用多个哈希函数将一个数据映射到位图的多个位置。从而大幅降低内存，但付出了一点误判的代价。

布隆过滤器概念

它是由布隆（Burton Howard Bloom）在 1970 年提出的一种紧凑型的、比较巧妙的概率型数据结构。特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。

布隆过滤器的增删查

• 插入：使用 (K) 个不同的哈希函数，算出 (K) 个不同的位置，将这 (K) 个比特位置为 1。
  比如：向布隆过滤器中插入：“baidu”，这个插入过程布隆过滤器会调用3个哈希函数生成3个哈希值，为什么是3个，因为那个创造布隆过滤器的大佬通过数学的方式计算出来的，最优是3到4个。
  
  插入后：
  

• 查找：

  • 只要有一个比特位为 0，该元素就一定不存在；如果所有比特位都为 1，说明该元素可能存在（因为这些 1 可能是别的元素在哈希冲突时碰巧置上去的）。

• 删除（：

  • 传统布隆过滤器绝对不能直接物理删除（置 0）。因为多个元素可能共享同一个比特位。例如插入 A 和 B，它们都映射到了下标为 3 的位置。此时如果要删除 A，将下标 3 置 0，那么下次查找 B 的时候，就会因为下标 3 为 0 而判定 B 不存在，从而发生严重的误判。
  • ** Counting Bloom filter**：可以将每个 bit 位扩展为一个计数器（Counter），插入时 +1，删除时 -1。但这就失去了布隆过滤器原本极致的空间优势，且可能发生计数回绕。

详情请可以去参考该链接布隆过滤器详解

简单实现一下布隆过滤器：

struct BKDRHash {
    size_t operator()(const string& s) {
        size_t hash = 0;
        for (auto ch : s) hash = hash * 131 + ch;
        return hash;
    }
};
struct SDBMHash {
    size_t operator()(const string& s) {
        size_t hash = 0;
        for (auto ch : s) hash = hash * 65599 + ch;
        return hash;
    }
};
struct RSHash {
    size_t operator()(const string& s) {
        size_t hash = 0;
        size_t magic = 63689;
        for (auto ch : s) {
            hash = hash * magic + ch;
            magic *= 378551;
        }
        return hash;
    }
};

template<size_t N, class K = string,
    class Hash1 = BKDRHash, class Hash2 = SDBMHash, class Hash3 = RSHash>
class BloomFilter {
public:
    // 实际应用中，N * 5 左右的比特位数比较合理
    BloomFilter() : _bs(N * 5) {}

    // 插入：将 K 个哈希位置全部置 1
    void Set(const K& key) {
        size_t bitPos1 = Hash1()(key) % _bs.size();
        size_t bitPos2 = Hash2()(key) % _bs.size();
        size_t bitPos3 = Hash3()(key) % _bs.size();

        _bs.set(bitPos1);
        _bs.set(bitPos2);
        _bs.set(bitPos3);
    }

private:
    // 底层复用了位图
    bitset<N * 5> _bs;
};

布隆过滤器优缺点

优点：

1. 时间复杂度极低：增加和查询时间复杂度为 (O(K))（(K) 为哈希函数个数），与数据量大小无关。
2. 空间优势巨大：不需要存储元素本身，在能够承受一定误判时，比哈希表节省几十倍空间。
3. 保密性强：不存储元素本身，某些对保密要求严格的场合有优势。
4. 支持交集运算：使用同一组哈希函数的布隆过滤器可以进行交、并、差运算。

缺点：

1. 有误判率（假阳性）：不能准确判断元素是否在集合中。补救方法：再建一个白名单，存储可能被误判的数据。
2. 不能获取元素本身。
3. 一般情况下不能删除元素（除非使用计数法，但代价大）。
4. 如果采用计数方式删除，可能会存在计数回绕问题（比如计数器只有 3 bit，加到 7 再加就变成了 0）。

完