Hash

平衡二叉树

通过比较保证有序，每次搜索都能够排除一半，时间复杂度O(log2为低n)

100万节点 –最多比较次数 20次

10亿节点 – 最多比较次数 30次

散列表

根据key计算key在表中的位置的数据结构，是key和其所在存储地址的映射关系

struct node
{
    void *key;
    void *val;
    struct node *next;
};

散列表
拉链法

散列表组成

hash函数

通过映射函数Hash(key) = addr; hash函数可能会把两个或两个以上的不同key映射到同一地址，这种情况称之为冲突(或者Hash碰撞)。

选择hash

  • 计算速度快
  • 强随机分布(等概率，均匀地分布在整个地址空间)
  • 常见hash算法: murmurhash2 -使用最频繁的,cityhash强随机分布性,siphash -redis的主要解决字符串接近的强随机分布性 测试地址

hash 冲突

负载因子

数组存储的元素个数/数组长度：用来形容散列表的存储密度；负载因子越小，冲突概率越小，负载因子越大，冲突概率越大

解决冲突

链表法

将冲突元素用链表链接起来。(极端情况，冲突元素越多，冲突链表过长，可将此链表转换为红黑树，最小堆 –可以采用超过256个节点(经验值)将链表结构转换为红黑树或堆结构)

redis，stl-unorder

散列表
拉链法

开放寻址法

将所有的元素都存放在哈希表的数组中，不使用额外的数据结构

  • 当插入新元素时，使用哈希函数在哈希表中定位元素位置
  • 检查数组中该槽位索引是否存在元素，若槽位为空，则插入，否则3
  • 在2检测的槽位索引加上一定步长接着检查2

也可使用双重hash解决hash聚集现象
在 . net HashTable 类的 hash 函数 Hk 定义如下：
Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize
在此 (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1))) 与 hashsize 互为素数（两数互为素数表示两者没有共同的质因 ⼦ ） ；
执 ⾏ 了 hashsize 次探查后， 哈希表中的每⼀个位置都有 且只有⼀次被访问到， 也就是说， 对于给定的 key ，对哈希表中的同 ⼀ 位置不会同时使 ⽤Hi和Hj ；

负载因子不再合理范围内

used > size –扩容| used < 0.1size –缩容

扩容/缩容之后 – rehash

STL散列表实现

unordered *

为了实现迭代器，将后面具体节点串成一个单链表,

当插入一个新的节点是，hash之后将该节点指向上一层的最后一个节点。以实现迭代器

STL散列表实现
STL散列表实现

布隆过滤器

布隆过滤器是一种概率性数据结构，高效地插入和查询,不存储具体数据，占用空间小，查询结果存在误差，可以确定一定不存在，但不能确定一定存在，不支持删除操作

背景

内存有限，只想确定某个key存不存在，不想知道具体内容

当数据key,value存入某个文件时，将对应的key，映射到文件的布隆过滤器中，当查询时，不需要读取文件到内存，只需要查询布隆过滤器(其放在内存当中)，对应的key是否存在即可。 – 数据库rocksdb

数据库MySql – 查看key是否在MySQL当中，在服务器端部署布隆过滤器，查询时，查布隆过滤器

构成

使用位图BIT数组 + n个hash函数

vector<char> bitmap;
uint64_t bitmap ;  //数组

（图片 image-20230705084805312.png 未随仓库迁移，原引用路径已失效）

原理

  • 当一个元素加入位图时，通过k个hash函数将这个元素映射到位图的k个点，并把他们置为1。
  • 当检索时，再通过k个hash函数运算检测位图的k个点是否都是1,如果有不为1的点，那么认为该key不存在，
  • 如果全部为1，则可能存在。
  • 不支持删除只有两种状态1或0，不确定槽位被设置多少次，也不知道被多少个key hash映射而来以及是被具体哪个hash函数映射而来。

布隆过滤器
布隆过滤器

