哈希的应用

哈希思想在算法中的应用繁多其重要性是不言而喻的，这里简单介绍两种哈希在大数据中的应用。

位图

算法思路

假如说有这么一种情景：给40亿个不重复的无符号整数，没排过序，判断一个无符号整数是否在这40亿个数中。
首先我们从时间考虑，假如说我们遍历40亿个数，事件复杂度是On的，如果我们先排序再用二分查找，排序要ONlogN二分查找要OlogN也还是不够快。不过这道题最重要的不是它的时间，而是空间，如果我们把40亿个整形全放到内存中需要4G * 4 = 16G内存，40亿字节 == 4G，不难发现我们根本存不下，那么怎么办呢？这里就需要用到位图。
我们标记一个数是否存在根本不需要存储完整整数，我们只需要用存在或者不存在两种状态对其进行标记即可，而两种状态的标记，只需要1位数据即可，由此我们可以用40亿比特位来标记40亿个数是否存在。并且无符号整形的上限差不多也就在42亿，我们就算标记完全部数字用到40亿位也只需要4 G / 8 = 500M内存，由此我们使用位图进行标记差不多相当于将空间压缩了32倍。
标记思路就是40多亿位分表标识40多亿无符号整型，一个数如果存在则它对应位标记为1，否则为0。假如说0存在，则第0位标记为1，32不存在则第32位标记为0，而无符号整形也是有上限的，40多亿位完全可以标记所有无符合整形。

实现

#include <iostream>
#include <vector>
class BitSet
{
public:
    //要保证每一个数据都能映射到一个唯一的位置，位图的大小与最大映射数据上限有关
    //因此这里的range代表的是映射的最大数据
    BitSet(size_t range)
    {
        _bs.resize((range >> 5) + 1);
    }
    //存储
    void Set(int num)
    {
        int index = num >> 5;
        int bitIdx = num % 32;
        _bs[index] |= (1 << bitIdx);
    }
    bool Find(int num)
    {
        int index = num >> 5;
        int bitIdx = num % 32;
        return 1 & (_bs[index] >> bitIdx);
    }
    void ReSet(int num)
    {
        int index = num >> 5;
        int bitIdx = num % 32;
        _bs[index] &= (~(1 << bitIdx));
    }
private:
    std::vector<int> _bs;
};
int main()
{
    BitSet bs(64);
    bs.Set(1);
    bs.Set(64);
    bs.Set(4);
    std::cout << bs.Find(1) << std::endl;
    std::cout << bs.Find(64) << std::endl;
    std::cout << bs.Find(4) << std::endl;
    std::cout << bs.Find(3) << std::endl;
    bs.ReSet(4);
    std::cout << bs.Find(4) << std::endl;
}


1
1
1
0
0

但是使用位图有一个缺陷，就是我们无法解决哈希冲突，如果我们想要判断字符串，当字符串转换为整数时就有可能会造成哈希冲突，因为算法的原因两个不同的字符串可能会最终会转换为相同的整数，所以在判断字符串等其他需要转换并且可能会造成哈希冲突的类型时不能直接使用位图，于是一种进化版的位图诞生了。

布隆过滤器

思想

布隆过滤器是专门为了解决为途中转换会造成哈希冲突的情况。例如我们现在要用位图标记字符串，我们两个不相同的字符串经过哈希函数转换后可能会出现最终一样的转换结果于是便出现了哈希冲突，例如str1哈希转换后为24于是我们将第24位置1表示str1存在，但是此时我们在判断str2是否存在的时候发现str2哈希后的值也为24，但是str2并不存在，于是这里就出现了哈希冲突，进行了误判。
为了解决它，布隆过滤器会选择利用多个不同的哈希函数对一个字符串进行哈希，并将所有哈希结果的对应位全部置1，这里与位图的思想无异。当我们查找一个字符串是否存在时再用同样的多个哈希函数对其进行哈希，然后依次查找每一位哈希结果，如果全为1则可大几率认定为这个字符串是存在的。例如str1存储利用三个哈希函数得到结果为24, 26, 28，于是我们将这3位置，我们在查找str2时利用同样三个哈希函数转换得到结果24, 25, 27，虽然24造成了冲突，但是由于25, 26并不为1，所以也并不会误判str2存在，只有str1三次哈希后结果在位图中全都为1时才会判断其存在，这样可以大概率解决冲突。
为什么说是大几率存在的呢？因为也有可能这个字符串的所有哈希结果都与其他字符串造成冲突，此时也会有误判，不过这种情况的几率很小，布隆过滤器可以保证绝大多数情况是正确的，但偶尔也难免会有特殊情况发生。

