哈希算法

将任意长度的二进制值串映射为固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制值串就是哈希值

hash算法一般需要满足的几点要求:

1.从哈希值不能反向推导出原始数据(所以哈希算法也叫单向哈希算法)

2.对输入数据非常敏感,哪怕原始数据只修改了一个 Bit,最后得到的哈希值也大不相同;

3.散列冲突的概率要很小,对于不同的原始数据,哈希值相同的概率非常小

4.哈希算法的执行效率要尽量高效,针对较长的文本,也能快速地计算出哈希值。

常用的哈希算法有 MD5(MD5 Message-Digest Algorithm,MD5 消息摘要算法) 和 SHA(Secure Hash Algorithm,安全散列算法),一些重要的数据推荐使用sha,md5已经不太安全

哈希算法的应用:

保护数据

比如不保存用户的明文密码,而是保存用户密码的hash值

散列函数

散列表实现的一部分,用来确定数组下标

唯一标识

比如把一台计算机的硬盘,显卡,cpu等序列号全部放在一起计算出哈希值作为该机器的唯一标识

数据校验

当我们在网上下载一个大文件时,为了确保该下载的文件是否完整,可以计算hash值跟网站上的hash值进行对比

其他的还有负载均衡分布式存储等,都是上面的这些应用的扩展


一致性哈希算法

在分布式中,假设我们有10台机器,那么我们一般会将需要保存的数据的标识码进行hash计算并跟 10 求余,然后得到的数字即为第几台机器,但是当我们新增一台机器或者减少机器时,整个就乱了

一致性哈希算法就是用来解决该问题的。

算法步骤:

简单来说,一致性哈希将整个哈希值空间组织成一个虚拟的圆环,如假设某哈希函数H的值空间为0-2^32-1(即哈希值是一个32位无符号整形)

我们假设现在有4台机器,A B C D 计算hash后分别落在了下图位置


假设要存储的数据 M1 M2 M3 M4 计算hash后落在了下图位置


我们通过顺时针法则,就可以得出,M1存储到A机器,M2 M4 存储到B机器,M3存储到D机器

此时,假设B机器宕机了,那么不用怕,只需要将 M2和M4迁移到C机器即可


此时,我们假设新增一台服务器E,那么,只需要处理A-E之间的数据即可


总结:

在一致性哈希算法中,如果一台服务器不可用,则受影响的数据仅仅是此服务器到其环空间中前一台服务器(即沿着逆时针方向行走遇到的第一台服务器)之间数据,其它不会受到影响

如果增加一台服务器,则受影响的数据仅仅是新服务器到其环空间中前一台服务器(即沿着逆时针方向行走遇到的第一台服务器)之间数据,其它数据也不会受到影响



上一篇: 返回不重复的整数
下一篇: 朴素贝叶斯算法
作者邮箱: 203328517@qq.com