前言

• 在计算机科学中，散列算法 的应用场景有很多，例如：散列表的散列函数、消息完整性验证的消息摘要算法，除此之外你还知道哪些应用场景呢？
• 在这篇文章里，我将带你列举散列算法的 基本要求 & 应用场景。如果能帮上忙，请务必点赞加关注，这真的对我非常重要。

目录

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. 总结

• 散列算法是一种将任意长度输入转换为固定长度输出的算法，由于是压缩映射，因而无法避免散列冲突。