#include <iostream>
#include <vector>
#include <string>
#include "BitSet.hpp"
struct HFun1
{
    size_t operator()(const std::string& str)
    {
        size_t hash = 0;
        for(auto& ch : str)
        {
            hash = hash * 131 + ch;
        }
        return hash;
    }
};
struct HFun2
{
    size_t operator()(const std::string& str)
    {
        size_t hash = 0;
        for(auto& ch : str)
        {
            hash = hash * 65599 + ch;
        }
        return hash;
    }
};
struct HFun3
{
    size_t operator()(const std::string& str)
    {
        size_t hash = 0;
        size_t magic = 63689;
        for(auto& ch : str)
        {
            hash = hash * magic + ch;
            magic *= 378551;
        }
        return hash;
    }
};
//HFun为3个自定义的哈希函数
template<class T, class HFun1, class HFun2, class HFun3>
class BloomFilter
{
public:
    //k = (m / n) * ln2
    //k:哈希函数数量
    //m:位图大小
    //n:元素个数
    //m = k * n / ln2
    //number表示元素个数，布隆这里不用元素最大上限作为位图的大小，因为可能会造成大量数据浪费
    //这里利用二次哈希，节省空间
    BloomFilter(size_t number)
        :_bitCount(5 * number)
        ,_bs(_bitCount)
    {
    }
    void Set(const T& data)
    {
        int index1 = HFun1()(data) % _bitCount;
        int index2 = HFun2()(data) % _bitCount;
        int index3 = HFun3()(data) % _bitCount;
        _bs.Set(index1);
        _bs.Set(index2);
        _bs.Set(index3);
    }
    bool Find(const T& data)
    {
        int index1 = HFun1()(data) % _bitCount;
        int index2 = HFun2()(data) % _bitCount;
        int index3 = HFun3()(data) % _bitCount;
        if(!_bs.Find(index1) || !_bs.Find(index2) || !_bs.Find(index3))
        {
            return false;
        }
        return true;//可能会有误判
    }
    //布隆为了防止误判不提供删除操作

private:
    BitSet _bs;
    size_t _bitCount;
};
int main()
{
    BloomFilter<std::string, HFun1, HFun2, HFun3> bf(1000);
    std::string str1 = "https://misakifx.github.io/";
    std::string str2 = "https://blog.csdn.net/qq_41669298";
    std::string str3 = "https://space.bilibili.com/14406161/#/fans/follow";
    std::string str4 = "https://space.bilibili.com/#/fans/follow";
    std::string str5 = "https://space.bilibili.com/4406161/#/fans/follow";
    std::string str6 = "https://space.bilibili.com/146161/#/fans/follow";
    bf.Set(str1);
    bf.Set(str2);
    bf.Set(str3);
    bool ret = bf.Find(str1);
    std::cout << ret << std::endl;
    ret = bf.Find(str2);
    std::cout << ret << std::endl;
    ret = bf.Find(str3);
    std::cout << ret << std::endl;
    ret = bf.Find(str4);
    std::cout << ret << std::endl;
    ret = bf.Find(str5);
    std::cout << ret << std::endl;
    ret = bf.Find(str6);
    std::cout << ret << std::endl;
}



1
1
1
0
0
0