Hash 函数(hash function),也称为散列函数 或 杂凑函数。原先是一种被用在资料编码中的技术。可以用来加密需要被隐藏的资料。还可以用来比较不同文本的相似度。

什么是 Hash 算法

哈希算法主要功能是将任意长度的消息M,映射为一个长度较短且长度固定的值 H(M)。 H(M)即为散列值。

hash 算法最重要的特点就是:

因此,其主要作用就是为了验证原始数据是否被篡改。

此外,在hash还经常被用作在数据存储的过程中,将数据映射到一个有限的地址区间内的映射方法。

这种映射方式存储形成的散列表,被称为hash表,数据存储的地址被称为hash地址或者散列地址。作为线性数据结构与表格和队列相比,hash表无疑是查找速度比较快的一种。

在我们日常编程工作中最常用的一种hash的场景就是 hashmap/hashtable。

Hash 值的计算方式

在数据映射算法中,常见的 hash 函数有以下几个。

Hash 碰撞

上边提到过,hash值的计算过程中,相同的输入一定会得到相同的输出;而不同的输入也有一定的可能会得到相同的输出。

因此,如果使用 hash 算法作为地址的计算方法。必然会出现两个不同的值落在相同的地址上的问题。这个现象就叫 Hash碰撞

即: hash(a) == hash(b)

衡量一个hash函数的好坏,最重要的指标就是发生碰撞的概率以及发生碰撞的解决方案。任何hash函数基本都无法彻底避免碰撞。常见的解决碰撞的方法有以下几种:

未完待续。。。