定义哈希是一种将任意长度的输入转化为固定长度输出的算法。假设我们定义了一个名为H的哈希函数，输入内容为message，输出内容为x，则有如下公式。H(message)=x这是一个压缩过程。通常，我们将输出值称为哈希值。下面通过一个具体的案例来理解散列的过程。我们定义这样一个场景，约定任何正整数都应该存放在一个长度为6的数组中。这个时候，我们可以利用hash的思想来设计什么样的方案来做到这一点呢？对于数组的具体位置，我们可以用下标来表示0、1、2、3、4、5。如果我们想把任意一个正整数放入数组中，只需要设计一个函数，输入值为任意正整数，输出值为数组中任意一个下标。得到输出值后，我们就相当于知道输入值应该放在数组的某处。我们可以使用求余法来定义这个散列函数。functionsuplus(number){returnnumber%6}所以，随机取几个数，得到hash值后，存入数组对应位置即可。//Inputvalue:61suplus(61)=1//Inputvalue:101suplus(101)=5此时的hash值表示数组的下标，所以在很多应用场景中，输出结果hash值也称为is哈希地址。HashCollision在上面的例子中，输入值的范围必须大于输出值的范围，这是hash的重要特性之一。所以在某些情况下，不同的输入会产生相同的输出。//不同的输入得到相同的输出，相同的哈希地址suplus(7)=1suplus(61)=1此时，哈希地址是相同的，根据规则，我们要在位置相同，这种情况称为散列冲突（collision）。有很多方法可以解决哈希冲突。这里介绍一种比较常见的方法：将数组的每个地址作为根节点，构建一个新的链表。例如，当输入数字分别为7、61时。但是，当数据量巨大时，链表的查询速度就比较低效了。所以在实践中，我们会用红黑树等运行效率更高的数据结构来代替链表。当然，最理想的情况是输出范围足够宽，可以防止散列冲突。因此，我们在实践中使用的哈希函数的输出值范围非常大。比如md5，早期用得比较多，现在比sha256用得更多：比特币使用的哈希算法。但是，由于输入值范围必须大于输出值范围，理论上哈希冲突必然存在。现在md5可以人为制造hash碰撞，实用性大大降低。本文转载自微信公众号“这波可以反击”，可以通过以下二维码关注。转载本文请联系本波杀公众号。
