数据结构与算法分析：大纲
数据结构：数组
算法：hash算法
算法：排序算法Java实现
1 Hash算法？
将任意长度的二进制串映射为固定长度的二进制值串的映射规则就是Hash算法。通过原始数据映射之后得到的二进制串就是hash值。
- 需要满足的要求
- hash值非常困难的反向推导出原始数据。
- 输入数据敏感，原始数据只修改了一个bit,最后的hash值也大不相同。
- 散列冲突的概率很小，对于不同的原始数据，hash值相同的概率非常小。
- hash算法的执行效率要尽量高效，针对长文本也能很快计算出hash值。
雀巢原理：有10个鸽巢，有11个鸽子，那肯定有1个鸽巢中的鸽子数量多于1。
所以对于定长的二进制串肯定会存在hash值相同。无法做到零冲突。
2 应用：安全加密
MD5+SHA
3 应用：唯一标识
对信息摘要进行Hash
通过比对hash值是否相同来判断是否同一个文件。
4 应用：数据校验
电驴分段下载
5 应用：散列函数
6 应用：负载均衡
同一个客户端在一次会话中的所有请求都路由到一个服务器上。
Hash(ip+sessionId)%服务器个数
7 应用：数据分片
海量数据-->hash分片-->单台机器-->汇总结果
8 应用：分布式存储
一致性Hash解决分布式存储结构下动态增加和删除节点所带来的问题。
https://en.wikipedia.org/wiki/Consistent_hashing
网友评论