共计 2737 个字符，预计需要花费 7 分钟才能阅读完成。
哈希函数
在计算机中，函数 是一个有输入输出的黑匣子，而 哈希函数 是其中一类函数。咱们通常会接触两类哈希函数。
- 用于 哈希表 的哈希函数。比方布隆过滤里的哈希函数，
HashMap的哈希函数。 - 用于加密和签名的哈希函数。比方，MD5，SHA-256。
哈希函数通常具备以下特色。
- 长度固定。任意的输出肯定失去雷同的输入长度。
- 确定性。雷同的输出肯定失去雷同的输入。
- 单向性。通过输出失去输入，然而不能通过输入反推输出。
哈希函数品质
哈希函数作用是将 一堆数据信息映射到一个简短数据，这个简短数据代表了整个数据信息。比方身份证号。
如何掂量一个哈希函数品质，次要从考量以下方面
- 哈希值是否散布平均，呈现出随机性，有利于哈希表空间利用率晋升，减少哈希的破解难度；
- 哈希碰撞的概率很低，碰撞概率应该管制在肯定范畴；
- 是否计算得更快，一个哈希函数计算工夫越短效率越高。
碰撞概率
什么是碰撞？
当同一个哈希值映射了不同数据时，即产生了碰撞。
碰撞不可避免，只能尽可能减小碰撞概率，而碰撞概率由 哈希长度 和算法 决定。
碰撞概率如何评估。概率学中有个经典问题 生日问题，数学法则揭示，23 人中存在两人生日雷同的概率会大于 50%，100 人中存在两人生日雷同的概率超过 99%。这违反直觉教训，所以也叫生日悖论。
生日问题 是碰撞概率的理论指导。密码学中，攻击者依据此实践只须要 \({\textstyle {\sqrt {2^{n}}}=2^{n/2}} \) 次就能找哈希函数碰撞。
上面是不同位哈希的碰撞参考表：
另外依据维基上的推导，咱们还能够失去以下公式。
指定已有哈希值数量 \(n \) 估算碰撞概率 \(p(n) \)
$$
p (n)\approx 1- e^{-\frac{n(n-1)}{2N}}
$$
指定碰撞概率 \(p \) 和哈希范畴最大值 \(d \)，估算达到碰撞概率时须要的哈希数量 \(n \)
$$
n (p)\approx \sqrt{2\cdot d\ln\left({1 \over 1-p}\right)}+{1 \over 2}
$$
指定碰撞概率 \(p \) 和哈希范畴最大值 \(d \)，估算碰撞数量 \(rn \)
$$
{\displaystyle rn=n-d+d\left({\frac {d-1}{d}}\right)^{n}}
$$
// 估算实践碰撞概率
public static double collisionProb(double n, double d) {return 1 - Math.exp(-0.5 * (n * (n - 1)) / d);
}// 估算达到碰撞概率时须要的哈希数量
public static long collisionN(double p, double d) {return Math.round(Math.sqrt(2 * d * Math.log(1 / (1 - p))) + 0.5);
}// 估算碰撞哈希数量
public static double collisionRN(double n, double d) {return n - d + d * Math.pow((d - 1) / d, n);
}依据下面公式，咱们评估一下String.hashCode()，Java 外面 hashCode() 返回 int，所以哈希范畴是 \(2^{32} \)。看下 String.hashCode() 在 1000 万 UUID 下的体现。
1000 万 UUID，实践上的碰撞数量为 11632.50
collisionRN(10000000, Math.pow(2, 32)) // 11632.50应用上面代码进行测试
private static Map<Integer, Set<String>> collisions(Set<String> values) {Map<Integer, Set<String>> result = new HashMap<>();
for (String value : values) {Integer hashCode = value.hashCode();
Set<String> bucket = result.computeIfAbsent(hashCode, k -> new TreeSet<>());
bucket.add(value);
}
return result;
}
public static void main(String[] args) throws IOException {Set<String> uuids = new HashSet<>();
for (int i = 0; i< 10000000; i++){uuids.add(UUID.randomUUID().toString());
}
Map<Integer, Set<String>> values = collisions(uuids);
int maxhc = 0, maxsize = 0;
for (Map.Entry<Integer, Set<String>> e : values.entrySet()) {Integer hashCode = e.getKey();
Set<String> bucket = e.getValue();
if (bucket.size() > maxsize) {
maxhc = hashCode;
maxsize = bucket.size();}
}
System.out.println("UUID 总数:" + uuids.size());
System.out.println("哈希值总数:" + values.size());
System.out.println("碰撞总数:" + (uuids.size() - values.size()));
System.out.println("碰撞概率:" + String.format("%.8f", 1.0 * (uuids.size() - values.size()) / uuids.size()));
if (maxsize != 0) {System.out.println("最大的碰撞的字符串:" + maxsize + " " + values.get(maxhc));
}
}碰撞总数 11713 十分靠近理论值。
UUID 总数: 10000000
哈希值总数: 9988287
碰撞总数: 11713
碰撞概率: 0.00117130留神，下面测试不足以得出 string.hashCode()性能论断，字符串状况很多，无奈逐个笼罩。
对于 JDK 中的hashCode 算法的优劣决定了它在哈希表的散布，咱们能够通过估算理论值和实测值来一直优化算法。
对于一些有名的哈希算法，比方FNV-1，Murmur2 网上有个帖子专门比照了它们的碰撞概率，散布状况。
https://softwareengineering.s…
小结
哈希函数是将长信息映射为长度固定的短数据，判断一个哈希函数的好坏考量它的 碰撞概率 和哈希值的散布状况。
https://en.wikipedia.org/wiki…
