目录

1.什么是哈希？

2.哈希冲突

3.哈希冲突解决方法

①闭散列

1.原理说明

2.代码实现

3.优缺点分析

4.二次探测

②开散列

1.原理说明

2.代码实现

③闭散列与开散列的比较

4.哈希的应用

①位图

②布隆过滤器

1.布隆过滤器概念

2.布隆过滤器的模拟实现

3.布隆过滤器的优缺点

③海量数据处理

1.哈希切割

2.位图应用

3.布隆过滤器

---

1.什么是哈希？

在顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(logN)，搜索的效率取决于搜索过程中元素的比较次数。
那么我们理想的搜索方法是：可以不经过任何比较，一次直接从表中得到要搜索的元素。
如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

当向该结构中：

1. 插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
2. 搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

这种方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表) 

举个例子

2.哈希冲突

虽然上面的方法确实很快，但是当新插入的元素为44时就会出现一个问题：新的数据放哪？

对于两个数据元素的关键字Ki和Kj(i != j)，有Ki != Kj，但有：Hash(Ki) == Hash(Kj)，即：不同关键字通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
我们把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

3.哈希冲突解决方法

那既然有了哈希冲突，我们如何来解决它呢？

一般来说，解决哈希冲突的方法有两种，分别是闭散列与开散列

①闭散列

闭散列也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置呢？

这里我们以上面的图片为例，这里有两种寻找方法
第一种是线性探测，即从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

1.原理说明

现在需要插入元素44，先通过哈希函数计算哈希地址为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。

2.代码实现

// 与开散列作区别（闭散列又叫开放寻址法）
namespace open_address
{// 在这里使用枚举来给哈希表每个空间标记enum State{EMPTY, // EMPTY此位置空,EXIST, // EXIST此位置已经有元素DELETE // DELETE元素已经删除};template<class K, class V>struct HashData{pair<K, V> _kv;State _state = EMPTY;};template<class K>struct DefaultHashFunc{size_t operator()(const K& key){return (size_t)key;}};// 这里可以使用偏特化对string的hashi进行处理template<>// BKDRHashFuncstruct DefaultHashFunc<string>{size_t operator()(const string& str){size_t hash = 0;for (auto ch : str){hash *= 131;hash += ch;}return hash;}};// 这里的HashFunc是当传入的K不为数字类型时，将其转换为对应的数字template<class K, class V, class HashFunc = DefaultHashFunc<K>>class HashTable{public:HashTable(){_table.resize(10);}bool Insert(const pair<K, V>& kv){HashFunc hf;// 当空间占有率大小>0.7时就扩容if (_n*10 / _table.size() >= 7){size_t newsize = _table.size() * 2;// 在扩容之后需要将哈希表中的元素对应关系重新映射HashTable<K, V, HashFunc> newHT;newHT._table.resize(newsize);for (size_t i = 0; i < _table.size(); i++){if (_table[i]._state == EXIST){newHT.Insert(_table[i]._kv);}}_table.swap(newHT._table);}size_t hashi = hf(kv.first) % _table.size();while (_table[hashi]._state == EXIST){++hashi;hashi %= _table.size();}// 到这时，状态要么是DELETE要么是EMPTY// 可以直接插入_table[hashi]._kv = kv;_table[hashi]._state = EXIST;++_n;return true;}HashData<const K, V>* Find(const K& key){HashFunc hf;size_t hashi = hf(key) % _table.size();// 当对应位置不为空时才进入查找while (_table[hashi]._state != EMPTY){if (_table[hashi]._state == EXIST&& _table[hashi]._kv.first == key){// 需要手动强转类型，因为不支持默认的自动类型转换return (HashData<const K, V>*) & _table[hashi];}++hashi;hashi %= _table.size();}return nullptr;}// 这里的删除应该只是改变元素状态bool Erase(const K& key){HashData<const K, V>* ret = Find(key);if (ret != nullptr){ret->_state = DELETE;--_n;return true;}return false;}private:vector<HashData<K, V>> _table;size_t _n = 0; // 存储有效数据的个数};
}

