⼀致性Hash算法（部分比较）

Hash算法，⽐如说在安全加密领域MD5、SHA等加密算法，在数据存储和查找⽅⾯有Hash表等, 以上
都应⽤到了Hash算法。

顺序查找法

遍历，一个个比对

for(int element: list) {
if(element == n) {
如果相等，说明n存在于数据集中
}
|

这种⽅式我们是通过循环来完成，⽐较原始，效率也不⾼

⼆分查找

排序之后折半查找，相对于顺序查找法会提⾼⼀些效率

直接寻址法

image.png

定义⼀个数组，数组⻓度⼤于等于数据集⻓度，此处⻓度为9，数据1就存储在下标为1的位置，3就存储
在下标为3的元素位置，，，依次类推。
这个时候，我想看下5存在与否，只需要判断list.get(5) array[5] 是否为空，如果为空，代表5不存在于
数据集，如果不为空代表5在数据集当中，通过⼀次查找就达到了⽬的，时间复杂度为O(1)。
直接把数据和数组的下标绑定到⼀起，查找的时候，直接array[n]就取出
了数据
优点：速度快，⼀次查找得到结果
缺点：
1）浪费空间，⽐如 1,5,7,6,3,4,8,12306 ，最⼤值12306 ，按照上述⽅式需要定义⼀个⽐如⻓度为
12307的数组，但是只存储零星的⼏个数据，其他位置空间都浪费着
2）数据如：1,5,7,6,3,4,8,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2最⼤值12，⽐如开辟13个空间，存储
不了这么多内容

继续优化

除留余数法

image.png

上⾯对数据求模 （数据%空间位置数）

image.png

开放寻址法：

1放进去了，6再来的时候，向前或者向后找空闲位置存放，不好的地⽅，如果数组⻓度定
义好了⽐如10，⻓度不能扩展，来了11个数据，不管Hash冲突不冲突，肯定存不下这么多数据

拉链法：

image.png

算好Hash值，在数组元素存储位置放了⼀个链表，如果Hash算法设计的⽐较好的话，那么查询效率会更接近于O(1)，如果Hash算法设计的⽐较low，那么查询效率就会很低了