題組內容
四、請回答以下有關雜湊搜尋法(Hashing Search)的問題:
⑵利用雜湊函數(Hash Function)來儲存資料時,如果產生溢位(Overflow)時,請 舉出兩種解決方法並說明其作法。(10 分)
詳解 (共 1 筆)
詳解
線性探測(Linear Probing):
是一開放尋址的策略。當雜湊函數對一個給定值產生一個鍵,且這個鍵指向雜湊表中某個已被占用的單元時,線性探測將往雜湊表後尋找最近的空閒單元,並將新的鍵插入。
平方探測(Quadratic Probing):
是一開放尋址的策略。當雜湊函數之結果被占用時,平方探測將以雜湊結果每次+k2(k=1,2,3,4,5,6...)直到尋找到空閒單元並插入。