Out F(in)
    1)in→∞ out→S MD5=0~2^64-1 16进制16长度表示16^16 2^4X16 2^64
    2)相同的输入返回相同的输出值 same in → same out，不含有随机
    3)不同的输入可能会有相同的输出，因为输出是有穷的。 not same in→same out 哈希碰撞
    4)均匀的离散到域中。均匀性、离散性。位运算机制来控制。
    out值%m，也在0~m-1均匀发布

    1、40亿个无符号整数，只有1G内存，统计每个数出现多少次数。 无符号整数0~2^32-1，0~42亿个。
    经典做法HashMap不行，因为key,value 一共八个字节，最坏情况每个数都不一样，40亿乘以8B=320亿B=320GB
    使用hash函数,out出来的数再%，划分大类，再用HashMap统计出现次数

    2、哈希表的实现
    放数：”a”:123,一开始17空间，先hash函数out再%17，放多了会增加常数时间，扩容%34,扩容一半，链依次减少一半。
    扩容是O(logN) 重新挂O(N),总的扩容代价O(logN)O(N)。平均扩容代价O(NLogN)/N=O(logN)
    在使用的时候可以认为是O(1)的，理论是O(logN)
    优化：JVM等语言可以离线扩容，不占用用户线上时间。java把挂着的单链表改成了有序树。开放地址法。

    1、设计RandomPool结构
    insert(key):将某个key加入到该结构，做到不重复加入。
    delete(key):将原本在结构中的某个key移除。
    getRandom():等概率随机返回结构中的任何一个key。
    要求都是O(1)
    准备两个Map str→index index→str int size=0,保持连续。

    2、布隆过滤器,只有设置查询，没有删除，允许一定失误率
    放100亿黑名单url,每个url占内存64B,使用HashSet,6400亿需要640G内存。
    布隆过滤器处理：会有失误，白名单认为成黑名单，如果数据量很大但bit位图很小。可以设计的很低，比如万分之一。
    不会出现黑→白因为进来数组描黑，不会白。
    根据数量N，失误率P，来决定bit位图。根据数据量N，bit位图，来决定K hash个数
    n=样本量 p=失误率
    问题中有类似黑名单：1、set 2、允许失误 3、与单样本大小无关，只要哈希函数能接受就行。
    公式算出来的都要向上去整。

    3、哈希一致性哈希原理
    “左”:33 经过hash out % 3决定是去一号数据库，二号数据库，三号数据库。均匀分配。
    HashKey选择要有区分性，会有高频 中频 低频即使很多也均匀分配。负载均衡。
    比如国家名就没有区分性，中国美国就很多,只有一号、二号机器有，三号机器没有。
    如果要进行扩容，变成四台机器，那就要重新%,%4。迁移是全量的。

    host1 host2 host3 经过hash out 1亿 2亿 3亿。成为环状。
    “左”:33 经过hash out值为2.5亿 离顺时针最近的机器。
    实现：把三个机器的hash值排序存在每个机器上。做二分找到>=2.5亿最左的位置，发现自己属于host3。
    找不到属于自己的就会转回来，属于host1。
    这样扩容加上host4，代价就会很小，因为只是一段环改变了。减少机器也一样。
    但是存在两个问题。问题一：机器数量很小的时候，环可能一上来做不到均分，因为hash函数是点多起来之后均分，而不是换上打三个点就均分。
    问题二：加上或减少机器，做不到立马负载均衡。
    虚拟节点技术：m1分给一千字符串，m2也分配，m3也分配。虚拟节点去抢环。让里面值hash去强点。
    初始加机器减机器很容易，因为按比例抢环很均衡，虚拟节点之间给数据，夺数据很容易。还可以管理负载，谁强谁就多分配，谁弱谁就少分配。