3.优缺点分析

线性探测优点：实现非常简单，
线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。如何缓解呢？

4.二次探测

线性探测的缺点是会导致冲突的数据集中在一起，这与它寻找下一个空位置的方式有关，因为它是按照顺序逐一查找的。为了避免这个问题，二次探测采用了一种不同的方法来找到下一个空位置，即：Hi​ = (H0​ + i^2 )% m 或 Hi​ = (H0​ - i^2 )% m。其中，i = 1,2,3…，H0​ 是通过散列函数 Hash(x) 对元素的关键码 key 进行计算得到的位置，m 是表的大小。

研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。

因此，我们可以知道闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。 

②开散列

1.原理说明

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
举例如图所示

从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

2.代码实现

// 开散列
namespace hash_bucket
{template<class K, class V>struct HashNode{pair<K, V> _kv;HashNode* _next;HashNode(const pair<K, V>& kv):_kv(kv),_next(nullptr){}};template<class K>struct DefaultHashFunc{size_t operator()(const K& key){return (size_t)key;}};// 这里可以使用偏特化对string的hashi进行处理template<>// BKDRHashFuncstruct DefaultHashFunc<string>{size_t operator()(const string& str){size_t hash = 0;for (auto ch : str){hash *= 131;hash += ch;}return hash;}};// 这里的HashFunc是当传入的K不为数字类型时，将其转换为对应的数字template<class K, class V, class HashFunc = DefaultHashFunc<K>>class HashTable{typedef HashNode<K, V> Node;public: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 pair<K, V>& kv){// 如果已经存在相同值就不再插入if (Find(kv.first)){return false;}HashFunc hf;// 桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，// 极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能// 因此在一定条件下需要对哈希表进行增容,最好的情况是：// 每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，// 因此，在元素个数刚好等于桶的个数时，可以给哈希表增容。if (_n == _table.size()){size_t newsize = _table.size() * 2;vector<Node*> newtable(newsize, nullptr);size_t i = 0;for (i = 0; i < _table.size(); i++){Node* cur = _table[i];// 将一个节点的全部桶重新挂到新的哈希表中while (cur){Node* next = cur->_next;size_t hashi = hf(cur->_kv.first) % newsize;// 在hashi处头插cur->_next = newtable[hashi];newtable[hashi] = cur;cur = next;}}}size_t hashi = hf(kv.first) % _table.size();Node* newnode = new Node(kv);newnode->_next = _table[hashi];_table[hashi] = newnode;++_n;return false;}Node* Find(const K& key){HashFunc hf;size_t hashi = hf(key) % _table.size();Node* cur = _table[hashi];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;}bool Erase(const K& key){HashFunc hf;// 删除某一个节点时需要上一个节点的信息Node* prev = nullptr;size_t hashi = hf(key) % _table.size();Node* cur = _table[hashi];while (cur){if (cur->_kv.first == key){if (cur == _table[hashi]){_table[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;}void Print(){for (size_t i = 0; i < _table.size(); i++){printf("[%d]->", i);Node* cur = _table[i];while (cur){cout << cur->_kv.first << ":" << cur->_kv.second << "->";cur = cur->_next;}printf("NULL\n");}cout << endl;}private:vector<Node*> _table; // 指针数组size_t _n = 0; // 存储了多少个有效数据};
}

③闭散列与开散列的比较

闭散列和开散列在处理哈希冲突时各有优缺点。

在存储效率上，闭散列采用顺序表存储，存储效率较高。而开散列采用单链表存储方式，因为附加了指针域，空间开销相对较大；在冲突解决方式上，闭散列方法是在哈希表中寻找下一个空闲位置来解决冲突，因此容易产生堆积，查找不易实现，可能需要二次再查找。而开散列方法则是将冲突的关键码存储在另一个数据结构中，避免了堆积现象，查找相对容易。

