0.哈希表的几个性质
（1）输入无穷，输出有穷
（2）输入一样，输出一定一样。（in same, out same）
（3）对于很多的输入域，对应输出域均匀分布
1.哈希表经典结构
每个桶里面是单链表。
2.JVM哈希表
每个桶里面是红黑树结构
3.leetcode380
设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。
insert(val)：当元素 val 不存在时，向集合中插入该项。
remove(val)：元素 val 存在时，从集合中移除该项。
getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。
4.布隆过滤器（https://www.bilibili.com/video/av83727135?p=7）
在搜索相关的公司基本都会问到。
用于查找某个场景是否在某个集合中。
本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少（把内存压得很小），但是缺点是其返回的结果是概率性的，而不是确切的。（失误率：如某个黑名单属于集合中的URL,则一定不会误报，不属于黑名单中的url可能会被误报。宁可错杀三千不可放过一个）共三个公式
p失误率
m位图大小
k哈希函数的个数
比特数组的大小，算出来之后再除以4得到字节。
哈希函数的个数确定：K个固定的哈希函数，k有个最优的个数，为上面第二个公式。
失误率为前两个m,k取整确定了以后再重新算失误率的实际数值。
k个哈希函数的设计，只需要两个哈希函数的种子就行了
hadoop中每个文件都是一个小的布隆过滤器，查找某个值在哪个文件中，先分别用布隆过滤器找
5。认识哈希一致性
数据服务器设计结构，数据均分，负载均衡
数据分布查询的hotkey问题，让key有一定的量。
（一致性哈希面试很频繁。。）
数据迁移代价？负载均衡？经典设计模式是加一台机器，所有的数据都要重新取模计算，这时候要用到一致性哈希
虚拟节点技术。
按比例抢环，虚拟节点越多，功能越强大
负载管理也是均衡的
一致性哈希：所有需要集群化的、抗压的、分布式内存都需要用到一致性哈希
京公网安备 11010502036488号