哈希算法

哈希算法是指将任意长度的二进制值串映射为固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制值串就是哈希值

要设计一个优秀的哈希算法需要满足的几点要求:

哈希算法要处理的文本可能是各种各样的。比如,对于非常长的文本,如果哈希算法的计算时间很长,那就只能停留在理论研究的层面,很难应用到实际的软件开发中。比如,我们把今天一篇包含 4000 多个汉字的文章,用 MD5 计算哈希值,用不了 1ms 的时间。

哈希算法的应用

最常见的应用分别是安全加密、唯一标识、数据校验、散列函数

在分布式系统中的应用有负载均衡、数据分片、分布式存储

应用一:安全加密

最常用于加密的哈希算法是MD5(MD5 Message-Digest Algorithm,MD5 消息摘要算法)、SHA(Secure Hash Algorithm,安全散列算法)、DES(Data Encryption Standard,数据加密标准)、AES(Advanced Encryption Standard,高级加密标准)。

为什么哈希算法无法做到零冲突?

鸽巢原理(也叫抽屉原理)是说,如果有 10 个鸽巢,有 11 只鸽子,那肯定有 1 个鸽巢中的鸽子数量多于 1 个,换句话说就是,肯定有 2 只鸽子在 1 个鸽巢内。

哈希算法产生的哈希值的长度是固定且有限的。比如 MD5 的哈希值是固定的 128 位二进制串,能表示的数据是有限的,最多能表示 2128 个数据,但要哈希的数据是无穷的。基于鸽巢原理,如果对 2128 + 1 个数据求哈希值,就必然会存在哈希值相同的情况。当然,哈希值越长的哈希算法,散列冲突的概率越低。

2^128=340282366920938463463374607431768211456

但MD5有 2128 个不同的哈希值,散列冲突的概率小于 $\frac{1}{2^{128}}$,冲突的概率极低。

通过毫无规律的穷举的方法,找到跟一个 MD5 值相同的另一个数据,那耗费的时间是个天文数字。没有绝对安全的加密。越复杂、越难破解的加密算法,需要的计算时间也越长。比如 SHA-256 比 SHA-1 要更复杂、更安全,相应的计算时间就会比较长。

应用二:唯一标识