综上所述，闭散列和开散列在存储效率和冲突解决方式上存在差异，具体选择哪种方案需要根据实际情况来决定。

4.哈希的应用

①位图

对于下面这个问题

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。

对此，我们有三种解决办法

1. 遍历，时间复杂度O(N)
2. 排序(O(NlogN))，利用二分查找: logN
3. 位图解决
数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。 

对于前面两种方法，在数据量达到40亿时，若要将其储存起来差不多会消耗 40亿*4byte = 1600万kb =  16000 mb = 16gb 的内存空间，这显然是做不到的，此时我们就需要第三种方法来解决，即位图，举例如下

在这里让我们模拟实现其关键接口，即set, reset, test

template<size_t N>
class my_bitset
{
public:my_bitset(){// 一个size_t是4个字节即32个比特位，在这里即以32个比特为一个单元_a.resize(N / 32 + 1);}// 将x位置的值映射为1void set(size_t x){size_t i = x / 32;size_t j = x % 32;// 只将该位置的值映射为1，其他位置维持不变_a[i] |= (1 << j);}// 将x位置的值映射为0void reset(size_t x){size_t i = x / 32;size_t j = x % 32;// 只将该位置的值映射为0，其他位置维持不变_a[i] &= (~(1 << j));}// 判断x位置的值是否为1bool test(size_t x){size_t i = x / 32;size_t j = x % 32;return _a[i] & (1 << j);}private:vector<int> _a;
};

②布隆过滤器

1.布隆过滤器概念

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。

举个例子

当向位图中插入一个数据时，会先根据不同的哈希函数计算出不同的对应下标，然后将对应的值标记成1，再插入一个值时，有

在查找时，可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。
注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判。举个例子，如在布隆过滤器中查找某个元素是否存在时，假设3个哈希函数计算的哈希值刚好和其他元素的比特位重叠，此时布隆过滤器告诉该元素存在，但实该元素是不存在的。

那么如何删除元素呢？其实布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。举个例子，在删除上图中"apple"元素时，如果直接将该元素所对应的二进制比特位置0，“banana”元素也被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。那我们该如何进行删除操作呢？在此，可以给出一种支持删除的方法：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作。但是这种方法也有缺陷，即存在计数回绕，当计数器的值达到其最大值（例如32位整数的最大值）时，再次增加计数器的值会导致其回到最小值（0）。这在布隆过滤器中可能会导致问题，因为如果一个元素被删除了（计数器减一），然后再次被插入（计数器加一），那么这个元素的计数器可能会回绕到最初的0，即使这个元素实际上仍然存在于布隆过滤器中。

2.布隆过滤器的模拟实现

// 三种计算字符串转换为数值的不同计算方法
struct BKDRHash
{size_t operator()(const string& str){size_t hash = 0;for (auto ch : str){hash = hash * 131 + ch;}return hash;}
};struct APHash
{size_t operator()(const string& str){size_t hash = 0;for (size_t i = 0; i < str.size(); i++){size_t ch = str[i];if ((i & 1) == 0){hash ^= ((hash << 7) ^ ch ^ (hash >> 3));}else{hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));}}return hash;}
};struct DJBHash
{size_t operator()(const string& str){size_t hash = 5381;for (auto ch : str){hash += (hash << 5) + ch;}return hash;}
};template<size_t N,class K = string,class Hash1 = BKDRHash,class Hash2 = APHash,class Hash3 = DJBHash>
class BloomFilter
{
public:void Set(const K& key){size_t hashi1 = Hash1()(key) % N;_bs.set(hashi1);size_t hashi2 = Hash2()(key) % N;_bs.set(hashi2);size_t hashi3 = Hash3()(key) % N;_bs.set(hashi3);}bool Test(const K& key){size_t hashi1 = Hash1()(key) % N;if (_bs.test(hashi1) == false)return false;size_t hashi2 = Hash2()(key) % N;if (_bs.test(hashi1) == false)return false;size_t hashi3 = Hash3()(key) % N;if (_bs.test(hashi1) == false)return false;return ture;}private:bitset<N> _bs;
};

