雜湊函式簡介

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。下表顯示了非素數和素數時的雜湊值。粗體文字表示相同的雜湊值。