常见的哈希函数
SHA-384
SHA-224
SHA-256
MD2
SHA
SHA-512
MD5
哈希函数作用和特征
可以把数据根据不同的值，集合几乎均匀的分开
1、 输入域无穷大，输出域相对有限；
2、 相同的输入，一定导致相同的输出，没有随机成分；
3、 有可能不同的输入，有相同的输出；
4、 大量的相似的不同输入，输出在输出域上离散分布，对输出结果取模，取模完以后也是均匀分布的；
哈希表的设计
存储：
1、 有一个初始化的桶区域，假如长度17；
2、 桶区域中每个桶都是一个单链表；
3、 接收一个输入作为key，根据key算出一个hash值，然后对hash值取模hash%17，假设得出的结果是5，那么就把键值对挂到5号桶；
4、 如果桶中已经有其他记录，就顺着链表往下挂；
查找：
1、 输入作为key，相同的hash运算，得出hash值，然后对hash值取得出桶区域中的位置；
2、 遍历链表，比较链表中键值对的key与输入的key是否相等，相等则代表找到记录；
扩容： 如果链表到达一定的长度，比如7，那么其他链表也很有可能达到7了（均匀分布），如果某个key到来，发现某个桶长度达到7了，把桶区域扩容一倍大，里面的每个数据都重新算hash值取模确定新的位置。
增删改查的时间复杂度为O(1)
布隆过滤器
常用于解决类似于黑名单，比如一些黑名单url，每次出现一个url查一下，看是否在黑名单里面的。
这个可以通过hash表来存，但是如果url非常多，这个hash表会非常大，非常浪费空间。
这时候可以使用布隆过滤器，与hash表一样，也可以用于解决类似于黑名单的问题，但是有一定的失误率，这个失误是指不在黑名单中的但是可能会误报，但是如果在黑名单里的，一定不会误报不存在。
位图： 一个bit数组，可以用整形来拼，比如一个长度为10的int数组，从0~9位置，每个位置有32bit，所以就相当于一个长度为320的bit数组
布隆过滤器 = 位图 + hash函数
实现细节：
1、 准备一个长度为n的位图；
2、 准备几个hash函数，例如3个；
3、 当一个str到来时，每个hash函数算出hash值，然后模上n，在位图上对应的点设置为1；
4、 当根据一个str查询时，也是每个hash函数算出hash值，然后模上n，如果一个str加入过的话，算出的每个位置上都是1；
位图长度n越大，失误率越低
hash函数少，会因为采样不足而导致失误率上升，如果hash函数过多，会因为空间迅速耗尽导致失误率上升
如果需要13个hash函数，怎么去找13个hash函数：
只要找2个hash函数
第一个：1 * hashFn1() + hashFn2()
第二个：2 * hashFn1() + hashFn2()
第三个：3 * hashFn1() + hashFn2()
…
一致性哈希
分布式存储最常见的结构
一致性哈希的两个重要设计：
1、 哈希环；
2、 虚拟节点；
常见的存储服务集群，确定一个数据存入到哪个服务器，是通过hash函数算出的。
这方式的问题就是如果后面要增加服务器，比如原来是3台，现在增加到4台，那么原来是hash % 3，现在是hash % 4，所有的数据都要重新计算决定归属，大量的数据迁移。
实现细节：
1、 把hash函数的返回值，想象成一个环；
2、 假设一开始有3台机器，取一个不同的特征值比如机器ip，通过hash函数算出ip值在环中的一个位置（一致性hash不需要取模）；
3、 如果增加一台机器，也是同样的计算方式确定环上的位置，把顺时针往下的第一个节点上的一部分数据迁移到新节点，迁移的数据是逆时针的上一个节点到新节点的这一段；
4、 如果下线一台机器，把下线机器的数据迁移到顺时针的下一个节点；
数据分布不均匀：
但是此时会有可能机器在环上不均分，这时候会出现数据不均分（数据倾斜），即使一开始时是均分的，也会因为增删机器导致不均分
不均匀的解决办法：虚拟节点技术
虚拟节点技术：
1、 给不同的机器分配多个不同的虚拟节点（比如虚拟的ip），每个机器之间的虚拟节点个数相同；
2、 现在不是把真实机器ip映射到环中，而是把虚拟节点映射到环中；
3、 数据打到虚拟节点上，根据虚拟节点映射到真实机器，此时3台机器的数据就保证是均匀的；
4、 如果增加一台机器，也是给它分配相同个数的虚拟节点，把虚拟节点映射到环中，然后进行数据迁移，最后数据还是均匀分布的；
有了虚拟节点技术，就可以根据机器的性能，给它们分配不同数量的虚拟节点技术，使得性能高的机器负载较高，性能差的机器负载相对较低。