哈希表&位图&topk&一致性哈希算法

哈希表&位图&topk&一致性哈希算法

文章目录

​​一、哈希表​​​​二、线性探测哈希表​​​​三、链式哈希表​​​​四、哈希表相关面试题​​​​五、位图大数据查重​​​​六、布隆过滤器Bloom Filter​​​​七、topK问题​​

​​（1）堆排序求topk​​​​（2）快排分割求topk​​

​​八、一致性哈希算法​​

​​（1）负载场景​​​​（2）缓存场景​​​​（3）解决方法：一致性哈希算法​​

一、哈希表

二、线性探测哈希表

哈希表的长度最好是素数表中的数，哈希表扩容的时候也是从哈希表中取得，扩容后需要把原来表中的数据重新哈希，存入新的哈希表

装载因子：当表的使用量 超过 总容量 * 装载因子 时，需要进行扩容，使用哈希表的 均摊时间复杂度是O(1)

enum State { UNUSE, // 从未被使用 USING, // 正在使用 DELETE // 使用后被删除};struct Node { Node(int val = 0, State state = UNUSE) :val_(val) , state_(state) {} int val_; State state_; // 节点的状态};class HashTable {public: HashTable(int cap = primes_[0], double load_factor = 0.75) : load_factor_(load_factor) , prime_idx(0) , size_(0) { // 如果用户传入的cap不符合素数表，需要重新指定cap_ if (cap != primes_[0]) { for (; prime_idx < PRIMES_SIZE; prime_idx++) { if (primes_[prime_idx] >= cap) { break; } } // 用户传入的cap过大，不合法，重新指定cap_ if (prime_idx == PRIMES_SIZE) { prime_idx--; } } cap_ = primes_[prime_idx]; table_ = new Node[cap_]; } ~HashTable() { delete[] table_; table_ = nullptr; }public: // 可以插入重复的val bool insert(int val) { cout << "哈希表使用因子：" << size_ * 1.0 / cap_ << endl; if (size_ >= load_factor_ * cap_) { cout << "当前使用：" << size_ << " 哈希表总容量：" << cap_ << " 需要扩容" << endl; expand(); cout << "扩容完成，当前容量："<

缺点：

发生冲突时，线性探测的过程会逐渐逼近O(n)，存储会比较慢C++ STL中的所有容器都不是线性安全的，需要额外进行同步互斥操作，并且锁的粒度很大，需要锁住整个数组。

三、链式哈希表

若使用线性探测哈希表，要锁住整个数组。使用链式哈希表，则可以只使用分段的锁（锁住一个桶即可），既保证了线程安全，又有一定的并发量，提高了效率

优化空间：

当数组里每个链表过长时，可以把链表转成红黑树O(n)链式哈希表都可以创建自己的锁（分段锁），不同的桶中的操作是可以并发的

class HashTable {public: // size用于初始化vector的大小 HashTable(int size = primes_[0], double load_factor=0.75) : load_factor_(load_factor) , prime_idx(0) , use_num(0) { if (size != primes_[0]) { for (; prime_idx < PRIMES_SIZE; prime_idx++) { if (primes_[prime_idx] >= size) { break; } } if (prime_idx == PRIMES_SIZE) { prime_idx--; } } // 开辟空间，并且创建元素:table_.size() == primes_[prime_idx] && table_.capacity == primes_[prime_idx] table_.resize(primes_[prime_idx]); } // 实现为不可重复插入 bool insert(int val) { bool inserted = false; double factor = use_num * 1.0 / table_.size(); cout << "当前装载因子：" << factor << endl; if (factor >= load_factor_) { cout <<" 需要扩容" << endl; expand(); cout << "扩容完成，当前容量："<> tmp; // 资源交换过来后，局部变量出作用域自动析构 table_.swap(tmp); // 若使用相同的容器适配器，只是交换成员变量 table_.resize(primes_[++prime_idx]); // 遍历旧表中的元素，然后重新哈希 for (list l : tmp) { for (int val : l) { int idx = val % table_.size(); if (table_[idx].empty()) { use_num++; } table_[idx].emplace_front(val); // 链表头插 } } }private: vector> table_; double load_factor_; // 装载因子 int use_num; static const int PRIMES_SIZE = 10; static const int primes_[PRIMES_SIZE]; int prime_idx; // 当前哈希表使用的素数};const int HashTable::primes_[PRIMES_SIZE] = { 3,7,23,47,251,443,911,1471,42773 };

四、哈希表相关面试题

有两个文件，分别存放了一些ip地址，找出同时在两个文件中都出现的ip地址

把一个文件的ip放在一个哈希表，然后遍历另一个文件的同时在哈希表中查找，找到则输出

有两个文件，分别存放了1亿个数，每条数字4B，限制内存100MB，找出同时在两个文件中都出现的数

1亿 约等于 100M 100M * 4B = 400MB数据 ==> 放入链式哈希表后，还需要增加400MB的地址域，一共800MB

将两个大文件分成足够多的小文件，使得哈希过后将数字存入每个小文件的数据不至于超过100MB，这样相同的数必然会被哈希到下标相同的小文件中。

把某个a小文件全部读入内存中的哈希表，然后从下标相同的b文件中挨个读取数据，然后在哈希表中查找，找到则在两个文件中重复出现

五、位图大数据查重

现在有1亿个数据，最大值为1亿，每个数字4B，限制内存100MB

若使用哈希表，需要使用100M * 4B * 2 = 800MB

使用位图，则只需要使用100000000bit，(100000000/8+1)B = 12500000 = 12.5MB

位操作： ​​|​​​ 是赋值的，​​&​​是求值的

templatevoid show_repeat(const vector& vec, T bit_map_type = char()) { int max_val = *max_element(vec.begin(), vec.end()); char* bitmap = new char[max_val / (sizeof(char) * 8) + 1](); unique_ptr ptr(bitmap); for (int v : vec) { int index = v / (sizeof(T) * 8); int offset = v % (sizeof(T) * 8); // &用于取出某个bit，|用于对某个bit赋值 if ((bitmap[index] & (1 << offset)) == 0) { bitmap[index] |= (1 << offset); } else { cout << v << "重复" << endl; } }}int main() { vector vec = {42,3,45,423,15,1,23,1,3412,45,12,45,2,65,412,5,4}; show_repeat(vec, int()); return 0;}

位图适用场景： 数据数量和数据的最大值相当的时候适用，不适用于数据很少，但是最大值很大的情况，因为要按照最大值开辟内存空间

六、布隆过滤器Bloom Filter

增加元素： 把key用k个哈希函数计算后，得到一组下标，将Bloom Filter中对应的bit置为1

搜索元素： 把key用k个哈希函数计算后，得到一组下标，若Bloom Filter中对应的bit全为1，那这个key有可能存在，若对应的bit不全为1，则key肯定不在。Bloom Filter存在一定的误判率，但随着其长度和哈希函数的增加，误判率会大大降低

删除元素： Bloom Filter不提供删除操作，若key1和key2有公用的bit，删除key1对应的bit后，那也改变了key2对应的bit，再查找key2的时候，也就查不到key2了

一些应用场景

优点： 结合了哈希表的效率高和位图的省内存的优点，但是会存在一定的误判率，但随着其长度和哈希函数的增加，误判率会大大降低

#include#include#include#include"stringhash.h"using namespace std;class BloomFilter {public: BloomFilter(int bit_cap = 1471) : bit_cap_(bit_cap) , type_size_(sizeof(char)) { bit_map_.resize(bit_cap_ / (type_size_ * 8) + 1); } // 往Bloom Filter中插入key void set_bit(const char* key) { int idx1 = BKDRHash(key) % bit_cap_; int idx2 = RSHash(key) % bit_cap_; int idx3 = APHash(key) % bit_cap_; int index = 0; int offset = 0; index = idx1 / (type_size_ * 8); offset = idx1 % (type_size_ * 8); bit_map_[index] |= (1 << offset); index = idx2 / (type_size_ * 8); offset = idx2 % (type_size_ * 8); bit_map_[index] |= (1 << offset); index = idx3 / (type_size_ * 8); offset = idx3 % (type_size_ * 8); bit_map_[index] |= (1 << offset); } // 查询key是否存在于Bloom Filter bool get_bit(const char* key) { int idx1 = BKDRHash(key) % bit_cap_; int idx2 = RSHash(key) % bit_cap_; int idx3 = APHash(key) % bit_cap_; int index = 0; int offset = 0; index = idx1 / (type_size_ * 8); offset = idx1 % (type_size_ * 8); if ((bit_map_[index] & (1 << offset)) == 0) { return false; } index = idx2 / (type_size_ * 8); offset = idx2 % (type_size_ * 8); if ((bit_map_[index] & (1 << offset)) == 0) { return false; } index = idx3 / (type_size_ * 8); offset = idx3 % (type_size_ * 8); if ((bit_map_[index] & (1 << offset)) == 0) { return false; } return true; } private: int bit_cap_; int type_size_; vector bit_map_; };class BlackList {public: void add(string url) { bloom_filter_.set_bit(url.c_str()); } bool query(string url) { return bloom_filter_.get_bit(url.c_str()); }private: BloomFilter bloom_filter_;};int main() { BlackList b_list; b_list.add("baidu.com"); b_list.add("alibaba.com"); b_list.add("tencent.com"); cout << b_list.query("baidu.com") << endl; cout << b_list.query("alibaba.com") << endl; cout << b_list.query("tencent.com") << endl; cout << b_list.query("bytedance.com") << endl; return 0;}

这里总结一下Bloom Filter的注意事项：

Bloom Filter是通过一个位数组+k个哈希函数构成的。Bloom Filter的空间和时间利用率都很高，但是它有一定的错误率，虽然错误率很低，Bloom Filter判断某个元素不在一个集合中，那该元素肯定不在集合里面；Bloom Filter判断某个元素在一个集合中，那该元素有可能在，有可能不在集合当中。Bloom Filter的查找错误率，当然和位数组的大小、哈希函数的个数有关系，具体的错误率计算有相应的公式（错误率公式的掌握看个人理解，不做要求）。Bloom Filter默认只支持add增加和query查询操作，不支持delete删除操作（因为存储的状态位有可能也是其它数据的状态位，删除后导致其它元素查找判断出错）。

Bloom Filter增加元素的过程： 把元素的值通过k个哈希函数进行计算，得到k个值，然后把k当作位数组的下标，在位数组中把相应k个值修改成1。

Bloom Filter查询元素的过程： 把元素的值通过k个哈希函数进行计算，得到k个值，然后把k当作位数组的下标，看看相应位数组下标标识的值是否全部是1，如果有一个为0，表示元素不存在（判断不存在绝对正确）；如果都为1，表示元素存在（判断存在有错误率）。

所以用Bloom Filter需要少量的内存就可以判断元素是否存在集合当中，当需要查找同时在a、b两个大文件中都出现的元素时，我们可以用a文件的数据构建Bloom Filter的位数组中的状态值，然后再读取b文件的数据进行布隆过滤的查找操作就可以了

​

七、topK问题

（1）堆排序求topk

求最小的K个元素，用大根堆：堆中加入小的，淘汰大的

求最大的K个元素，用小根堆：堆中加入大的，淘汰小的

时间复杂度： O(logK)*O(n) = O(n)

手写堆，实现求最大的k个数

求出最大的K个元素，使用小根堆 把数组前K个元素建立一个小根堆，从前K个元素第一个内部节点（K-1）/2开始建堆

建堆完成后，开始遍历数组的其他元素

若当前元素大于堆顶元素，则淘汰堆顶元素，将当前元素放在堆顶，然后对堆顶元素调堆若当前元素小于堆顶元素，则直接遍历下一个元素

// 在[0,size-1]的范围内调堆，使下标为cur的元素满足堆性质void sift_down(int arr[], int cur, int size) { int val = arr[cur]; int n = size - 1; while (cur <= (size - 2) / 2) { int min_child = 2 * cur + 1; // 若满足while循环条件，则必然存在左孩子 if (2 * cur + 2 <= n) { min_child = arr[min_child] < arr[2 * cur + 2] ? min_child : 2 * cur + 2; } if (arr[min_child] < val) { arr[cur] = arr[min_child]; cur = min_child; } else { break; } } arr[cur] = val;}int main() { int arr[10] = { 11,54,62,45,27,98,7,625,37,59 }; int k = 5; for (int i = (k - 1 - 1) / 2; i >= 0; i--) { sift_down(arr, i, k); } int n = sizeof(arr) / sizeof(arr[0]); for (int i = k; i < n; i++) { if (arr[i] > arr[0]) { arr[0] = arr[i]; sift_down(arr, 0, k); } else { continue; } } for (int i = 0; i < k; i++) { cout << arr[i] << " "; } return 0;}

使用内置的优先级队列和哈希表实现统计出现次数最少的k个数字

int main() { int k = 5; vector vec; srand(time(nullptr)); for (int i = 0; i < 1000; i++) { vec.push_back(rand() % 100); } // 统计元素出现的个数 unordered_map mp; for (int key : vec) { mp[key]++; } using Type = pair; using Comp = function; priority_queue, Comp> max_heap( [](Type& a, Type& b)->bool { return a.second < b.second; // 大根堆 } ); auto iter = mp.begin(); for (int i = 0; i < k; i++, iter++) { max_heap.push(*iter); } for (; iter != mp.end(); iter++) { if (iter->second < max_heap.top().second) { max_heap.pop(); max_heap.push(*iter); } } while (!max_heap.empty()) { cout <<"value:"<< max_heap.top().first << " times:" << max_heap.top().second << endl; max_heap.pop(); } return 0;}

（2）快排分割求topk

int partition(int arr[], int begin, int end, int k) { int l = begin; int r = end; int val = arr[l]; while (l < r) { while (l < r && arr[r] > val) { r--; } if (l < r) { arr[l] = arr[r]; l++; } while (l < r && arr[l] < val) { l++; } if (l < r) { arr[r] = arr[l]; r--; } } arr[l] = val; return l;}// 递归函数作用：能把[begin, end]区间内，前topk的元素放在[0, k]void select_topk(int arr[], int begin, int end, int k) { int pos = partition(arr, begin, end, k); if (pos == k - 1) { return; } else if (pos < k - 1) { select_topk(arr, pos + 1, end, k); } else { select_topk(arr, begin, pos - 1, k); }}

最好时间复杂度： 每次基准数都在中间，二叉树很平衡，n+n/2+…+1 = O(n)最坏时间复杂度： 数据本就有序，基准数每次都在最边上，二叉树退化为链表，O(n^2)

八、一致性哈希算法

（1）负载场景

经过哈希算法​​hash(ip:port)%N​​，同一客户的请求都会被映射到相同的服务器上，这有效解决了会话共享 的问题，这时候就不需要加入redis缓存服务器去记录客户的登录状态，避免引用外部模块过多导致系统不稳定的问题。

但这种方法也有问题，比如当某个服务器宕机了（或增加服务器），这时候​​N​​的值就发生改变，导致相同客户的请求就不一定还会转发到以前那台服务器上，这会发生身份认证的问题。

我们想要的是 同一 ip:port 的请求，永远被映射到同一台server上处理

（2）缓存场景

客户通常发请求查询信息的时候，是现在缓存服务器上查找，查找不到再到DB查找，然后把数据从DB转移到缓存服务器。

若此时有一台服务器宕机了，同理在0号缓存服务器中的信息再次被查询时，这个请求很有可能会被转发到1号服务器，此时无法在1号缓存服务器中找到信息，就会去DB中查找，此时大量的磁盘IO会严重影响server的响应速度。更严重来讲，一台服务器的负载太高，可能会影响整个系统的运转，甚至崩溃若此时增加了一台服务器，​​N​​发生改变。举个极端的例子，此时所有的请求都被转发到新的服务器中，新的服务器无法查询到相应信息，同理会产生大量的磁盘IO，甚至服务器崩溃

我们的理想情况是：

某个server挂了，不影响其他server的正常运转，不会请求急剧增加server增加了，不影响原来server的请求，只会把后续的请求映射到新的server上

（3）解决方法：一致性哈希算法

为解决普通哈希算法导致的以上问题，提出一致性哈希算法（分布式系统负载均衡的首选算法）

一个良好的分布式哈希方案应该具有良好的单调性，即服务节点数量的改变不会造成大量哈希的重新定位

算法过程

容错性分析

假设server A 宕机了，那原来在server C的请求2、3依然在server C，原来在server B的请求4依然在server B，只是原来在server A的请求会被转发到server C假设多了一台server D放在如下位置，这只会影响新增server D与逆时针碰到的第一个server C之间的请求4，不会影响到其他的请求，这将影响降到了最低

为了达到良好的负载均衡，经过一致性哈希算法后的 server最好在哈希环上分散开，所以一般我们要在哈希环上加入物理节点的虚拟节点。加入物理节点的虚拟节点可防止由于物理节点过少，导致哈希处理后几台服务器挤在一起，从而导致某一台主机的负载过多，而其他空闲的情况

类设计如下：

#include#include#include#include

server ip :10.117.121.66该服务器服务的客户端有3个client ip :192.168.1.105192.168.1.109192.168.1.112-----------------------------server ip :10.117.121.67该服务器服务的客户端有5个client ip :192.168.1.100192.168.1.102192.168.1.103192.168.1.107192.168.1.110-----------------------------server ip :10.117.121.68该服务器服务的客户端有6个client ip :192.168.1.101192.168.1.104192.168.1.106192.168.1.108192.168.1.111192.168.1.113-----------------------------*********主机2宕机*********server ip :10.117.121.66该服务器服务的客户端有4个client ip :192.168.1.105192.168.1.109192.168.1.110192.168.1.112-----------------------------server ip :10.117.121.68该服务器服务的客户端有10个client ip :192.168.1.100192.168.1.101192.168.1.102192.168.1.103192.168.1.104192.168.1.106192.168.1.107192.168.1.108192.168.1.111192.168.1.113-----------------------------

该代码需要md5源码才可运行，需要可以私信

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。