概``述
Hash算法应用
Hash算法设计
- 单向Hash，不可逆推
- 数据敏感，一点点改动，结果很大差异
- 冲突概率小
- 性能尽可能高效
应用
- 安全加密(MD5密码)
- 唯一标识(相同图片识别)
- 数据校对(BT下载，每个块Hash)
- 散列函数(设计散列表的关键，决定了散列表的冲突概率以及散列表的性能)
- 分布式系统相关：
- 负载均衡：轮询/随机/加权轮询/IpHash，其中IpHash就是用了Hash算法相关（IP=>哈希值=>Mod服务器数)
- 数据分片
- 分布式存储
数据分片
n台机器，1T搜索记录，分别取搜索记录Hash值，再Mod n得到每个搜索记录待处理的服务器，每个机器分别统计搜索词次数，最后再从n台机器统计起来（MapReduce思想）
如何在一亿张图片中，检索一张图片是否存在！
- 对每个图片内容求摘要信息（可以通过前中后值取值算Hash），无法直接存到一台机器中，假定存到N台机器，将图片摘要信息Mod N，存储到第X台机器；
- 针对检索的图片，求得Hash内容摘要，Mod N，到第X台机器中检索是否摘要在图片库中；
给一亿张图片构建Hash表，需要多少台机器?
- 一亿张图片，以MD5为例，得到128位(16字节Hash值），每个指针8字节，路径平均128字节(最长256字节/2)，合计16+8+128=152字节；152byte x 1e8 = 15.2G内容；散列因子算0.75，则15.2G*4/3 = 21G；以每个机器2G大小，则合计需要10多台机器！
借助Hash函数实现的数据分片，可以突破单机内存、CPU限制。
分布式存储
海量数据缓存，将数据分布在多台机器上，提升每个节点的读写性能，从而实现整体分布式系统性能的提升
默认如果我们只使用简单的Hash算法，即针对key，利用hash(key) mod n得到具体的存储服务器，一旦我们增加或者减少存储服务器节点，则会导致很大一部分的节点缓存失效。
如果是分布式缓存，可能导致缓存穿透到数据库，导致雪崩效应。应对此类问题的解决方案是一致性Hash。
一致哈希算法的主要思想是将每个缓存服务器与一个或多个哈希值域区间关联起来，其中区间边界通过计算缓存服务器对应的哈希值来决定。
假定我们有k台机器，数据的哈希值区间将整个值范围划分为m个区间，m远大于k，每个机器负载m/k个小区间。当有新的机器加入或移除时候，仅只有少量数据元素需要重新散列存储！
具体实现方式，将圆分成2^32份(m)，假定有4个存储节点(k)，每个key 执行hash(key) mod 2^32 = X，寻找>=X的下一个节点k，即为即为存储节点；
良好的分布式存储系统，Hash算法应该还满足：
- 单调性：满足一致性Hash，即单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲节点中，当又加入新的节点或者移除节点，整体的Hash映射到节点不会有大的变化；
- 平衡性：考虑到节点删除后，可能导致Hash值偏差不均衡，可以考虑加入虚拟节点；
- 分散性
- 负载性
参考文章：