Hash，布隆过滤器，hyperloglog

平衡二叉树

增删改查时间复杂度为 O(log n)；

平衡的目的是增删改后，保证下次搜索能稳定排除一半的数据；

O(log n)的直观理解：100万个节点，最多比较 20 次；10 亿个节点，最多比较 30 次；

通过比较保证有序，通过每次排除一半的元素达到快速索引的目的.

Hash表(散列表)

哈希表（Hash Table，也叫散列表）是一种基于键（key）进行快速数据存取的数据结构。它通过一个哈希函数（Hash Function）将给定的键映射到数组（哈希桶）中的某个位置（称为索引或哈希值），从而实现对数据的增、删、改、查操作。理想情况下，这些操作的平均时间复杂度可以达到O(1)，最坏位O(n)。

装填因子

哈希函数：将任意大小的键（如字符串、对象）转换为固定范围的整数索引。

murmurhash1，murmurhash2，murmurhash3，*siphash
（ redis6.0 中使用，rust 等多数语言用此实现 hashmap），cityhash 都具备强随机分布性；

哈希函数：除留余数法：

哈希桶（Buckets）：通常是一个数组，用于存储数据。哈希函数计算出的索引决定了数据应放入数组的哪个位置（即哪个桶）。

冲突解决机制：由于哈希函数的输出空间是有限的，而输入可能是无限的，因此不同的键可能会被映射到同一个索引，这种情况称为“哈希冲突”。常见的解决方法有：

链地址法：在每个数组位置（桶）上维护一个链表（或树结构）。当发生冲突时，将新元素添加到对应索引的链表中。如果冲突链表过长，这个时候可以将这个链表转换为红黑树、最小堆。由原来链表时间复杂度O(n) 转换为红黑树时间复杂度O(log n) ；

开放地址法：当发生冲突时，按照某种探测方法（如线性探测、二次探测、双重哈希）在数组中寻找下一个可用的空位置。

线性探测法：冲突后依次检测下一个位置，直到遇到空闲位置。表尾的下一个元素是表头。删除元素时，需要在这个位置作特殊标记，后续还可以增加新元素。

平方探测法：

布隆过滤器

位图（BIT 数组）+ n 个 hash 函数

只负责判断存不存在。

不存储具体的元素。

不能删除元素。

有一定的误差,但误差可控。

概率型过滤器，与哈希表协同工作，共同处理海量数据。

在查找某个元素是否存在时，只要出现0就一定不存在；如果全为1，不能确定存不存在。

当一个元素加入位图时，通过 k 个 hash 函数将这个元素映射到位图的 k 个点，并把它们置为 1；当检索时，再通过 k 个 hash函数运算检测位图的 k 个点是否都为 1；如果有不为 1 的点，那么认为该 key 不存在；如果全部为 1，则可能存在。

n -- 预期布隆过滤器中元素的个数，如上图 只有str1和str2 两个元素 那么 n=2 p -- 假阳率，在0-1之间 0.0000001 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));

通过n和p计算m和k的数值。

缺点：占用内存依然很高，十亿个数据占用内存37G，一百万个数据占用内存377M。

常见处理场景：① 缓存穿透的解决；② 热 key 限流

hyperloglog

概率型数据结构。

估算集合中不重复元素的数量。

最大元素数量2^64，固定占用内存12KB左右。

误差是固定值0.8125%。

给定一系列随机整数N，记录低位连续零位的最大长度k，随机整数数量N和最大长度k的数学关系，大致满足N=2^k。

所以通过k可以近似估算出基数N，这个N就是全部数据去重后的数量。

又因为一次估算就确定N，误差太大。

于是引入了桶的概念，计算m个桶的加权平均值，这样就得到比较准确的答案了（实际上还要进行其他修正）。最终的公式如图

m：桶的数量。const：修正常数，它的取值会根据m而变化。

DV_HLL：去重后的元素数量。Rj： 第 j 个桶记录的最大 ρ 值

对于一个输入的字符串，首先得到64位的hash值，用前14位来定位桶的位置（共有 ，即16384个桶）。后面50位即为伯努利过程，每个桶有6bit，记录第一次出现1的位置count，如果count>oldcount，就用count替换oldcount。

一共有个M数据，真实去重后的数据是N。

对这M个数据，每个数据经过hash函数都生成一个64位的hash值。前14位用来定位桶的位置，即作为桶的索引，最大为16384。后50位统计低位最长连续零。因为桶只有16384个，所以一定会有冲突，有冲突的话，索引对应的数值里就存放 长度更长的低位最长连续零 的数值。

最后使用上面的公式计算得出一个近似N的数值。

因为后50位最长连续0为50，用二进制存放，只需要6bit，2^6=64。

一共2^14=16384个桶，每个桶里的数值只需要为6bit的空间。

16384*6bit/8约等于12Kb。

hash表：真正的存储用的数据结构。

布隆过滤器：判断元素存不存在。

hypweloglog：估算去重后的基数。

，2^6=64。

一共2^14=16384个桶，每个桶里的数值只需要为6bit的空间。

16384*6bit/8约等于12Kb。

hash表：真正的存储用的数据结构。

布隆过滤器：判断元素存不存在。

hypweloglog：估算去重后的基数。

参考：https://zhuanlan.zhihu.com/p/58519480
https://www.bilibili.com/video/BV13NwveLE1D?spm_id_from=333.788.videopod.sections&vd_source=045b53bf85e6101c062282f4ccb5d69b