數據結構-哈希表及其查找
哈希表與哈希函數
記錄在結構中的相對位置是隨機的,和記錄的關鍵字之間不存在確定的關係。因此,在結構中查找記錄需要進行一系列和關鍵字比較。這一類建立在「比較」基礎上,查找效率依賴於查找過程中進行比較的次數。
理想情況下是希望不經過比較,一次存取便能得到記錄,那就必須在記錄的存儲位置和它的關鍵字之間建立確定的關係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)和處理衝突的方法將一組關鍵字映像到一個有限的連續地址集(區間)上,並以關鍵字在地址集中的「像「作為記錄在表中的存儲位置,這種表為哈希表,這一映像過程稱為哈希表或者散列,所得存儲位置稱為哈希地址活著散列地址。
哈希函數和處理衝突方法嘛,下次討論吧~~~
推薦閱讀: