雜湊函式

雜湊函式 將來自包含許多（甚至無限數量）成員的集合的值投影到來自包含固定數量（較少）成員的集合的值。雜湊函式是不可逆的。例如，雜湊函式 可以定義為 ，其中 ，，並且 是 向下取整函式。

雜湊函式可以用於確定兩個物件是否相等（可能具有固定的平均錯誤數）。雜湊函式的其他常見用途包括對大量資料進行 校驗和（例如，迴圈冗餘校驗 [CRC]）以及透過鍵值在資料庫中查詢條目。UNIX c-shell (csh) 使用雜湊表來儲存可執行程式的位置。因此，在使用者的搜尋路徑中新增新的可執行程式需要使用以下命令重新生成雜湊表rehash命令，然後才能在不指定完整路徑的情況下執行這些程式。

為了說明雜湊函式在資料庫查詢中的應用，請考慮一個數據庫，該資料庫由一個包含索引 、名稱和電話號碼的陣列組成，名稱以任意順序排列。

	名稱	號碼
0	Parker	12345
1	(空)
2	Davis	43534
3	Harris	32452
4	Corea	46532
5	Hancock	96562
6	Brecker	37811
7	(空)
	Marsalis	54323

要在此陣列中查詢 Hancock，您需要從陣列的開頭開始，比較名稱，然後嘗試下一個，直到名稱匹配。這種非常簡單的演算法可以在 1 到 步內找到任何條目，平均查詢時間為 。因此，查詢時間與 成正比。如果資料庫已排序，通常可以獲得更快的速度。

	名稱
0	Brecker
1	Corea
2	Davis
3	Hancock
4	Harris
5	Marsalis
6	Parker
7	(空)
	(空)

在這種排序陣列上的高效演算法首先檢查條目 ，然後遞迴地使用二分法檢查區間 或 中的條目，具體取決於最近查詢的名稱是在要查詢的名稱之前還是之後。此過程的平均查詢時間與 成正比。

在此處使用雜湊函式的想法是，儘管名稱中字元組合的可能數量非常大，但在實踐中通常只找到其中的一個子集（即，像“Kwqrst”這樣的名稱遠不如像“Jones”這樣的名稱常見）。因此，當您將條目插入資料庫中的索引時，該索引可以使用鍵來計算（在您搜尋它時也可以使用該鍵），您稍後可能會在您檢查的第一個位置找到它。

考慮以下簡單示例，其中雜湊函式 只是名稱中字元的 ASCII 程式碼之和（假設全部為小寫），計算結果模 。

名稱
Brecker	6
Corea	2
Davis	2
Hancock	12
Harris	12
Marsalis	2
Parker	8

上面的例子說明了雜湊函式對於不同的鍵可以給出相同的結果。通常透過引入第二個雜湊函式 來規避這個困難，該雜湊函式的結果被設計為與 的結果完全不同。為了說明目的，讓 為 1 加上名稱中所有程式碼的按位異或（再次全部取小寫）模 。

名稱
Brecker	11
Corea	3
Davis	10
Hancock	4
Harris	8
Marsalis	3
Parker	8

然後可以將新索引計算為第一個索引和 的總和（模 ），直到找到可以儲存新資料的空槽。請注意，當使用 作為偏移量來遍歷資料庫時，通常不能保證任何鍵最終都會到達任何槽。但是，對於 的某些值，即 素數，確實保證了這種行為，因此 始終被選擇為 素數。在使用 （（素數））計算 後，對於按字母順序新增的名稱，上面的電話列表將如下所示。

在此表中查詢名稱的平均查詢時間取決於資料型別、 和所用雜湊函式的質量。但是，對於雜湊函式的合理選擇，它將遠小於 。