3.布隆过滤器的优缺点

优点

1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关
2. 哈希函数相互之间没有关系，方便硬件并行运算
3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

 缺点

1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)
2. 不能获取元素本身
3. 一般情况下不能从布隆过滤器中删除元素
4. 如果采用计数方式删除，可能会存在计数回绕问题

③海量数据处理

1.哈希切割

给一个超过 100G 大小的 log file, log 中存着 IP 地址 , 设计算法找到出现次数最多的 IP 地址？如何找到top K 的 IP ？

在这里我们需要用到哈希切割，在这之前我们要先了解一下什么是哈希切割

哈希切割是一种将大文件分割成多个小文件的方法，其本质是将小文件当做哈希桶，将大文件中的query通过哈希函数映射到这些哈希桶中，如果是相同的query，则会产生哈希冲突进入到同一个小文件中。

举个例子 这样经过切分后，不同的ip地址就存入了不同的小文件中，此时再用map去统计各个小文件中ip出现次数即可

2.位图应用

给定 100 亿个整数，设计算法找到只出现一次的整数？

这里可以设计用两个位来标记一个数的算法，如图所示

这里可以用两个位图来标记，算法具体实现如下

template <size_t N>
class TwoBit
{void set(size_t x){// 对于没有出现过的元素——00要将其变为01if (!bs1.test(x) && !bs1.test(x)){bs2.set(x);}// 对于出现过一次的元素——01要将其变为10else if (!bs1.test(x) && bs2.test(x)){bs1.set(x);bs2.reset(x);}// 对于出现过一次以上的元素——10不变即可}bool is_once(size_t x){// 判断是否为01即可return !bs1.test(x) && bs2.test(x);}private:bitset<N> bs1;bitset<N> bs2;
};

给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？ 

对此，我们可以用两个位图来分别标识两个文件中的数据，第一个文件遇见一个数就将第一个位图的对应位置set为1，第二个文件遇见就将第二个位图的对应位置set为1，在标识完所有数据后，将两个位图&一下，这样得到的位图中所有为1的数据即为交集

1 个文件有 100 亿个 int ， 1G 内存，设计算法找到出现次数不超过 2 次的所有整数

对此，我们采取与第一个方式差不多的方法，即用两个位图标识一个数，标识完所有的数后，找到所有为01或者10的数据，即为出现次数不超过两次的整数。

3.布隆过滤器

给两个文件，分别有 100 亿个 query ，我们只有 1G 内存，如何找到两个文件交集？分别给出 精确算法和近似算法

对此，我们可以用哈希切分来解决问题，具体解决如下

将两个文件分别哈希切分到若干个小文件中，第一个文件切分到A_1, A_2, ... A_n，第二个文件切分到B_1, B_2, ...B_n，这样对应的query会被切分到对应编号的小文件中，然后我们先将A_i的数据读入到一个set中，然后在对应的B_i中去判断，如果存在就是交集，反之。

即

但是这种解决办法存在一些问题：哈希切分并不是均匀的切分，当哈希冲突过多时，某一个文件会超出预计的1G内存，此时又该如何解决呢？

此时这个文件可以被分为两种情况：一种是大部分query相同少部分相冲突，另一种是大部分的query都是相冲突的。对此我们的解决方案如下
1.将A_i的数据全部插入到一个set中，如果set抛异常（bad_alloc）说明申请内存过多，即此时大部分的query都是互相冲突的，如果插入成功说明此时大部分的query都是相同的；

2.如果结果是抛异常的话需要更换一个哈希函数进行二次切分，即将这个小文件进行再次的哈希切分。