哈希算法
将任意长度的二进制值串映射为固定长度的二进制值串
笔记:
哈希算法能将任何数据映射为 固定长度ID,
几乎可保证 同一数据 同一ID,不同数据 不同ID 的特性
相当于数据自带了一串具有辨识度的唯一ID,
通过这个 ID 能做很多事情
优秀的哈希算法要求
不能反向推到出数据(单向算法)
对输入数据非常敏感, 1Bit的修改 哈希值也大不同.
散列冲突概率小
执行效率 要高效 ,较长文本也要快速算出哈希值
哈希算法的应用
安全加密 唯一标识 数据校验 散列函数 负载均衡 数据分片 分布式储存
1.安全加密
MD5(消息摘要算法) SHA(安全散列算法) DES(数据加密标准) AES(高级加密标准)
哈希算法要求:
很难反向推导出原石数据 (目的:防止数据泄露)
散列冲突概率要小 (无法零冲突,因为抽屉原理)
越复杂越难破解的加密算法,计算时间也越长
2.唯一标识
利用哈希值做唯一标识
问题:如何快速判断图片是否在库中?
取图片摘要信息,计算哈希值做唯一标识,与图片路径信息 一起储存在散列表
插入图片时,
先 通过 计算哈希值唯一标识,查找 散列表 判断是否存在.
唯一标识不存在则 代表图片不存在; 唯一标识存在,继续全量比较图片
3.数据校验
举例:
BT下载 基于 P2P协议,网络传输不安全,
通过哈希算法 对100个文件块 分别取哈希值,存在种子文件中.
由于 哈希算法对数据很敏感 ,对下载好的文件块逐一求哈希值,对比种子文件.
4.散列函数
散列函数 决定了 散列表的 冲突概率 和 性能
散列冲突要求相对低 ,不关心能否反向解密,
但 追求高效率
哈希算法在分布式系统中的应用
5.负载均衡
负载均衡算法很多: 随机 轮询 加权轮询
问题:如何实现
会话粘滞(session sticky)
(同一个客户端,依次会话中的所有请求都路由到同一个服务器)
的负载均衡算法?
简单做法:维护一张映射关系表,客户端IP/会话ID 与 服务器编号 映射
弊端:
- 客户端多,映射表就大,浪费内存空间
- 客户端 下线/上线,服务器 扩容/缩容 会导致映射失效.
哈希算法做法完美避开了这两个问题:
对 客户端IP/会话ID 计算哈希值, 哈希值 对 服务器列表大小 进行取模运算,
最终得到 被路由到的服务器编号.
6.数据分片
问题:计算出 1T 的用户搜索关键词日志数据 中 每个关键词被搜索的次数?
难点:1.日志大到内存放不下,2.处理时间会很长
解决:数据分片,再多台机器处理
从 搜索记录日志文件 中读出每个关键词,计算哈希值 在跟N(机器数)取模,得到机器号
这样 相同的搜索关键词必在同一台机器上
这里的处理过程 也是 MapReduce 的基本设计思想
问题:如何快速判断 1亿 张图片是否在 图库中
难点:无法像之前一样 在单台机器上构建散列表
解决:多机处理,通过哈希算法计算唯一标识,对计算机数N取模,
得到机器号,再去对应机器的散列表中查找
7.分布式储存
问题:假设原本有10台机器 采用数据分片 储存数据,现在要扩容 1 台机器
难点:原版对10取模,现在开始对11取模,数据会混乱.
例如:则原本13/10会放置在3,现在13/11放在2.
除非对所有数据重新计算哈希值,并取模,显然不合理.
解决: 一致性哈希算法
k台机器 每台机器 分得 哈希值范围 的一部分区间.(一台机器负责一个区间的哈希值)
新机器加入时,从其他机器那 分得 管理一部分区间的哈希值,
并 获得 被分得的哈希值区间的数据.
其他用到了哈希算法的地方
网络协议的CRC校验 Git commit id
