線性探測再散列法是啥？

線性探測再散列是哈希表解決沖突的一種計算方法，哈希表又稱散列表，哈希表存儲的基本思想是：以數據表中的每個記錄的關鍵字 k為自變量，通過一種函數H(k)計算出函數值。

把這個值解釋為一塊連續存儲空間（即數組空間）的單元地址（即下標），將該記錄存儲到這個單元中。

在此稱該函數H為哈希函數或散列函數。按這種方法建立的表稱為哈希表或散列表。

Hi=(H(key)+di) % m，i=1,2,……k(k<=m-1)，H(key)哈希函數，m哈希表長，di增量序列。

當di值可能為1,2,3,...m-1，稱線性探測再散列。開放地址法有一個公式：Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1）。

其中，m為哈希表的表長。di是產生沖突的時候的增量序列。

如果di取1，則每次沖突之后，向后移動1個位置。如果di取值可能為1，-1、4、-4、9、-9、16,、16、...k*k、-k*k(k<=m/2），稱二次探測再散列，如果di取值可能為偽隨機數列。稱偽隨機探測再散列。