目录2.1底层结构哈希概念2.2 哈希冲突2.3 哈希函数2.4 哈希冲突解决2.4.1 闭散列2.4.2 开散列3. 模拟实现3.1 哈希表的改造4. 哈希的应用4.1 位图4.1.1 位图概念4.1.2 位图的实现4.1.3 位图的应用4.2 布隆过滤器4.2.1 布隆过滤器提出4.2.2 布隆过滤器概念布隆过滤器的插入4.2.3 布隆过滤器的查找4.2.4 布隆过滤器删除4.2.5 布隆过滤器优点4.2.6 布隆过滤器缺陷5. 海量数据面试题5.1 哈希切割5.2 位图应用5.3 布隆过滤器2.1底层结构unordered系列的关联式容器之所以效率比较高是因为其底层使用了哈希结构。哈希概念顺序结构以及平衡树中元素关键码与其存储位置之间没有对应的关系因此在查找一个元素 时必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)平衡树中为树的高度即 O(log N)搜索的效率取决于搜索过程中元素的比较次数。理想的搜索方法可以不经过任何比较一次直接从表中得到要搜索的元素。 如果构造一种存储结构通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立 一一映射的关系那么在查找时通过该函数可以很快找到该元素。当向该结构中插入元素 根据待插入元素的关键码以此函数计算出该元素的存储位置并按此位置进行存放搜索元素 对元素的关键码进行同样的计算把求得的函数值当做元素的存储位置在结构中按此位置 取元素比较若关键码相等则搜索成功该方式即为哈希(散列)方法哈希方法中使用的转换函数称为哈希(散列)函数构造出来的结构称 为哈希表(Hash Table)(或者称散列表)例如数据集合{176459} 哈希函数设置为hash(key) key % capacity; capacity为存储元素底层空间总的大小。用该方法进行搜索不必进行多次关键码的比较因此搜索的速度比较快问题按照上述哈希方式向集合中插入元素44会出现什么问题2.2 哈希冲突对于两个数据元素的关键字k_i和k_j(i ! j)有k_i! k_j但有Hash(k_i) Hash(k_j)即不同关键字通过相同哈希函数计算出相同的哈希地址该种现象称为哈希冲突或哈希碰撞把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”发生哈希冲突该如何处理呢2.3 哈希函数引起哈希冲突的一个原因可能是哈希函数设计不够合理哈希函数设计原则哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值域必须在0到m-1之间哈希函数计算出来的地址能均匀分布在整个空间中哈希函数应该比较简单常见哈希函数1、直接定址法--(常用)取关键字的某个线性函数为散列地址HashKey A*Key B优点简单、均匀缺点需要事先知道关键字的分布情况使用场景适合查找比较小且连续的情况面试题387. 字符串中的第一个唯一字符 - 力扣LeetCode2、除留余数法--(常用)设散列表中允许的地址数为m取一个不大于m但最接近或者等于m的质数p作为除数按照哈希函数Hash(key) key% p(pm),将关键码转换成哈希地址3、平方取中法--(了解)假设关键字为1234对它平方就是1522756抽取中间的3位227作为哈希地址再比如关键字为4321对它平方就是18671041抽取中间的3位671(或710)作为哈希地址平方取中法比较适合不知道关键字的分布而位数又不是很大的情况4、折叠法--(了解)折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)然后将这几部分叠加求和并按散列表表长取后几位作为散列地址折叠法适合事先不需要知道关键字的分布适合关键字位数比较多的情况5、随机数法--(了解)选择一个随机函数取关键字的随机函数值为它的哈希地址即H(key) random(key),其中random为随机数函数通常应用于关键字长度不等时采用此法6、数学分析法--(了解)设有n个d位数每一位可能有r种不同的符号这r种不同的符号在各位上出现的频率不一定相同可能在某些位上分布比较均匀每种符号出现的机会均等在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小选择其中各种符号分布均匀的若干位作为散列地址。例如假设要存储某家公司员工登记表如果用手机号作为关键字那么极有可能前7位都是相同的那么我们可以选择后面的四位作为散列地址如果这样的抽取工作还容易出现冲突还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成123446)等方法数字分析法通常适合处理关键字位数比较大的情况如果事先知道关键字的分布且关键字的若干位分布较均匀的情况注意哈希函数设计的越精妙产生哈希冲突的可能性就越低但是无法避免哈希冲突2.4 哈希冲突解决解决哈希冲突两种常见的方法是闭散列和开散列2.4.1 闭散列闭散列也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把key存放到冲突位置中的“下一个”空位置中去。那如何寻找下一个空位置呢1、线性探测比如2.1中的场景现在需要插入元素44先通过哈希函数计算哈希地址hashAddr为4因此44理论上应该插在该位置但是该位置已经放了值为4的元素即发生哈希冲突线性探测从发生冲突的位置开始依次向后探测直到寻找到下一个空位置为止插入通过哈希函数获取待插入元素在哈希表中的位置如果该位置中没有元素则直接插入新元素如果该位置中有元素发生哈希冲突使用线性探测找到下一个空位置插入新元素删除采用闭散列处理哈希冲突时不能随便物理删除哈希表中已有的元素若直接删除元素会影响其他元素的搜索。比如删除元素4如果直接删除掉44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素// 哈希表每个空间给个标记 // EMPTY此位置空EXIST此位置已经有元素DELETE元素已经删除 enum State{EMPTY, EXIST, DELETE};线性探测的实现// 注意假如实现的哈希表中元素唯一即key相同的元素不再进行插入 // 为了实现简单此哈希表中我们将比较直接与元素绑定在一起 templateclass K, class V class HashTable { struct Elem { pairK, V _val; State _state; }; public: HashTable(size_t capacity 3) : _ht(capacity), _size(0) { for(size_t i 0; i capacity; i) _ht[i]._state EMPTY; } bool Insert(const pairK, V val) { // 检测哈希表底层空间是否充足 // _CheckCapacity(); size_t hashAddr HashFunc(key); // size_t startAddr hashAddr; while(_ht[hashAddr]._state ! EMPTY) { if(_ht[hashAddr]._state EXIST _ht[hashAddr]._val.first key) return false; hashAddr; if(hashAddr _ht.capacity()) hashAddr 0; /* // 转一圈也没有找到注意动态哈希表该种情况可以不用考虑哈希表中元素个数到达一定的数量哈希冲突概率会增大需要扩容来降低哈希冲突因此哈希表中元素是不会存满的 if(hashAddr startAddr) return false; */ } // 插入元素 _ht[hashAddr]._state EXIST; _ht[hashAddr]._val val; _size; return true; } int Find(const K key) { size_t hashAddr HashFunc(key); while(_ht[hashAddr]._state ! EMPTY) { if(_ht[hashAddr]._state EXIST _ht[hashAddr]._val.first key) return hashAddr; hashAddr; } return hashAddr; } bool Erase(const K key) { int index Find(key); if(-1 ! index) { _ht[index]._state DELETE; _size; return true; } return false; } size_t Size()const; bool Empty() const; void Swap(HashTableK, V, HF ht); private: size_t HashFunc(const K key) { return key % _ht.capacity(); } private: vectorElem _ht; size_t _size; };思考哈希表什么情况下进行扩容如何扩容void CheckCapacity() { if(_size * 10 / _ht.capacity() 7) { HashTableK, V, HF newHt(GetNextPrime(ht.capacity)); for(size_t i 0; i _ht.capacity(); i) { if(_ht[i]._state EXIST) newHt.Insert(_ht[i]._val); } Swap(newHt); } }线性探测优点实现非常简单线性探测缺点一旦发生哈希冲突所有的冲突连在一起容易产生数据“堆积”即不同关键码占据了可利用的空位置使得寻找某关键码的位置需要许多次比较导致搜索效率降低。如何缓解呢2、二次探测线性探测的缺陷是产生冲突的数据堆积在一块这与其找下一个空位置有关系因为找空位置的方式就是挨着往后逐个去找因此二次探测为了避免该问题找下一个空位置的方法为H_i (H_0 i^2 )% m, 或者H_i (H_0 - i^2 )% m。其中i 1,2,3…H_0是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置m是表的大小对于2.1中如果要插入44产生冲突使用解决后的情况为研究表明当表的长度为质数且表装载因子a不超过0.5时新的表项一定能够插入而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置就不会存在表满的问题。在搜索时可以不考虑表装满的情况但在插入时必须确保表的装载因子a不超过0.5如果超出必须考虑增容因此比散列最大的缺陷就是空间利用率比较低这也是哈希的缺陷2.4.2 开散列开散列概念开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中从上图可以看出开散列中每个桶中放的都是发生哈希冲突的元素2、开散列实现templateclass V struct HashBucketNode { HashBucketNode(const V data) : _pNext(nullptr), _data(data) {} HashBucketNodeV* _pNext; V _data; }; // 本文所实现的哈希桶中key是唯一的 templateclass V class HashBucket { typedef HashBucketNodeV Node; typedef Node* PNode; public: HashBucket(size_t capacity 3) : _size(0) { _ht.resize(GetNextPrime(capacity), nullptr); } // 哈希桶中的元素不能重复 PNode* Insert(const V data) { // 确认是否需要扩容。。。 // _CheckCapacity(); // 1. 计算元素所在的桶号 size_t bucketNo HashFunc(data); // 2. 检测该元素是否在桶中 PNode pCur _ht[bucketNo]; while(pCur) { if(pCur-_data data) return pCur; pCur pCur-_pNext; } // 3. 插入新元素 pCur new Node(data); pCur-_pNext _ht[bucketNo]; _ht[bucketNo] pCur; _size; return pCur; } // 删除哈希桶中为data的元素(data不会重复)返回删除元素的下一个节点 PNode* Erase(const V data) { size_t bucketNo HashFunc(data); PNode pCur _ht[bucketNo]; PNode pPrev nullptr, pRet nullptr; while(pCur) { if(pCur-_data data) { if(pCur _ht[bucketNo]) _ht[bucketNo] pCur-_pNext; else pPrev-_pNext pCur-_pNext; pRet pCur-_pNext; delete pCur; _size--; return pRet; } } return nullptr; } PNode* Find(const V data); size_t Size()const; bool Empty()const; void Clear(); bool BucketCount()const; void Swap(HashBucketV, HF ht; ~HashBucket(); private: size_t HashFunc(const V data) { return data%_ht.capacity(); } private: vectorPNode* _ht; size_t _size; // 哈希表中有效元素的个数 }3、开散列增容桶的个数是一定的随着元素的不断插入每个桶中元素的个数不断增多极端情况下可能会导致一个桶中链表节点非常多会影响的哈希表的性能因此在一定条件下需要对哈希表进行增容那该条件怎么确认呢开散列最好的情况是每个哈希桶中刚好挂一个节点再继续插入元素时每一次都会发生哈希冲突因此在元素个数刚好等于桶的个数时可以给哈希表增容void _CheckCapacity() { size_t bucketCount BucketCount(); if(_size bucketCount) { HashBucketV, HF newHt(bucketCount); for(size_t bucketIdx 0; bucketIdx bucketCount; bucketIdx) { PNode pCur _ht[bucketIdx]; while(pCur) { // 将该节点从原哈希表中拆出来 _ht[bucketIdx] pCur-_pNext; // 将该节点插入到新哈希表中 size_t bucketNo newHt.HashFunc(pCur-_data); pCur-_pNext newHt._ht[bucketNo]; newHt._ht[bucketNo] pCur; pCur _ht[bucketIdx]; } } newHt._size _size; this-Swap(newHt); } }4、开散列的思考只能存储key为整形的元素其他类型怎么解决// 哈希函数采用处理余数法被模的key必须要为整形才可以处理此处提供将key转化为整形的方法 // 整形数据不需要转化 templateclass T class DefHashF { public: size_t operator()(const T val) { return val; } };// key为字符串类型需要将其转化为整形 class Str2Int { public: size_t operator()(const string s) { const char* str s.c_str(); unsigned int seed 131; // 31 131 1313 13131 131313 unsigned int hash 0; while (*str) { hash hash * seed (*str); } return (hash 0x7FFFFFFF); } };// 为了实现简单此哈希表中我们将比较直接与元素绑定在一起 templateclass V, class HF class HashBucket { // ... private: size_t HashFunc(const V data) { return HF()(data.first)%_ht.capacity(); } };2、除留余数法最好模一个素数如何每次快速取一个类似两倍关系的素数size_t GetNextPrime(size_t prime) { const int PRIMECOUNT 28; static const size_t primeList[PRIMECOUNT] { 53ul, 97ul, 193ul, 389ul, 769ul, 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, 1610612741ul, 3221225473ul, 4294967291ul }; size_t i 0; for (; i PRIMECOUNT; i) { if (primeList[i] prime) return primeList[i]; } return primeList[i]; }各种字符串Hash函数 - clq - 博客园5、开散列与闭散列比较应用链地址法处理溢出需要增设链接指针似乎增加了存储开销。事实上由于开地址法必须保持大量的空闲空间以确保搜索效率如二次探查法要求装载因子a 0.7而表项所占空间又比指针大的多所以使用链地址法反而比开地址法节省存储空间3. 模拟实现3.1 哈希表的改造模板参数列表的改造// K:关键码类型 // V: 不同容器V的类型不同如果是unordered_mapV代表一个键值对如果是unordered_set,V 为 K // KeyOfValue: 因为V的类型不同通过value取key的方式就不同详细见unordered_map/set的实现 // HF: 哈希函数仿函数对象类型哈希函数使用除留余数法需要将Key转换为整形数字才能取模 templateclass K, class V, class KeyOfValue, class HF DefHashFT class HashBucket;2、增加迭代器操作// 为了实现简单在哈希桶的迭代器类中需要用到hashBucket本身 templateclass K, class V, class KeyOfValue, class HF class HashBucket; // 注意因为哈希桶在底层是单链表结构所以哈希桶的迭代器不需要--操作 template class K, class V, class KeyOfValue, class HF struct HBIterator { typedef HashBucketK, V, KeyOfValue, HF HashBucket; typedef HashBucketNodeV* PNode; typedef HBIteratorK, V, KeyOfValue, HF Self; HBIterator(PNode pNode nullptr, HashBucket* pHt nullptr); Self operator() { // 当前迭代器所指节点后还有节点时直接取其下一个节点 if (_pNode-_pNext) _pNode _pNode-_pNext; else { // 找下一个不空的桶返回该桶中第一个节点 size_t bucketNo _pHt-HashFunc(KeyOfValue()(_pNode-_data))1; for (; bucketNo _pHt-BucketCount(); bucketNo) { if (_pNode _pHt-_ht[bucketNo]) break; } } return *this; } Self operator(int); V operator*(); V* operator-(); bool operator(const Self it) const; bool operator!(const Self it) const; PNode _pNode; // 当前迭代器关联的节点 HashBucket* _pHt; // 哈希桶--主要是为了找下一个空桶时候方便 };3、增加通过key获取value操作templateclass K, class V, class KeyOfValue, class HF DefHashFT class HashBucket { friend HBIteratorK, V, KeyOfValue, HF; // ... public: typedef HBIteratorK, V, KeyOfValue, HF Iterator; ////////////////////////////////////////////////////////// // ... // 迭代器 Iterator Begin() { size_t bucketNo 0; for (; bucketNo _ht.capacity(); bucketNo) { if (_ht[bucketNo]) break; } if (bucketNo _ht.capacity()) return Iterator(_ht[bucketNo], this); else return Iterator(nullptr, this); } Iterator End(){ return Iterator(nullptr, this);} Iterator Find(const K key); Iterator Insert(const V data); Iterator Erase(const K key); // 为key的元素在桶中的个数 size_t Count(const K key) { if(Find(key) ! End()) return 1; return 0; } size_t BucketCount()const{ return _ht.capacity();} size_t BucketSize(size_t bucketNo) { size_t count 0; PNode pCur _ht[bucketNo]; while(pCur) { count; pCur pCur-_pNext; } return count; } // ... };3.2 unordered_map// unordered_map中存储的是pairK, V的键值对K为key的类型V为value的类型HF哈希函数类型 // unordered_map在实现时只需将hashbucket中的接口重新封装即可 templateclass K, class V, class HF DefHashFK class unordered_map { typedef pairK, V ValueType; typedef HashBucketK, ValueType, KeyOfValue, HF HT; // 通过key获取value的操作 struct KeyOfValue { const K operator()(const ValueType data) { return data.first;} }; public: typename typedef HT::Iterator iterator; public: unordered_map(): _ht() {} //////////////////////////////////////////////////// iterator begin(){ return _ht.Begin();} iterator end(){ return _ht.End();} //////////////////////////////////////////////////////////// // capacity size_t size()const{ return _ht.Size();} bool empty()const{return _ht.Empty();} /////////////////////////////////////////////////////////// // Acess V operator[](const K key) { return (*(_ht.InsertUnique(ValueType(key, V())).first)).second; } const V operator[](const K key)const; ////////////////////////////////////////////////////////// // lookup iterator find(const K key){ return _ht.Find(key);} size_t count(const K key){ return _ht.Count(key);} ///////////////////////////////////////////////// // modify pairiterator, bool insert(const ValueType valye) { return _ht.Insert(valye);} iterator erase(iterator position) { return _ht.Erase(position);} //////////////////////////////////////////////////////////// // bucket size_t bucket_count(){ return _ht.BucketCount();} size_t bucket_size(const K key){ return _ht.BucketSize(key);} private: HT _ht; };4. 哈希的应用4.1 位图4.1.1 位图概念面试题给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在这40亿个数中。【腾讯】遍历时间复杂度O(N)排序(O(NlogN))利用二分查找: logN位图解决数据是否在给定的整形数据中结果是在或者不在刚好是两种状态那么可以使用一个二进制比特位来代表数据是否存在的信息如果二进制比特位为1代表存在为0代表不存在。比如2、位图概念所谓位图就是用每一位来存放某种状态适用于海量数据数据无重复的场景。通常是用来判断某个数据存不存在的4.1.2 位图的实现class bitset { public: bitset(size_t bitCount) : _bit((bitCount 5) 1), _bitCount(bitCount) { // 这里每个int负责32个比特位 // 所以总比特数需要换算成整型个数 } // 将which比特位置1 void set(size_t which) { // 越界直接返回 if (which _bitCount) return; // 找到which所在的整型下标 size_t index (which 5); // 找到which在该整型中的比特位位置 size_t pos which % 32; // 把对应比特位置1 _bit[index] | (1 pos); } // 将which比特位置0 void reset(size_t which) { // 越界直接返回 if (which _bitCount) return; // 找到which所在的整型下标 size_t index (which 5); // 找到which在该整型中的比特位位置 size_t pos which % 32; // 把对应比特位清零 _bit[index] ~(1 pos); } // 检测位图中which是否为1 bool test(size_t which) { // 越界直接返回false if (which _bitCount) return false; // 找到which所在的整型下标 size_t index (which 5); // 找到which在该整型中的比特位位置 size_t pos which % 32; // 判断对应位是不是1 return _bit[index] (1 pos); } // 获取位图中比特位的总个数 size_t size() const { return _bitCount; } // 位图中比特为1的个数 size_t Count() const { // 预处理每个字节里1的个数 int bitCntTable[256] { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 }; size_t size _bit.size(); size_t count 0; for (size_t i 0; i size; i) { int value _bit[i]; int j 0; // 这里按字节统计一个int中1的个数 while (j sizeof(_bit[0])) { unsigned char c value; count bitCntTable[c]; j; value 8; } } return count; } private: std::vectorint _bit; size_t _bitCount; };4.1.3 位图的应用1. 快速查找某个数据是否在一个集合中2. 排序 去重3. 求两个集合的交集、并集等4. 操作系统中磁盘块标记4.2 布隆过滤器4.2.1 布隆过滤器提出我们在使用新闻客户端看新闻时它会给我们不停地推荐新的内容它每次推荐时要去重去掉那些已经看过的内容。问题来了新闻客户端推荐系统如何实现推送去重的用服务器记录了用户看过的所有历史记录当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选过滤掉那些已经存在的记录。如何快速查找呢用哈希表存储用户记录缺点浪费空间用位图存储用户记录缺点位图一般只能处理整形如果内容编号是字符串就无法处理了将哈希与位图结合即布隆过滤器4.2.2 布隆过滤器概念布隆过滤器是由布隆Burton Howard Bloom在1970年提出的一种紧凑型的、比较巧妙的概率型数据结构特点是高效地插入和查询可以用来告诉你“某样东西一定不存在或者可能存在”它是用多个哈希函数将一个数据映射到位图结构中。此种方式不仅可以提升查询效率也可以节省大量的内存空间https://zhuanlan.zhihu.com/p/43263751/布隆过滤器的插入向布隆过滤器中插入baidustruct BKDRHash { size_t operator()(const std::string s) { // BKDR 哈希算法 // 从前往后扫描字符串把前面的计算结果乘以一个种子再加上当前字符 size_t value 0; for (auto ch : s) { value * 31; value ch; } // 返回最终哈希值 return value; } }; struct APHash { size_t operator()(const std::string s) { // APHash 算法 // 偶数位置和奇数位置字符采用不同的扰动方式 size_t hash 0; for (long i 0; i s.size(); i) { // 偶数下标字符的处理方式 if ((i 1) 0) { hash ^ ((hash 7) ^ s[i] ^ (hash 3)); } // 奇数下标字符的处理方式 else { hash ^ (~((hash 11) ^ s[i] ^ (hash 5))); } } // 返回最终哈希值 return hash; } }; struct DJBHash { size_t operator()(const std::string s) { // DJB 哈希算法 // 初值通常给 5381然后不断乘以 33 再加当前字符 size_t hash 5381; for (auto ch : s) { hash (hash 5) ch; } // 返回最终哈希值 return hash; } }; templatesize_t N, size_t X 5, class K std::string, class HashFunc1 BKDRHash, class HashFunc2 APHash, class HashFunc3 DJBHash class BloomFilter { public: void Set(const K key) { // 位图总长度 // N 表示数据规模X 表示放大倍数 size_t len X * N; // 分别用三个哈希函数计算同一个 key 的三个映射位置 size_t index1 HashFunc1()(key) % len; size_t index2 HashFunc2()(key) % len; size_t index3 HashFunc3()(key) % len; // 把三个位置都置为 1 // 表示这个 key 已经映射到了这些比特位上 _bs.set(index1); _bs.set(index2); _bs.set(index3); } bool Test(const K key) { // 位图总长度 size_t len X * N; // 先检查第一个哈希位置 // 只要有一个位置为 0就说明该元素一定不存在 size_t index1 HashFunc1()(key) % len; if (_bs.test(index1) false) return false; // 再检查第二个哈希位置 size_t index2 HashFunc2()(key) % len; if (_bs.test(index2) false) return false; // 再检查第三个哈希位置 size_t index3 HashFunc3()(key) % len; if (_bs.test(index3) false) return false; // 走到这里说明三个位置都为 1 // 只能说明该元素可能存在不能保证一定存在 // 因为可能与其他元素的哈希结果发生重叠产生误判 return true; } // 不支持直接删除 // 因为多个元素的哈希位置可能重叠 // 如果直接清零可能把其他元素对应的位也一起破坏掉 void Reset(const K key); private: // 底层使用位图保存多个哈希函数映射后的结果 bitsetX * N _bs; };4.2.3 布隆过滤器的查找布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找分别计算每个哈希值对应的比特位置存储的是否为零只要有一个为零代表该元素一定不在哈希表中否则可能在哈希表中注意布隆过滤器如果说某个元素不存在时该元素一定不存在如果该元素存在时该元素可能存在因为有些哈希函数存在一定的误判比如在布隆过滤器中查找alibaba时假设3个哈希函数计算的哈希值为1、3、7刚好和其他元素的比特位重叠此时布隆过滤器告诉该元素存在但实该元素是不存在的4.2.4 布隆过滤器删除布隆过滤器不能直接支持删除工作因为在删除一个元素时可能会影响其他元素比如删除上图中tencent元素如果直接将该元素所对应的二进制比特位置0“baidu”元素也被删除了因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠一种支持删除的方法将布隆过滤器中的每个比特位扩展成一个小的计数器插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一删除元素时给k个计数器减一通过多占用几倍存储空间的代价来增加删除操作缺陷无法确认元素是否真正在布隆过滤器中存在计数回绕4.2.5 布隆过滤器优点增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数一般比较小)与数据量大小无关哈希函数相互之间没有关系方便硬件并行运算布隆过滤器不需要存储元素本身在某些对保密要求比较严格的场合有很大优势在能够承受一定的误判时布隆过滤器比其他数据结构有这很大的空间优势数据量很大时布隆过滤器可以表示全集其他数据结构不能使用同一组散列函数的布隆过滤器可以进行交、并、差运算4.2.6 布隆过滤器缺陷有误判率即存在假阳性(False Position)即不能准确判断元素是否在集合中(补救方法再建立一个白名单存储可能会误判的数据)不能获取元素本身一般情况下不能从布隆过滤器中删除元素如果采用计数方式删除可能会存在计数回绕问题5. 海量数据面试题5.1 哈希切割给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址与上题条件相同如何找到top K的IP如何直接用Linux系统命令实现5.2 位图应用给定100亿个整数设计算法找到只出现一次的整数给两个文件分别有100亿个整数我们只有1G内存如何找到两个文件交集位图应用变形1个文件有100亿个int1G内存设计算法找到出现次数不超过2次的所有整数5.3 布隆过滤器给两个文件分别有100亿个query我们只有1G内存如何找到两个文件交集分别给出精确算法和近似算法如何扩展BloomFilter使得它支持删除元素的操作
