数据结构 Hash，哈希冲突，哈希聚集，BloomFilter，分布式一致性hash

顺序访问的数据结构

有序数组
平衡二叉搜索树：AVL树 红黑树
平衡多路搜索树：B-树、B+树
多层级有序链表：跳表

hash函数

这里是引用

冲突

不同的Key有相同的hash值产生冲突

hash聚集

频繁访问几个特定的hash值产生hash聚集现象

• 寻址方法

链表法
开放寻址法

布隆过滤器

• 概率型数据结构 ： 可能存在，一定不存在

存在误差

• 不支持删除操作

使用一个存储删除的布隆过滤器来实现删除功能

• 占用空间小

• 控制误差

预期布隆过滤器中可能存储的元素
假阻率

Hash函数的选择

https://hur.st/bloomfilter ： 选择合适的值
31随机分布性比较好
siphash Redis 6.0中使用，rust
murmurhash murmurhash2 cituhash
用两个Hash函数构造k个Hash函数

• 缓存穿透

原因：访问大量不存在的数据导致大量请求发送到mysql导致瘫痪
解决方案：见Redis

hyperloglog – Redis

见Redis

分布式一致性Hash

• 背景

顺时针依次访问不同的服务器

• 虚拟节点

解决分布和访问不均匀
通过计算Hash实现访问新增服务器