1. 哈希函数
1.1 定义
out = H(in) ，如果函数H满足以下特征：
- in -> ∞，输入域是无穷的，eg: 可以接受任意长度的字符串
- out -> s, 输出域是有限的，eg: 输出为64的字符
- 相同的输入，一定返回相同的输出值，没有任何随机的成分
- 即便是不同的输入，输出可能会相同（hash碰撞）
- 要保证：均匀行 & 离散性，eg: 在指定域，填入了不同的输入后，得到的输出整体是均匀离散的分布在整个域内的
那么我们称函数H就是hash函数。
1.2 常见的hash函数
- md5
- sha1
1.3 解决hash冲突的方式
1.3.1 开放定址法
当散列表中未满时，处理冲突需要的“下一个”空位置在该散列表中解决，即当发生冲突时，按照如下的方法求得后续散列地址。
Di = (H(k) + di) MOD m, 其中di未地址增量
- di = 1，2，3...m-1 称为线性探测在散列
- di = 1^2，-1^2，2^2，-2^2... n^2,(n<=m/2), 称为二次再探测再散列
- di = 伪随机数序列，成为伪随机探测再散列
特点：
- 线性探测再散列是一种简单好用的处理冲突的方案，只要散列表足够大，总能找到一个空闲的位置存放元素，但这种方案容易造成元素的“聚集”，即出现散列地址不同的元素争夺同一后续散列地址，因为这被争夺了后续地址，原本应该在这位置的数据进入后，由于冲突会去占用下一个位置，导致任何元素都需要经过多次探测才能解决冲突，从而大大增加了查找下一个空闲位置的路径长度。
- 线性探测再散列只能对散列表进行逻辑删除，而不是物理删除，以免在删除某个记录以后找不到比它晚插入的、并与其发生过地址冲突的其他记录，使得看起来很满的散列表实际上存在很多空的位置
- 二次探测虽然能很好的解决“聚集”现象，但还是不能够探查到散列表中的所有位置
1.3.2 再散列法
在发生冲突时，用不同的散列函数再求得新的散列地址，直到不发生冲突时为止，即 Di = Hi(k), i = 1,2...n，Di代表不同的hash函数
特点：
- 不易发生冲突
- 增加了计算时间，且需要构建多个hash数
1.3.3 链地址法
也叫拉链法，即把具有相同散列地址的元素用一个线性链表连接在一起。
特点：
- 需要额外的空间开销
- 方便删除
1.3.4 建立公共溢出区
1.4 应用
1.4.1 布隆过滤器
1.4.2 大数据处理
题目1: 一个中文件中保存着40亿个无符号整数（0-2的32次方-1），使用指定内存，返回出现的次数最多的数据，eg:1G内存
思路：根据hash将大文件中数 分到 不同的小文件中，然后使用指定的内存，挨个处理小文件，并记录出现次数最多的数。
题目2: 设计randomPool，设计一种结构，满足以下：
1.insert(key) 将key加入结构，但不能重复加入
2.delete(key)
3.getRandom() 等概率随机返回一个key
思路：真、反2张HashMap表，map1记录（key -> index）,map2记录（index -> key）,删除时，要拿最后index的数据来添删除的洞，并更新最新size。
3. 一致性hash
主要使用场景：分布式数据库，即
- 当数据成为海量之后，这些海量的数据需要按照一定规则划分到不同机器上
- hash key的选择要合理，数据划分才合理，例如需要根据userId去进行hash % m, （其中m为集群机器的数量）划分，而不是 男女、状态 这种维度去进行
- 当数据机器要扩容或者缩容，如果使用经典hash去模的，那么需要对全部的数据进行重新划分，否则会出现查询不到数据的情况，全部迁移数据的代价太了。
这时：一致性hash登场了
3.1 hash环
- 一致性hash不在对机器的数量进行hash去模，而是对一个固定的值进行hash去模，例如2^32-1
- 一致哈希算法是对 2^32 进行取模运算的结果值组织成一个圆环，成为hash环
一致性hash要进行2步hash操作：
- 对存储数据的机器进行hash，一般是根据ip进行hash映射到环上
- 当一个数据进行存储和查询时，对数据进行hash映射
所以：一致性哈希是指将「存储节点」和「数据」都映射到一个首尾相连的hash环上。
3.2 操作
当需要对指定key的值进行读写的时候，要通过下面2步进行寻址：
- 对 key 进行哈希计算，确定此 key 在环上的位置；
- 从这个位置沿着顺时针方向走，遇到的第一节点就是存储 key 的节点。
实现：
1. 将所有机器节点的hash后的位置，存在一个数组中，eg：A机器的index为10000，B机器index位置为20000，C机器的位置为0，那么arr=[0,10000,20000]
2. key1数据hash后的index为500，那么key1就在A上。
以上逻辑，通过代码很容易实现。
增加和删除机器节点后，仅影响该节点在哈希环上顺时针相邻的后继节点，其它数据也不会受到影响。
例如：当A节点删除后，0-1000上的数据就归B管了，仅需要迁移这部分数据即可
但是这样并不保证节点能够在哈希环上分布均匀，这样就会带来一个问题，可能会有大量的请求集中在一个节点上
3.3 hash环的问题
- 当机器数量很少的时候，环上数据如何均分
- 增加和减少机器时，如何保证数据均衡分布
为了解决这2个问题，就需要有大量的节点，节点数越多，哈希环上的节点分布的就越均匀，增加和删除时影响越小，但现实中机器节点的数量时有限制的，那么就引出了虚拟节点技术。
3.4 虚拟节点技术
不再将真实节点映射到哈希环上，而是将虚拟节点映射到哈希环上，并将虚拟节点映射到实际节点，数据 -> 虚拟节点 -> 机器节点的链路，多了一层映射关系。
例如：
A节点对应的虚拟节点有10个，(A0,A1...A9)
B节点对应的虚拟节点有10个，(B0,B1...B9)
C节点对应的虚拟节点有10个，(C0,C1...C9)
3.4.1 特点
将这些虚拟节点通过hash函数映射到hash环上，根据上面hash的特性第5点可知，当数量多时，这些节点的位置时均匀且离散的分布在hash环上，任意取一段中A和B和C的虚拟节点数量都是一样的。
虚拟节点技术个特点如下：
- 每台机器包含多个虚拟节点
- 让虚拟节点取抢占环
- 虚拟节点均匀且离散的分布在环上
3.4.2 操作
数据读写时，需要走2层映射关系：
- 数据key找到hash环上的位置，顺时针找到虚拟节点
- 根据虚拟节点和机器节点的映射关系，找到真实机器节点
- 操作读写
增加和删除机器节点后：
- 对应该节点的多个虚拟节点均会移除
- 由于这些节点时均匀且离散的分布在环上，所以会将自己负责的数据迁移到顺时针下一个节点
通过代码我们很容易写出一个数据迁移的通用方法：
def trans_data(node1, node2):
node1.data -> node2.data
3.4.3 管理节点
通过虚拟节点技术，还可以
- 硬件配置更好的节点增加权重，比如对权重更高的节点增加更多的虚拟机节点即可
- 后端管理页面手动管理节点负载
