其他哈希函数
- 平方取中法
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；
再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址。
平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况。 - 折叠法
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况。 - 随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。
通常应用于关键字长度不等时采用此法。 - 数学分析法
设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定
相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只
有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散
列地址。
例如：
假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是 相同
的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现 冲突，还
可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移
位、前两数与后两数叠加(如1234改成12+34=46)等方法。
数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的
若干位分布较均匀的情况。
注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突。
哈希的应用
哈希切割（面试题）
给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？
IP可以视为一个字符串，无法直接转成整形。
这道题可以将这100G的文件切割成1G的文件（100份）。
将100G文件中的IP通过哈希切割（哈希表与桶上面将string转成int类型的仿函数）转成整形，遍历一遍然后挨个%100放进这100份的文件中。
然后用map统计次数，统计完一个小文件释放掉这个map，在新创建一个map用来统计下一个，最后找到IP最多的。
那么如果一个小文件大小超过1G呢？这会有两种情况：
1.这个小文件不同IP很多，大多数都是不重复的，map统计不下。
2.这个小文件相同IP很多，大多数都是重读的，map可以统计下。
此时只要解决了第一种情况即可：
换个哈希切割的函数（方法），一定要换方法，不然切割出来的内容还是相同的，然后在从头开始进行上面的方法，分成100份，再用map统计即可。
区分这两种方式是，直接用map统计，如果是第一种情况map就会插入结点失败，抛异常。
第二种不会有任何的错误，会统计完，不会报错。
位图
所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用
来判断某个数据存不存在的。（也是一种哈希的思想）
例如：用23个比特位就能判断这组数据是否存在。
位图应用（面试题）
1. 给40亿个不重复的无符号整数，没排序过，给一个无符号整数，如何快速判断一个数是否在这40亿个数。【腾讯】
40亿个整数大概是16G的大小，我们电脑台式机一般都是32G，笔记本一般是16G，这些数据要是放进内存肯定是不行的。
所以这里就适合用位图去搞。
一个无符号整形数据的范围是：
这里就放2^23-1个比特位的位图，大小算起来就是512MB的大小。
然后，因为一个字节是8个比特位，那么在开辟空间的时候就是按照字节开辟，存储比特位也通过字节位移的方式存储。
那么对应值如何映射到位图中呢？首先确定是在哪一个字节，也就是要/8，然后确定是该字节中的哪个比特位当中%8。
#include<iostream> #include<vector> using namespace std; namespace baiye { template<size_t N> class bit_set { public: bit_set() { _arr.resize(N / 8 + 1, 0);//这里是开辟多少个字节，+1是为了多余的比特位能有容身之所 } void set(size_t x)//标记比特位 { size_t i = x / 8; size_t j = x % 8; _arr[i] |= (1 << j); } void reset(size_t x)//清除比特位 { size_t i = x / 8; size_t j = x % 8; _arr[i] &= (~(1 << j)); } bool test(size_t x)//查找这个数是否存在 { size_t i = x / 8; size_t j = x % 8; return _arr[i] &= (1 << j);//0就是不存在，非0就是存在 } private: vector<char> _arr; }; } void test() { baiye::bit_set<100> arr; arr.set(10); arr.set(20); arr.set(30); cout << arr.test(30) << endl; cout << arr.test(20) << endl; cout << arr.test(10) << endl; arr.reset(30); cout << arr.test(30) << endl; } int main() { test(); return 0; }
库里一个写好的位图：https://legacy.cplusplus.com/reference/bitset/bitset/?kw=bitset
2. 给定100亿个整数，设计算法找到只出现一次的整数？
这道题使用位图表示数据的状态，其实可以用两个比特位就能表示：
0次 00
1次 01
1次以上 11
我们可以开辟两个大小相同的位图结构：
一个位图对应另一个位图的相同位置成为一组。
#include<iostream> #include<vector> #include<bitset> using namespace std; namespace baiye { template<size_t N> class bit_set { public: void set(size_t x) { if (arr1.test(x) == 0) arr1.set(x); else arr2.set(x); } void Printf() { for (size_t i = 0; i < arr1.size(); i++) { if (arr1[i] && !arr2[i]) { cout << i << ' '; } } cout << endl; } private: bitset<N> arr1; bitset<N> arr2; }; } void test() { baiye::bit_set<100> arr; int a[] = { 10,25,25,66,66,66,78,49,32, }; for (auto& e : a) { arr.set(e); } arr.Printf(); }
3. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
这道题和上一道题区别不大，开两个位图，遍历两个位图，如果都为1就是交集。
4. 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整
数。
可以在第二题的基础上改动，：
0次 00
1次 01
2次 10
2次以上 11
布隆过滤器
给一组英文单词，想看这几个单词是否存在，我们可以用位图，但是冲突是不可避免的，完全不相同的单词通过HashFunc函数可能就转成了同一个整形，映射到了同一个位置，如果某个单词其实不存在，但是他映射的位置是1，那么这里就有了误判。
那么有什么办法能降低误判率呢？我们可以让每个单词同时映射2个位置。
C单词看两个位置如果都为1，就是存在，D单词也是，如果D单词不存在，C单词存在，D单词红线映射的部分就是0，黑线还是1，这样两个单词就不冲突了。（降低了误判率）
布隆过滤器的改进：映射多个位置，降低误判率。
多少个哈希函数（映射关系）与误判率的概率：
原文章地址：https://zhuanlan.zhihu.com/p/43263751/
m = k*n/0.7
假设k = 3 ，m = 4.2n，也就是说存一个值要开4个位出来。
代码实现
#include<iostream> #include<string> #include<bitset> using namespace std; struct Func1 { size_t operator()(const string str) { size_t hash = 0; for (auto& ch : str) { hash = hash * 131 + ch; } return hash; } }; struct Func2 { size_t operator()(const string str) { unsigned int hash = 0; int i = 0; for (auto& ch : str) { if ((i & 1) == 0) { hash ^= ((hash << 7) ^ ch ^ (hash >> 3)); } else { hash ^= (~((hash << 11) ^ ch ^ (hash >> 5))); } i++; } return hash; } }; struct Func3 { size_t operator()(const string str) { size_t hash = 5381; for (auto& ch : str) { hash += (hash << 5) + ch; } return hash; } }; template<size_t N,//假设N是最多储存数据的个数 class HashFunc1 = Func1,//映射几个位置就给几个哈希函数 class HashFunc2 = Func2, class HashFunc3 = Func3, class K = string>//因为大部分都是string类型，给个缺省值 class BloomFilter { public: void set(const K& key)//存数据 { arr.set(HashFunc1()(key) % (5 * N));//将key分别映射到三个位置 arr.set(HashFunc2()(key) % (5 * N)); arr.set(HashFunc3()(key) % (5 * N)); } bool test(const K& key) { size_t hashi1 = HashFunc1()(key) % (5 * N); size_t hashi2 = HashFunc2()(key) % (5 * N); size_t hashi3 = HashFunc3()(key) % (5 * N); if (!arr.test(hashi1)) return false; if (!arr.test(hashi2)) return false; if (!arr.test(hashi3)) return false; return true; } private: bitset<N * 5> arr;//原本是4.2，这里多扩大一点 }; int main() { BloomFilter<10> arr; string str[] = { "666", "ckx","小黑子","鸡哥","树枝","蒸虾头","蒸乌鱼","香翅捞饭" }; for (auto& e : str) { arr.set(e); } for (auto& e : str) { cout << arr.test(e) << " "; } cout << endl; string str1[] = { "1白龙马", "白1龙马","白龙1马","白龙马1","1白1龙1马1","白1龙1马","1白龙1马","白1龙马1" }; for (auto& e : str1) { arr.set(e); } for (auto& e : str1) { cout << arr.test(e) << " "; } return 0; }
第二组测试用例是近似的，但是也区分开来了，说明冲突的概率确实不大。（但是无法避免，只能缩小概率）
布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。
布隆过滤器的优缺点
优点
- 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无
关。 - 哈希函数相互之间没有关系，方便硬件并行运算。
- 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势。
- 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势。
- 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能。
- 使用同一组散列函数的布隆过滤器可以进行交、并、差运算。
缺陷
- 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中。(补救方法：再
建立一个白名单，存储可能会误判的数据) - 不能获取元素本身。
- 一般情况下不能从布隆过滤器中删除元素。
- 如果采用计数方式删除，可能会存在计数回绕问题。
布隆过滤器应用（面试题）
1. 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法。
精准算法：
query一般是查询指令，比如是一个网络请求，一个数据库sql语句等等。
假设每个query每个是50字节，那么100亿个就是500G。
想要精准计算，就要用到上面讲100G的文件分成100个文件的方法。
这里两个大文件各分成1000份小文件：HashFunc(query)%1000
然后通过一个两个小文件组成一对，找出他们的交集即可。
这里如果某个小文件超过规定的大小，那么就从头开始继续分，像之前的哈希切割一样。
近似算法：
用一个布隆过滤器，两个数据中是交集的一定会映射到一起去，但是也会有不是的映射到一起去。
2. 如何扩展BloomFilter使得它支持删除元素的操作。
可以在每个位图上面加一个计数的，每有一个映射在这个位置上就++，少一个映射就- - 。
