散清單、散列函數

直接尋址法，浪費空間。

散列函數：

（1）除法函數：

h(k)=kmodm

m的選擇：一個不太接近2的幂次的素數。

（2）乘法函數： h(k)=m∗(kAmod1)

k乘以A之後取小數部分再乘以m.在這裡m的選擇不是重點。

通過散列函數将k映射到一個值最容易造成沖突。解決沖突的兩種方法：

（1）連結清單法：顧名思義

（2）開放尋址法：

（a）線性探查：

h(k,i)=(h′(k)+i)modm

（b）二次探查： h(k,i)=(h′(k)+c∗i+c∗i2)modm

（c）雙重散列： h(k,i)=(h1(k)+i∗h2(k))modm