哈希表的概念和哈希沖突的處理

哈希表(Hash table)是相對於線性表和樹形結構的壹種數據結構。它可以直接在元素的存儲位置和其關鍵字之間建立壹定的關系，所以在搜索的時候，不需要做或者很少做比較，就可以直接通過關鍵字找到對應的記錄。這就是Hase Search的思想，通過對元素的鍵值進行某種運算，直接找到元素的地址。即使用關鍵字到地址的直接轉換方式，不需要重復比較。因此，哈希搜索法也稱為哈希法或散列法。

選擇壹個好的哈希函數可以在壹定程度上減少沖突，但是在實際應用中，很難完全避免沖突，所以選擇壹個有效的方法來處理沖突是哈希表的另壹個關鍵問題。

處理沖突的方式與哈希表本身的組織形式有關。根據組織形式的不同，通常分為兩類:開放地址法和鏈地址法。

開放地址方法的基本思想是所有記錄都存儲在壹個哈希表數組中。當壹個記錄鍵的初始哈希地址H0=H(key)沖突時，基於H0計算另壹個地址H1。如果H1仍然沖突，則根據H1計算下壹個地址H2。如果H2仍然沖突，下壹個地址H2將被發現。

根據計算方法，可分為以下三種檢測方法:

線性檢測法在處理中出現沖突時會競爭相同的後續哈希地址，稱為二次聚合或累加。即在處理同義詞沖突的過程中，加入了非同義詞沖突。

它的好處是，只要哈希表沒有滿，就壹定能找到不沖突的地址。

二次檢測法和偽隨機數檢測法可以避免二次聚集的現象，但不能保證找到沒有沖突的地址。

鏈地址法的基本思想是將散列地址相同的記錄放在同壹個單鏈表中，稱為同義詞鏈表。有m個具有m個散列地址的單鏈表，並且數組HT [0...m-1]用於存儲每個鏈表的頭指針。所有hash地址為I的記錄都以節點的形式插入到以HT[i]為頭節點的單鏈表中。