散列表

• 与平衡二叉树比较：通过比较、结构有序，（利用二分查找）提升搜索效率
• 散列表：key与节点存储的映射关系
• 组成：hash函数；数组；
• hash函数：
  • 作用：解决映射关系
  • 选择依据：
    • 计算速度快
    • 强随机分布
    • murmurhash1（速度快，质量一般）、murmurhash2（平衡，经常用这个）、murmurhash3（计算慢，质量最好）、siphash（redis用，主要解决字符串接近的强随机分布性）、cityhash（也经常使用）
• 操作流程：
  • 插入
  • 搜索
• 冲突
  • 负载因子：数组存储元素个数/数组长度；用来形容散列表存储密度；负载因子越小，冲突概率越小，越大，冲突概率越大；
  • 解决冲突：负载因子在合理范围内（ used < size ）
    • 链表法（拉链法）：redis、stl等
    • 开放寻址法（线性探查法）：先hash到位置，发现已经冲突了，那么采用步长每次+1/+1^2来看是否可以，可以就存储，不可以就继续加步长探查；缺点：相似的key连续查询，会产生hash聚集现象，算法退化成O(N)，解决：双重hash；
  • 解决冲突：负载因子不在合理范围内（ used >= size or used < 0.1 * size）
    • 扩容：翻倍扩容
    • 缩容
    • rehash

STL散列表实现

• 基于红黑树实现：
  1. map
  2. set
  3. multimap
  4. muliset
• 基于散列表实现
  1. unordered_map
  2. unordered_set
  3. unordered_multimap
  4. unordered_multiset

1. 为了实现迭代器，将后面的节点穿成了一个单链表

布隆过滤器

• 背景：内存有限，不需要存储具体元素，只想确定key是否存在
• 构成
  • 位图
  • n个hash函数
• 怎么操作
  • hash(key)%bit_size = index
  • 不支持删除操作
• 要点
  • 能够确定一个key一定不存在，可控假阳率确定存在
  • 不能删除
  • 根据n和p，算出m和k

确定 n 和 p

• 在实际使用布隆过滤器时，首先需要确定 n 和 p，通过上面的运算得出 m 和 k；通常可以在下面这个网站上选出合适的值；https://hur.st/bloomfilter

选择 hash 函数

• 选择一个 hash 函数，通过给 hash 传递不同的种子偏移值，采用线性探寻（开放寻址法）的方式构造多个 hash 函数；

  1 2 3 4 5 6 7

  ##define MIX_UINT64(v) ((uint32_t)((v>>32)^(v))) uint64_t hash1 = MurmurHash2_x64(key, len, Seed); uint64_t hash2 = MurmurHash2_x64(key, len, MIX_UINT64(hash1)); for (i = 0; i < k; i++) // k 是hash函数的个数 { Pos[i] = (hash1 + i*hash2) % m; // m 是位图的⼤⼩ }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

假设有三个hash函数，h1,h2,h3
那么添加一个key=str1的操作就是，通过h1(str1),h2(str1),h3(str1)得到三个值，在布隆过滤器中都置为1
那么添加一个key=str2的操作就是，通过h1(str2),h2(str2),h3(str2)得到三个值，在布隆过滤器中都置为1

那么查询的时候，仍然查询h1(key)、h2(key)、h3(key);
不存在的情况：只要有一个索引位置为0
假设索引位置都为1，也不一定存在（但是是可控的，称为假阳率）
so，布隆过滤器主要解决了判断了一个值不存在的情况

n -- 预期布隆过滤器中元素的个数，如上图 只有str1和str2 两
个元素 那么 n=2
p -- 假阳率，在0-1之间 0.000000
m -- 位图所占空间
k -- hash函数的个数
公式如下：
n = ceil(m / (-k / log(1 - exp(log(p) / k))))
p = pow(1 - exp(-k / (m / n)), k)
m = ceil((n * log(p)) / log(1 / pow(2, log(2))));
k = round((m / n) * log(2));

解决缓存穿透

1. 缓存穿透：redis、mysql都没有数据，黑客可以利用此漏洞导致mysql压力过大，以此来使系统瘫痪；（缓存和数据库中都不包含的数据，最终压力全部给到mysql）
2. 解决：
   1. 在server端存储一个布隆过滤器，将mysql包含的key放入过滤器，过滤器能过滤掉一定不存在的数据；
   2. 在redis设置<key,null>键值对，缺点是过多占用内存（可以给key设置过期时间600ms，攻击停止这些数据会自动由redis清理）

使用案例

Example1

• Open Bloom Filter基本用法

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82

  ##include <iostream> ##include <string> ##include "bloom_filter.hpp" int main() { // 参数初始化 bloom_parameters parameters; // 多少个元素期望被加入到布隆过滤器中？ parameters.projected_element_count = 1000; // 假阳率 (0,1) parameters.false_positive_probability = 0.0001; // 1 in 10000 // 随机种子 (可选的) parameters.random_seed = 0xA5A5A5A5; if (!parameters) { std::cout << "Error - Invalid set of bloom filter parameters!" << std::endl; return 1; } // 根据n和p计算m和k parameters.compute_optimal_parameters(); // 根据参数初始化布隆过滤器 bloom_filter filter(parameters); std::string str_list[] = { "AbC", "iJk", "XYZ" }; { // 字符串加入 for (std::size_t i = 0; i < (sizeof(str_list) / sizeof(std::string)); ++i) { filter.insert(str_list[i]); } // 加入一些数字 for (std::size_t i = 0; i < 100; ++i) { filter.insert(i); } } // 对加入的结果进行检验 { // 查询刚才加入的字符串是否存在 for (std::size_t i = 0; i < (sizeof(str_list) / sizeof(std::string)); ++i) { if (filter.contains(str_list[i])) { std::cout << "BF contains: " << str_list[i] << std::endl; } } // 查询刚才加入的数字是否存在 for (std::size_t i = 0; i < 100; ++i) { if (filter.contains(i)) { std::cout << "BF contains: " << i << std::endl; } } std::string invalid_str_list[] = { "AbCX", "iJkX", "XYZX" }; // 查询不存在的字符串内容 for (std::size_t i = 0; i < (sizeof(invalid_str_list) / sizeof(std::string)); ++i) { if (filter.contains(invalid_str_list[i])) { std::cout << "BF falsely contains: " << invalid_str_list[i] << std::endl; } } // 查询不存在的数字内容 for (int i = -1; i > -100; --i) { if (filter.contains(i)) { std::cout << "BF falsely contains: " << i << std::endl; } } // 压缩布隆过滤器的大小，这会导致误报率变高 if (!filter.compress(5.0)) { std::cout << "Filter cannot be compressed any further." << std::endl; break; } } return 0; }

分布式一致性hash

• 解决了什么问题：分布式缓存中扩容问题（实现优雅扩容）
• 怎么解决：
  • 固定算法 —— 解决缓存失效
  • 数据迁移
  • 虚拟节点 —— 保证数据均匀

分布式缓存扩容造成缓存失效

• 当hash函数采用数组长度作为取余项时，增加节点会使之前的缓存大面积失效
• 解决方法：固定算法

固定算法解决缓存失效问题

• 固定hash函数后，缓存增加节点，但不会失效
• 将节点也映射到hash圆环上，使用顺时针查询的方法，决定key值存储在哪个节点的问题
• 如何解决增加节点，局部缓存失效问题？
  • hash迁移：当增加节点时，把失效的局部数据迁移到新的节点中

hash偏移

• 当样本数和节点数少的时候，会出现某个节点存储了大量数据，而其他少量数据的hash问题
• 如何解决
  • 增加虚拟节点

补充

https://github.com/metang326/consistent_hashing_cpp

1. 如何增加节点？

• 在新增一个实际节点后，会为它生成一些虚拟节点，每个虚拟节点有一个自己的哈希值，会对应到哈希环中的一个位置，插入新虚拟节点后可能会需要从后面位置的虚拟节点上“抢”一些数据。抢夺的数据可能与当前的虚拟节点是属于同一个实际节点的，例如：原本的虚拟节点列表为[1,100,500，1500]，在新增实际节点A时，先生成了一个虚拟节点1000，那么它会从1500节点上“抢”走范围在501 ~ 1000的数据；然后节点A又生成了一个哈希值为800的虚拟节点，那么就会从节点1000上“抢”走范围在501 ~ 800的数据。

2. 如何删除节点？

• 删除一个实际节点时，属于它的虚拟节点也要删除。如果在删除过程中，某个虚拟节点有存放数据，那么就要从当前虚拟节点的位置向后遍历，找到第一个不属于要被删除实际节点的虚拟节点。例如目前哈希值为1000、属于A实际节点的虚拟节点要被删掉了，1500节点也属于A，不能把数据迁移到这里；2000节点属于B，因此选择把1000节点上的数据迁移到2000节点。

散列表补充

• 只用2GB内存在20亿个整数中找到出现次数最多的数
• 40亿呢？
• 80亿呢？

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

  20亿级别 问：如果我给你 2GB 的内存，并且给你 20 亿个 int 型整数，让你来找出次数出现最多的数，你会怎么做？ 答：可以采用哈希表来统计，把这个数作为 key，把这个数出现的次数作为 value，之后我再遍历哈希表哪个数出现最多的次数最多就可以了。 问：你可以算下你这个方法需要花费多少内存吗？ 答：key 和 value 都是 int 型整数，一个 int 型占用 4B 的内存，所以哈希表的一条记录需要占用 8B，最坏的情况下，这 20 亿（9个0）个数都是不同的数，大概会占用 16GB （8*2*10^9B == 16GB）的内存。 问:你的分析是对的，然而我给你的只有 2GB 内存。按照你那个方法的话，最多只能记录大概 2 亿多条不同的记录，2 亿多条不同的记录，大概是 1.6GB 的内存。 答：可以把这 20 亿个数存放在不同的文件，然后再来筛选。那么我可以把这 20 亿个数映射到不同的文件中去，例如，数值在 0 至 2亿之间的存放在文件1中，数值在2亿至4亿之间的存放在文件2中….，由于 int 型整数大概有 42 亿个不同的数，所以我可以把他们映射到 21 个文件中去，显然，相同的数一定会在同一个文件中，我们这个时候就可以用我的那个方法，统计每个文件中出现次数最多的数，然后再从这些数中再次选出最多的数，就可以了。 问：嗯，这个方法确实不错，不过，如果我给的这 20 亿个数数值比较集中的话，例如都处于 1~20000000 之间，那么你都会把他们全部映射到同一个文件中，你有优化思路吗？ 答：那我可以先把每个数先做哈希函数映射，根据哈希函数得到的哈希值，再把他们存放到对应的文件中，如果哈希函数设计到好的话，那么这些数就会分布的比较平均。（关于哈希函数的设计，我就不说了，我这只是提供一种思路） 40亿级别 问：那如果我把 20 亿个数加到 40 亿个数呢？ 答：可以加大文件的数量啊。 问：那如果我给的这 40 亿个数中数值都是一样的，那么你的哈希表中，某个 key 的 value 存放的数值就会是 40 亿，然而 int 的最大数值是 21 亿左右，那么就会出现溢出，你该怎么办？ 答：（那我把 int 改为 long 不就得了，虽然会占用更多的内存，那我可以把文件分多几份呗，不过，这应该不是面试官想要的答案），我可以把 value 初始值赋值为 负21亿，这样，如果 value 的数值是 21 亿的话，就代表某个 key 出现了 42 亿次了。 80亿级别 问：那我如果把 40 亿增加到 80 亿呢？ 答：我可以一边遍历一遍判断啊，如果我在统计的过程中，发现某个 key 出现的次数超过了 40 亿次，那么，就不可能再有另外一个 key 出现的次数比它多了，那我直接把这个 key 返回就搞定了。