hash解決衝突的方法優缺點

hash表解決衝突的方法：

1.開放定址法

1.1 線性探測法

1.2 二次探測法

1.3 隨機探測法

2.鏈地址法

3.公共溢出區法

這種方法需要兩個表，分別是基本表、溢出表

鏈地址法的優點

與開放定址法相比，拉鏈法有如下幾個優點：

①鏈地址法處理衝突簡單，且無堆積現象，即非同義詞決不會發生衝突，因此平均查找長度較短；

②由於鏈地址法中各鏈表上的結點空間是動態申請的，故它更適合於造表前無法確定表長的情況；

③開放定址法為減少衝突，要求裝填因子α較小，故當結點規模較大時會浪費很多空間。而鏈地址法中可取α≥1，且結點較大時，鏈地址法中增加的指針域可忽略不計，因此節省空間；

④在用鏈地址法構造的散列表中，刪除結點的操作易於實現。只要簡單地刪去鏈表上相應的結點即可。而對開放地址法構造的散列表，刪除結點不能簡單地將被刪結 點的空間置為空，否則將截斷在它之後填人散列表的同義詞結點的查找路徑。這是因為各種開放地址法中，空地址單元(即開放地址)都是查找失敗的條件。因此在 用開放地址法處理衝突的散列表上執行刪除操作，只能在被刪結點上做刪除標記，而不能真正刪除結點。

鏈地址法的缺點

鏈地址法的缺點是：指針需要額外的空間，故當結點規模較小時，開放定址法較為節省空間，而若將節省的指針空間用來擴大散列表的規模，可使裝填因子變小，這又減少了開放定址法中的衝突，從而提高平均查找速度。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！