雜湊函式雜湊法
雜湊法 (hashing) 的搜尋與一般的搜尋 (saerching) 法不同。 在 Hashing 中，鍵值 (key value) 或識別字 (identifier) 在記憶體的位址是經由雜湊函式 (function) 轉換而得。 一般稱之為雜湊函式 (hashing function) 或鍵值對應位址轉換 (key to address transformation) 。
以下是它的特點：
1. 使用 hashing 搜尋，檔案不須事先排序 (sorting) 。
2. 在沒有碰撞 (collision) 及溢位 (overflow) 的情形下，只需要讀取一次即可。
3. 保密性高，若不知道雜湊函式，無法擷取到資料。
4. 可做資料的壓縮 (data compression) ，利用適當的散置函式，可以將資料壓縮到較小的範圍內以節省空間。
雜湊函式 (hashing function) ：就是一種可將一個 key 對應到一個索引的函式，一個可能的雜湊函式為 h(x)=key % 100 ， (% 傳回 key 除以 100 的餘數 ) ，這個函式僅傳回 key 的末兩位數。 若一個特定的 key ，被雜湊到 i ，就降這個 key 及其對應到的紀錄吋放在 S[i] 。 若一個特定的 key ，被雜湊到 i ，就降這個 key 及其對應到的紀錄吋放在 S[i] 。
● 除法 (Division Method) 是常見的函式，是將資料除以常數，然後使用於數的作為索引的位置，其公式如下：
索引位置 = 鍵值 mod M
上述 M 是餘數，可以取得鍵值除以此除數的餘數。
舉例：搜尋的鍵值分別為 10 、 20 、 30 、 40 、 50 、 60 ， 7 buckets h(x)=x%7
結果： h(x)= 10 % 7=1….3
h(x)= 20 % 7=2….6 0
h(x)= 30 % 7=4….2 1
h(x)= 40 % 7=5….5 2
h(x)= 50 % 7=7….1 3
h(x)= 60 %7=8….4 4
5
6
| 50 |
| 30 |
| 10 |
| 60 |
| 40 |
| 20 |
舉例： 23467851 、 1626527 、 372547 、 56238 右邊第一位和第三位， 100buckets 碰撞石放在下一位置。 舉例： 23467851 、 1626527 、 372547 、 56238 右邊第一位和第三位， 100buckets 碰撞石放在下一位置。
結果： A[28] 56238 結果： A[28] 56238
Ａ [57] 162527
A[58] A[58] 372547
A[81] A[81] 2346851
