Hash函數
在一般的線性表、樹結構中，資料的存儲位置是随機的，不像數組可以通過索引能一步查找到目标元素。為了能快速地在沒有索引之類的結構中找到目标元素，需要為存儲位址和值之間做一種映射關系h(key),這個h就是哈希函數，用公式表示：
h(key)=Addr
h:哈希函數
key:關鍵字，用來唯一區分對象的
把線性表中每個對象的關鍵字通過哈希函數h(key)映射到記憶體單元位址，并把對象存儲到該記憶體單元，這樣的線性表存儲結構稱為哈希表或散清單。
構造哈希函數
構造哈希函數的方法有很多種，下面介紹幾種常見的算法。在設定哈希函數時，通常要考慮以下因素：
○ 計算函希函數所需的時間
○ 關鍵字的長度
○ 哈希表的長度
○ 關鍵字的分布情況
○ 記錄的查找頻率
1. 直接定址法
直接定址法取關鍵字或關鍵字的某個線性函數作為哈希位址，即
h(key) = key
或
h(key) = a*key + b
其中a,b為常數，調整a與b的值可以使哈希位址取值範圍與存儲空間範圍一緻。這種方法簡單并且不會發生沖突，适用于關鍵字分布基本連續的情況，若關鍵字分布不連續，将造成存儲空間的巨大浪費。
2. 數字分析法
數字分析法是提取關鍵字中随機性較好的數字位，将其拼接作為哈希位址，适用于所有關鍵字已知的情況，并需要對關鍵字中每位的取值情況進行分析。如下圖，經分析c,f,g,h這幾位取值較為集中，随機性不好，不适用于哈希函數，而a,e取值分散，可将這兩個數字拼接位哈希位址。需要注意，提取多少位數字應該根據哈希表長度來确定。
位 h g f e d c b a 提取結果
6 1 3 1 7 6 3 2 12
6 2 3 2 6 8 7 5 25
6 2 3 4 3 6 3 4 44
6 2 7 0 6 6 1 6 6
6 1 7 7 4 6 3 8 78
6 1 3 8 1 2 6 1 81
6 1 3 9 4 2 2 0 90
3. 除留餘數法
除留餘數法采用取模運算，把關鍵字除以某個不大于哈希表表長的整數得到的餘數作為哈希位址。哈希函數形式為：
h(key) = key % p
除留餘數法的關鍵是選好P，使得記錄集合中的每個關鍵字通過該整數轉換後映射到哈希表範圍内任意位址上的機率相等，進而盡可能減少發生沖突的可能性。
例如，P不要設為2的次幂，如設P=25,則對P的取模相當于截取P的最低5位二進制數，這等于将關鍵字的所有高位二進制數都忽略了。理論研究表明，P取奇數比偶數效果好，P取不大于哈希表長度的質數效果最好。
507683的二進制 1111011111100100011
507683%2相當于取低5位二進制數