前言
- 在计算机科学中，散列算法 的应用场景有很多，例如：散列表的散列函数、消息完整性验证的消息摘要算法，除此之外你还知道哪些应用场景呢？
- 在这篇文章里，我将带你列举散列算法的 基本要求 & 应用场景。如果能帮上忙，请务必点赞加关注，这真的对我非常重要。
系列文章
相关文章
目录
1. 概述
1.1 散列函数的定义
散列算法（Hash算法，又译哈希算法） 是一种将任意长度输入转换为固定长度输出的算法，输出的结果就是散列值。
散列算法一定是 压缩映射，即：值域会远小于输入值域。例如，MD5的输出散列值为 128 位，SHA256的输出散列值为 256 位。
1.2 散列算法的性质
散列算法有很多，但是都要满足以下性质 & 要求：
| 性质 | 描述 |
|---|---|
| 单向性 | 通过散列值无法反推输入数据 |
| 一致性 | 同一个输入数据，计算后的散列值总是相同的 |
| 高效性 | 散列运算过程尽量快速 & 高效 |
| 随机性 | 散列值在输出值域的分布尽量随机 |
| 输入敏感性 | 相似的数据，计算后的散列值差别很大 |
2. 散列冲突
2.1 什么是散列冲突？
上一节提到，散列算法是压缩映射（输出值域远小于输入值域），因此肯定会存在两个甚至多个输入数据映射到同一个散列值的情况，这就是发生了 散列冲突（又称散列碰撞，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 散列冲突
既然散列冲突是无法完全避免的，那么只能采取应对措施，主要有两种：降低概率 & 处理冲突。
2.2 降低散列冲突概率
降低散列冲突概率的思路主要有：
-
1、优化散列算法
前面提到了散列算法的随机性：散列值在输出值域的分布尽量随机。这是为了避免出现“堆积”现象，即散列值集中于输出值域的某一块区域，这种情况无疑会增大冲突概率。 -
2、扩大输出值域
在输入值域相对稳定的情况下，扩大输出值域可以降低冲突概率。例如SHA的散列值长度就比MD5长，相应的冲突概率更低。HashMap 在达到阈值时执行扩容，本质上也是扩大了输出值域。
2.3 处理散列冲突
在《数据结构 | 散列表是如何避免散列冲突的？》中，我们将讨论散列表中的解决方案。
3. 散列算法的应用场景
Editting...
4. 总结
- 散列算法是一种将任意长度输入转换为固定长度输出的算法，由于是压缩映射，因而无法避免散列冲突。
参考资料
- 《Java加密与解密的艺术》（第6、7、8、9章） —— 梁栋 著
- 《数据结构与算法之美》（第21、22章） —— 王争 讲，极客时间 出品
- 《散列算法》—— 维基百科
推荐阅读
- 密码学 | Base64是加密算法吗？
- 算法面试题 | 回溯算法解题框架
- 算法面试题 | 链表问题总结
- 计算机网络 | 图解 DNS & HTTPDNS 原理
- Android | 带你探究 LayoutInflater 布局解析原理
- Android | 适可而止！看 Glide 如何把生命周期安排得明明白白
- Android | View & Fragment & Window 的 getContext() 一定返回 Activity 吗？
感谢喜欢！你的点赞是对我最大的鼓励！欢迎关注彭旭锐的GitHub！
网友评论