应用分析

  • n -- 预期布隆过滤器中元素的个数
  • p – 假阳率 在0-1之间
  • m – 位图所占空间
  • k – hash函数的个数

n,p确认m,k

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));
  • 随着n越来越多，假阳率也越来越高

pVSn
PVSn

  • 位图所占空间越来越大，假阳率也就越来越低

pVSm
pVSM

  • hash函数的个数越多，假阳率降低到一个水平，开始缓慢上升。 大约31最低

pVSk
pVSk

应用场景

布隆过滤器通常用于判断某个key一定不存在的场景，同时允许判断存在时有误差的情况

  • 缓存穿透解决
  • 热key限流

数据库redis
数据库redis

  • 缓冲穿透

redis，MySQL都没有数据，黑客可以利用此漏洞导致MySQL压力过大，如果以来真个系统将陷入瘫痪

  • 读取步骤
  • 先访问redis，如存在，直接返回，如不存在走2
  • 访问MySQL，如果不存在，直接返回，如存在走3
  • 将MySQL存在的key写回redis
  • 解决步骤
  • 在redis端设置<key,null> 键值对，以此避免访问MySQL；缺点是<key,null>过多的话，占用过多内存
  • 可以给key设置过期 expire key 600ms，停止攻击后最后由redis自动清除这些无用的key
  • 在server端存储一个布隆过滤器，将MySQL包含的key放入布隆过滤器中，布隆过滤器一定不存在的数据
  • 为了减轻数据MySQL的访问压力，在server端与数据库MySQL之间加入缓存用来存储热点数据
  • 描述缓存穿透，server端请求数据时，缓存和数据库都不包含该数据，最终请求压力全部涌向数据库

只用2G内存在20亿个整数中找到出现次数最多的数

大文件 hash拆成小文件

单台机器 hash 分流到多台机器

主要解决 : 分布式缓存扩容问题

k 整数

v 出现次数 – -需要内存uint32 4个字节 （21.49亿

一个key value对8个字节 2亿个 – 需要1.6G内存

20亿 — 需要16G内存

使用散列表

  • 拆分成若干等份(把10亿个整数的大文件拆分成多个文件中)
  • 目的: 把相同的整数放到同一个文件
  • 通过Hash的强随机性将相同整数放到统一文件中
  • 分别在每个文件中找出最大值。

分布式一致性hash

分布式一致性hash算法将哈希空间组织称一个虚拟的圆环，圆环的大小是2^32；

算法为：hash(ip)%2^32 ,最终会得到一个[0~2^32-1] 之间的无符号整型，这个整数代表服务器的编号；多个服务器都通过这种方式在hash换上映射一个点来标识该服务器的位置，当用户操作某个key，通过同样的算法生成一个值，沿环顺时针定位某个服务器，那么该key就在该服务器中

分布式hash
分布式一致性hash

应用场景

将数据均衡地分散在不同的服务器当中，用来分摊缓存服务器的压力

解决缓存服务器数量变化尽量不影响缓存失效

hash偏移

服务器承受的压力不均匀

hash偏移
hash偏移

虚拟节点

添加虚拟节点的概念；理论上哈希环上节点数越多，数据分布越均衡

为每个服务器节点计算多个哈希节点(虚拟节点); 通常做法是，hash("IP:PORT:seqno")%2^32;

hash(key) % 分布式个数 确认存储位置

  • 当分布式个数增加一个之后，算法发生改变，原有映射

原有三个分布式节点

1,2,3,4 % 3 存储位置： 1,2,0,1

添加一个节点后:

1,2,3,4 % 4 存储位置： 1,2,3,0

算法发生改变，3,4，会出现大面积缓存失效，

解决方法:

  • 固定算法解决缓存失效

hash(key) % 2^32 = index

  • 改变查找节点的映射关系，把具体的地址hash到圆环(逻辑)上，(顺时针查找) – 局部缓存失效

hash(node-ip:port) % 2^32 = index

  • hash迁移， – 解决局部缓存失效
  • hash强随机性，样本越大，

虚拟节点
虚拟节点