"""
hash函数(散列函数)的性质：
1.典型的哈希函数的输入域是无限的 输出域是有限的S集合
2.给同一个哈希函数传入同样的值得到的结果是相同的
3.同一个哈希函数输入不同的值时 返回值可能相同
4.很多不同的输入得到的输出值均匀分布在S集合中

1个hash函数得到n个hash函数的方法：
将这个hash函数得到的结果分为两半h1 h2
那么h1+1*h2与h1+2*h2即为相互独立的新的hash结果 以此类推

布隆过滤器：
假设有一个长度为m的bit类型的数组 即数组中每个位置都为bit类型(只有0/1)
有k个hash函数 当有一个数据想进入布隆过滤器时 用这个数据经过k个hash函数
得到的结果值对应在m数组上的位置涂黑(从0变为1) 那么有n个位置都被涂黑了
如果遇到同一个位置需要被涂黑那么让它保持被涂黑
这样当所有数据都经过同样的处理之后 想判断一个新的数据是否进入过布隆过滤器
让这个数据经过k个hash函数后进行比对即可

布隆过滤器要求：
m = n * lnP / (ln2)^2
其中m为数组长度 n为样本量 P为预期失误率 需要的空间大小为m/8单位byte
k = ln2 * m / n
其中k为需要的hash函数个数 结果向上取整
p = (1 - e^(-n * k / m))^k
由于存在向上取整 因此p为真实失误率


一致性哈希：

经典服务器结构：
前端接受到请求后 用同一个哈希函数得到的值模服务器数 得到的结果即为将信息存在哪一台机器上
经典结构存在的问题在于加或者减机器的时候必须全部计算再考虑迁移

一致性哈希结构：
假设hash函数得到的结果为0~2^64 并形成一个环 即2^64下一个为0
然后将机器的唯一标识如mac地址或ip经过该hash函数得到一个值 然后将该机器放在对应值的位置上
那么假设有三台机器m1 m2 m3  经过hash均匀的按顺时针分布在0~2^64位置上
此时有一个新的值想要加入机器 那么让这个值经过该hash得到一个范围内的hash值
然后找到顺时针方向离这个值最近的机器即可 换句话说每台机器负责的范围为从该机器开始逆时针方向直到下一个机器的前一个位置

一致性哈希实际实现：
假设有三台机器m1 m2 m3  将这三台机器ip地址经过hash函数得到的值存入数组 假设为[m1, m3, m2]
将该数组放入前端每一个前端服务器当中
此时如果有新的数据想加入机器 那么将新的数据经过hash算出来的结果通过二分法找到小于等于且离得最近的机器ip哈希结果对应的机器

数据迁移：
假设现在三台机器形成的环的顺序为[m1, m3, m2]
此时有一台m4机器想加入 假设排序完的结果为[m1, m3, m4, m2]
那么只需要将原先m2机器上的数据m2到m3属于m4到m3范围内的数据交给m4即可
如果想要撤出m4 那么也只需要将m4机器上的数据交给顺时针离得最近的机器m2即可

解决加入或减少机器负载不均匀的问题：
不论机器数量的多少 假设加入或减少前机器是平均分布的 那么再加入或减少之后均匀性一定会被打破 此时需要引入虚拟节点技术

虚拟节点技术原理：
准备一个路由表 仍假设有三台机器 每台机器分配1k个虚拟节点 由这些虚拟节点来抢资源范围
呈现在环上的是这些虚拟节点 需要找机器的时候只需要查路由表即可得到原始机器编号
新增机器的时候新机器通过分配新的虚拟节点来分配其他机器上的资源
"""

