-
Notifications
You must be signed in to change notification settings - Fork 0
/
HashAlgorithm.java
52 lines (51 loc) · 3.72 KB
/
HashAlgorithm.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
package 海量数据;
/**
* 哈希算法(散列算法)特征:
* 1. 正向快速: 给定明文和哈希算法, 在有限的时间和资源内计算出hash值.
* 2. 逆向困难: 给定Hash值, 在有限时间内很难(基本不可能)逆推出铭文.
* 3. 输入敏感: 原始输入信息修改一点信息, 产生的Hash值看起来应该大不相同.
* > MD5("version1") = "966634ebf2fc135707d6753692bf4b1e";
* > MD5("version2") = "2e0e95285f08a07dea17e7ee111b21c8";
* 4. 冲突避免: 很难找到两段内容不同的明文,使得它们的 hash 值一致(发生冲突)。
* 即对于任意两个不同的数据块,其hash值相同的可能性极小;对于一个给定的数据块,找到和它hash值相同的数据块极为困难。
*
* > 总结: 相同输入相同输出, 不同输入均匀分布(离散性); 输入域几乎无穷大, 输出域有限.
*
* -------------
* 用途:
*
* 数据结构领域: 对速度要求较高, 对碰撞要求较低, 只要保证Hash均匀分布就可以. 比如HashMap, 得出Hash值对Hash的性能有极高的影响.
* 安全领域:
* 1. 用于对文件/信息的完整性进行校验, 将任意文件转换为小的数字(指纹), 这样通过比较指纹就可以保证文件的唯一性. 这个指纹
* 标志与文件里的每一个字节都相关, 而且很难找到逆向规律. 比如Git用SHA1散列函数来检查文件更新.
* 2. 给证书、文档、密码等高安全系数的内容添加加密保护。这一方面的用途主要是得益于散列算法的不可逆性,这种不可逆性体现在,
* 你不仅不可能根据一段通过散列算法得到的指纹来获得原有的文件,也不可能简单地创造一个文件并让它的指纹与一段目标指纹相一致。
*
* ------------
* 大数据领域的用途:
* 假设有N个缓存服务器, 如何将一个对象Cache映射到N个机器上.
*
* 1. 哈希取余, 通过计算Cache的hash值, 由于hash均匀分布, 所以可以使用`hash(Cache) % N`来将Obj均匀的映射到N个机器上.
*
* 但是, 假设这时候一个机器Down了, 或者要新增一台机器, Obj的位置将变为`hash(Cache) % (N-1)`或者`hash(Cache) % (N+1), 所有的
* 缓存位置都将发生变化, 即几乎所有的缓存都会失效.
* 所以有了以下这个方法, 一致性哈希算法(Consistent hashing).
*
* 2. 一致性哈希, 通过一致性哈希环(将0-(2^32-1)的数值作为一个Hash环), 尽可能小的改变已存在Key的映射关系(即尽可能避免因新增/减少节点而导致的之前映射关系失效问题).
* 不再通过`哈希取余`的方式来决定Cache的位置, 而是将每个机器的Hash值(比如hash(ip))放在一个圆环上, 根据Cache的Hash值来顺时针寻找下一个
* 最近的机器节点, 这个机器节点就是它所在的位置. 这样在增加或减少机器的时候, 只会有一部分的数据会失效.
*
* 但是一致性Hash算法会使得缓存的分布极不均匀, 因为各个机器的Hash值并不能将圆环换分为区域大小相同的环.
*
* 3. 带有虚拟节点的一致性哈希
* 通过添加虚拟节点, 使得各个机器划分的圆环区域尽量均匀.
*
* ----
* Redis采取方法1, 将Hash值按1024取模, 将这个值作为槽(Slot), 但是Slot并不会固定在某个机器, 而是将这个值手动的分配个某个机器.
* 这样在新增或减少机器的时候, 只要机器分配的槽范围不变, 那么这段范围内的缓存就不会失效.(槽是Redis集群扩容和伸缩的基本单位)
* 如果使用一致性哈希算法,那么当减少机器的时候,这个机器的数据就一定要向某个机器迁移,而不是随意某个机器.
*
*
*/
public class HashAlgorithm {
}