除余法
hash(key) = key % M
M為素?cái)?shù)時(shí)，數(shù)據(jù)對(duì)散列表的覆蓋最充分，分布最均勻
MAD法
除余法的缺陷：
1）不動(dòng)點(diǎn)：無論表長(zhǎng)M取值如何，總有hash(0) = 0
2）零階均勻：[0,R)的關(guān)鍵碼，平均分配至M個(gè)桶；但相鄰關(guān)鍵碼的散列地址也必相鄰
一階均勻：鄰近的關(guān)鍵碼，散列地址不再鄰近
MAD = multiply-add-divide
取M為素?cái)?shù)，a>0，b>0，a%M != 0
hash(key) = ( a * key + b )%M
特定場(chǎng)合下，未必需要高階的均勻性
數(shù)字分析
抽取key中的某幾位，構(gòu)成地址。比如，取十進(jìn)制表示的奇數(shù)位，hash(12345) = 135
平方取中
取key^2的中間若干位，構(gòu)成地址。比如，hash(123) = 512? // 123^2 = 15129
折疊法
將key分割成等寬的若干段，取其總和作為地址。比如hash(123456789) = 1368 //123+456+789
位異或法
將key分割成等寬的二進(jìn)制段，經(jīng)異或運(yùn)算得到地址。比如hash(110011011) = 110 //110 ^ 011 ^ 011
（偽）隨機(jī)數(shù)法
（偽）隨機(jī)數(shù)發(fā)生器
循環(huán)：rand(x+1) = [ a * rand(x) ] % M
徑取：hash(key) = rand(key) = [rand(0) * a^key] % M
種子：rand(0) = ？?
（偽）隨機(jī)數(shù)發(fā)生器的實(shí)現(xiàn)，因具體平臺(tái)、不同歷史版本而異，創(chuàng)建的散列表可移植性差
