哈希函数简介

Created: November-22, 2018

散列函数 h() 是一个任意函数，它将任意大小的数据 x ∈ X 映射到固定大小的 y ∈ Y：y = h(x)。好的哈希函数有以下限制：

一般情况下，散列函数的大小小于输入数据的大小：|y| < |x|。散列函数不可逆，换句话说它可能是碰撞：∃ x1, x2 ∈ X, x1 ≠ x2: h(x1) = h(x2)。X 可以是有限集或无限集，Y 是有限集。

散列函数用于计算机科学的许多部分，例如软件工程，密码学，数据库，网络，机器学习等。有许多不同类型的散列函数，具有不同的域特定属性。

哈希值通常是整数值。用于哈希计算的程序语言中有特殊方法。例如，在 C# GetHashCode() 方法中，所有类型都返回 Int32 值（32 位整数）。在 Java 每个类提供 hashCode() 方法返回 int。每种数据类型都有自己或用户定义的实现。

哈希方法

确定散列函数有几种方法。不失一般性，让 x ∈ X = {z ∈ ℤ: z ≥ 0} 是正整数。通常 m 是素数（不太接近 2 的精确幂）。

方法	哈希函数
除法	`h(x) = x mod m`
乘法	`h(x) = ⌊m (xA mod 1)⌋, A ∈ {z ∈ ℝ: 0 < z < 1}`

散列表中使用的散列函数用于将索引计算到插槽数组中。哈希表是用于实现字典（键值结构）的数据结构。良好实现的哈希表有下一个操作的 O(1) 时间：按键插入，搜索和删除数据。多个密钥可以散列到同一个槽。解决碰撞有两种方法：

接下来的方法用于计算开放寻址所需的探测序列

其中 i ∈ {0, 1, ..., m-1}，h'(x), h1(x), h2(x) 是辅助散列函数，c1, c2 是正辅助常数。

让 x ∈ U{1, 1000}, h = x mod m。下表显示了非素数和素数时的哈希值。粗体文本表示相同的哈希值。