哈希表與哈希函數

記錄在結構中的相對位置是隨機的，和記錄的關鍵字之間不存在確定的關係。因此，在結構中查找記錄需要進行一系列和關鍵字比較。這一類建立在「比較」基礎上，查找效率依賴於查找過程中進行比較的次數。

理想情況下是希望不經過比較，一次存取便能得到記錄，那就必須在記錄的存儲位置和它的關鍵字之間建立確定的關係f，使每個關鍵字和結構中一個唯一的存儲位置相對應。因而在查找時，只要根據這個對應關係f找到給定值K的像f(k)即可。

若結構中存在關鍵字和k相等的記錄，則必定在f(k)的存儲位置上，因此，不需要進行不叫便可直接取得所差記錄。稱這個對應關係f為哈希（Hash）函數，按這個設想建立的表為哈希表。

舉例：假設建立一張全國30個地區的各民族人口統計表，每個地區為一個記錄，記錄項為：

顯然，可以用一維數組c(1:30)來存這張表，其中c[i]是編號為i的地區的人口情況。編號i便為記錄的關鍵子，由它唯一確定記錄位置i。例如，假設北京市編號1，則若要查看北京市的各民族人口，只要取出c[1] 的記錄即可。

假如把這個數據看成哈希表，則哈希函說f(key)=key.很多時候並不是數字，用數字給予記錄，其中Beijing的哈希函說數值為字母「B」在字母表中的需要為02等，如下表：

由此可見：

（1） 哈希函數式一個映像，給定很靈活，只要使得關鍵字由此所得的哈希函數值都在允許的範圍即可。

（2） 對不同的關鍵字可能得到同一哈希地址，

即key1不等於key2,而f(key1)=f(key2),稱為衝突（Collision）.

綜合上述，可如下描述哈希表：根據跟定的哈希函數H(key)和處理衝突的方法將一組關鍵字映像到一個有限的連續地址集（區間）上，並以關鍵字在地址集中的「像「作為記錄在表中的存儲位置，這種表為哈希表，這一映像過程稱為哈希表或者散列，所得存儲位置稱為哈希地址活著散列地址。

哈希函數和處理衝突方法嘛，下次討論吧～～～

推薦閱讀：