Search

解決溢位

一般常見方法有：線性探測法(linear probing)、鏈結串列(chaining)、平方探測(quadratic probing)、再雜湊(rehashing)。

線性探測法(linear probing)
又稱線性開放定址(linear open addressing)。將雜湊位址視為環狀空間，當溢位發生時，以線性方式找下一個空的儲存空間將資料存入。

【優點】容易使用。

【缺點】易產生「主要群集」問題，也就是一群資料有相近之hashing address之問題，長時間執行會增加平均搜尋時間。

鏈結串列(chaining)
將碰撞之資料(data)放到溢位資料區(overflow data area)，並用指標連結。

【優點】容易使用。

【缺點】需求溢位資料區(overflow data area)，需使用指標函數。

平方探測(quadratic probing)
此方法改善線性探測法之「主要群集」問題，可避免相近之鍵值聚在一起。當h(X)位址發生溢位時，下一次探測位址為

(h(X)+i2) mod b 與 (h(X)-i2) mod b

其中，1≦i≦(b-1)/2，b為可表示為4j+3型式之質數。

再雜湊(rehashing)
事先設計好一套雜湊函數 h1、h2、h3、…、hm，當溢位時先使用h1，若再發生溢位則依次使用h2、h3、…、hm，至沒溢位發生或沒雜湊函數。