hash function hash函数
通过计算得到一个数据的hash值的函数
md5、sha1……好像都是对一个数据反复进行了大量的二进制运算，比如：或、与……，具体实现看源码
Features:
- （在使用同一个hash function的前提下）相同的输入有相同的输出，不同输入均匀分布（但是不同的输入也可能计算出的hash值是一样的，因为输入域是无限的 输出域是固定数量（16位的16进制）、固定数据的）
- hash function计算得出的hash值长度固定
- hash函数与输入的顺序无关，会均匀分布，比如：有一个s域 0~99 经过hash函数计算后又 % array的size，就会在这个array数组上均匀分布
- 一个域均匀分布，那么它取模（%）后还是均匀分布的
散列分布是评判一个hash function优劣的标准，也就是说使用hash function计算出的数组下标位置是会做到均匀分布的，
但是散列分布和数组容量大小有关，随着底层结构 数组 的可使用容量的减少，会增大发生hash冲突的概率，所以需要使用负载因子来判断何时需要resize数组的容量
hash扩容 resize：
每次扩容都会是现在容量大小的2倍，那么如果扩容到N的大小，那么时间复杂度就是logN，但是扩容后还需要对原来的数据进行重新rehash，每次扩容的时间复杂度应该就是N了，那么多次扩容的总时间复杂度就是N * logN
resize还可以后台操作，不占用主线程的时间
hash函数在大数据领域经常使用
布隆过滤器 Bloom Filter
作用：
解决一个数值是否存在某个范围内，如果使用hashMap会造成很大的内存占用。
比如：不安全网页的黑名单包含100亿个黑名单网页，每个网页的URL最多占用64字节。现在想要实现一种网页过滤系统，可以根据网页的URL判断该网站是否在黑名单上，请设计该系统。要求该系统允许有万分之一以下的判断失误率，并且使用的额外空间不要超过30G。
这个问题如果使用hashMap来存储黑名单，有100亿个URL，每个URL最多占用64字节，就是640G的内存空间，所以Bloom Filter就登场了。
Bloom Filter使用的是一个bitMap，即bit数组，每一个bit都代表了一数据，所以数据的单位就从原来的byte字节缩减到了bit
原理：
一个数据通过一系列的hash function，得到多个hash值，对这多个hash值进行计算，计算得到bitmap中的某个下标位置，然后将该下标的元素置为1。
如果在之后的计算中计算出的下标位置已经为1，再继续置为1。
如果在之后查询中，对一个数据使用k个hash function计算，计算得出的k个下标中有1个下标不是1，那么这个数据不在Bloom Filter中，如果全为1，才在。因为如果一个数据在Bloom Filter中，它计算出的下标应该全为1才对。
计算逻辑：
使用计算出的hash值进行%取余计算得到bitmap中的下标位置
（一般使用hash function对一个数据计算 计算得出数组下标，然后在数组中存储数据 或者 标记为1，但是Bloom Filter不是这样，
Bloom Filter使用了k个hash function，计算得出k个hash值，再对k个hash值进行计算得出数组下标 标记为1，这整个过程就代表这个数据进到Bloom Filter里来了。
所以bitmap就要很大，因为如果是100亿个数据，每个数据都要使用k个hash function计算得出k个下标，如果bitmap容量比100亿小，操作完后bitmap全1了 还查什么，这失误率不就100%了嘛。
所以也可以得出 可以通过调整hash function的个数 和 bitmap的容量 来得到失误率。
bitmap容量多大合适呢？bitmap容量与 失误率 和 hash function个数 有关）
公式：
Bloom Filter的大小m，失误率p，样本数量n，比如：样本数量100亿，失误率万分之一 即0.01%
根据公式计算出m=19.19n，向上取整为20n，即需要2000亿个bit，也就是25GB。
hash function个数k
因为我们在确定布隆过滤器大小的过程中选择了向上取整，所以还要用如下公式确定布隆过滤器真实的失误率为
根据这个公式算出真实的失误率为0.006%，这是比0.01%更低的失误率，哈希函数本身不占用什么空间，所以使用的空间就是bitMap的大小（即25GB），服务器的内存都可以达到这个级别，所有要求达标。
优点：
节省空间占用、查询效率也快
缺点：
有一定失误率、删除困难
失误率：因为hash function有不同的输入也会有相同输出的问题，所以会出现某个在黑名单中不存在的数据但是经过hash function计算后再计算出下标位置后发现该位置为1的情况
删除困难：某个数据不在名单中了，将bitmap中的下标位置置为0了，但是由于其他数据在这个下标位置置为1过，现在是0了，就会造成之后查询时，原本在黑名单中的这个下标的数据访问时，由于已经是0了，就代表不在黑名单中，所以这个数据就可以和正常数据一样任意访问了，产生数据不安全的问题
（与hashMap不同的是hashMap使用hash function计算出hash值后再计算出下标位置后会存储数据，所以发生hash碰撞后因为数据的不同不会失误的覆盖掉不同的数据，而Bloom Filter使用hash function计算出hash值后再计算出下标位置后会置为1，所以之后查询时，不同的数据使用hash function计算出hash值后再计算出下标位置后无法判断是否是相同的数据置为1的，所以就会发生误判，存在失误率）
使用场景：
- 在大数据量的场景下 比如：上亿数据，计算某个数据是否存在
- 缓存穿透
问：
为什么使用多个hash function？是为了使用多个结果来证明某个数据存在吗？还是其他别的原因？
一个数据使用多个hash function后，计算出来的hash值不一样吗？
多个hash函数的逻辑是不同的，比如：虽然是相同的输入必会有相同的输出，但也只是在使用同一种hash function的前提下，如果对同一个数据分别使用md5、sha1计算出的hash值就是不一样的。
tips： Bloom Filter因为使用hash function，而且不像hashMap一样存储了数据，只是将制定位置置为了1，所以会因为hash冲突有失误率，在建模时，就需要根据想要达到的失误率来定义bitmap的大小、hash function的个数。
可供使用的第三方：
guava
redis（需要自己创建bitmap、定义bitmap的大小、hash function的个数、hash function的逻辑实现、手动标记bitmap中的下标位置）
hint：
单点登录CAS时，每个服务器请求统一认证服务器后，会在本地服务器上缓存cookie，因为如果每次请求都去请求统一认证服务器 对服务器有压力，这就和平时使用浏览器访问某个网站时一样，第一次请求服务器并缓存，第二次后就从缓存中获取