密码学 | 蓄势待发！说说什么是散列算法？

2020-08-09 本文已影响0人彭旭锐

前言

散列算法（Hash算法，又译哈希算法） 是一种将任意长度输入转换为固定长度输出的算法，输出的结果就是散列值。

散列算法一定是 压缩映射，即：值域会远小于输入值域。例如，MD5的输出散列值为 128 位，SHA256的输出散列值为 256 位。

散列算法有很多，但是都要满足以下性质 & 要求：

上一节提到，散列算法是压缩映射（输出值域远小于输入值域），因此肯定会存在两个甚至多个输入数据映射到同一个散列值的情况，这就是发生了 散列冲突（又称散列碰撞，Hash Collision）。

需要注意的是，散列冲突是无法完全避免的，这其实只要用鸽巢原理（又称：抽屉原理）就很好理解了，假设有 10 个鸽巢，现有 11 只鸽子，无论分配多么平均，也肯定有一个鸽巢里有两只甚至多只鸽子。

举个例子，Java中的字符串"Aa"与"BB"的散列值就冲突了：

String str1 = "Aa";
String str2 = "BB";
System.out.println(str1.hashCode());  2112
System.out.println(str2.hashCode());  2112 散列冲突

既然散列冲突是无法完全避免的，那么只能采取应对措施，主要有两种：降低概率 & 处理冲突。

降低散列冲突概率的思路主要有：

1、优化散列算法
前面提到了散列算法的随机性：散列值在输出值域的分布尽量随机。这是为了避免出现“堆积”现象，即散列值集中于输出值域的某一块区域，这种情况无疑会增大冲突概率。
2、扩大输出值域
在输入值域相对稳定的情况下，扩大输出值域可以降低冲突概率。例如SHA的散列值长度就比MD5长，相应的冲突概率更低。HashMap 在达到阈值时执行扩容，本质上也是扩大了输出值域。

Editting...