李大師 asked in 電腦與網際網路軟體 · 1 decade ago

什麼是線性探測法(linear probing)?

什麼是線性探測法(linear probing)?請詳細說明可以的話請附參考資料

1 Answer

Rating
  • Favorite Answer

    親愛的板主您好有關您的問題,分享如下線性探測法(Linear Probing)是當碰撞情形發生時,如果該索引位置已經有鍵值,就使用下列原則來處理,如下所示:●      如果鍵值欲存放的索引位置已經有鍵值存在時,將鍵值儲存在下一個索引位置。●      如果原位置的下一個索引位置仍然已有鍵值,再將鍵值儲存在下一個索引位置,重覆操作直到找到一個空位置。 上述碰撞問題的處理稱為線性探測法或線性開放地址法(Linear Open Addressing)● 雜湊函數是使用除法的餘數運算          索引位置 = 鍵值 mod 10 重雜湊法可以解決線性深測法儲存位置過於集中的問題,這是線性探測法解決碰撞問題時造成的特殊情況。索引值6可能是由索引值5和6碰撞而決定。這樣的結果將造成搜尋時,比較的次數快速的增加,而且這些鍵值連續的現象將愈演愈烈,因為碰撞的機會大幅增加,所以鍵值越連越多,這種情況稱為叢聚現象(Cluster)。 重雜湊法雖然可以解決線性深測法,儲存位置過於集中的問題,不過線性探測法的雜湊搜尋仍然有二個問題,如下所示:● 擴充困難:如果雜湊表的儲存空間有n個元素,在存入n+1個元素時,就會發生鍵值無法存入的問題。●      鍵值刪除問題:除非重建整個雜湊表,否則刪除有碰撞情況的鍵值,在雜湊搜尋時就有可能再也找不到http://mail2u.tnit.edu.tw/~49307009/data/14詳細解說請點選...

    2006-10-09 14:05:12 補充:

    什麼是二次探測法:也是當碰撞而且溢位發生時,在雜湊表中找尋另一個可用空間的方法,其找尋的方式是,第一次碰撞. 時,由碰撞發生的位置加上1. 2. ;第二次加上,由碰撞發生的位置加上2. 2. ;第三次加上,由碰撞發生的位置加上以此類推

Still have questions? Get your answers by asking now.