哈希表與哈希函數
記錄在結構中的相對位置是隨機的,和記錄的關鍵字之間不存在確定的關係。因此,在結構中查找記錄需要進行一系列和關鍵字比較。這一類建立在「比較」基礎上,查找效率依賴於查找過程中進行比較的次數。
理想情況下是希望不經過比較,一次存取便能得到記錄,那就必須在記錄的存儲位置和它的關鍵字之間建立確定的關係f,使每個關鍵字和結構中一個唯一的存儲位置相對應。因而在查找時,只要根據這個對應關係f找到給定值K的像f(k)即可。
若結構中存在關鍵字和k相等的記錄,則必定在f(k)的存儲位置上,因此,不需要進行不叫便可直接取得所差記錄。稱這個對應關係f為哈希(Hash)函數,按這個設想建立的表為哈希表。
舉例:假設建立一張全國30個地區的各民族人口統計表,每個地區為一個記錄,記錄項為: