哈希

hash，一般翻譯為散列，也名哈希

哈希的描述：把任意長度的輸入通過雜湊演算法變換為固定長度的輸出，輸出稱為哈希值（散列值）。

• 通過同一哈希函數計算出的哈希值如果不同，那麼輸入值肯定也不同
• 通過同意哈希函數計算出的哈希值如果相同，那麼輸入值不一定相同

兩個不同的輸入值通過相同的哈希函數計算出相同的哈希值，這種現象稱為碰撞。

衡量一個哈希函數好壞的重要标準，就是發生碰撞的機率及發成碰撞的解決方法。

任何哈希函數基本都無法徹底避免碰撞。

常見的解決碰撞的方法有一下幾種：

• 開放定址法
• 鍊位址法
• 再哈希法
• 建立公共溢出區

1.開放定址法

一旦發生了沖突，就去尋找下一個空的散列位址，隻要散清單足夠大，空的散列位址總能找到，并将記錄存入

2.鍊位址法

将哈希表的每個單元作為連結清單的頭結點，所有哈希位址為i的元素構成一個同義詞連結清單。即發生沖突時就把該關鍵字鍊在以該單元為頭結點的連結清單的尾部

3.再哈希法

當哈希位址發生沖突用其他的函數計算另一個哈希函數位址，直到沖突不再産生為止

4.建立公共溢出區

将哈希表分為基本表和溢出表兩部分，發生沖突的元素都放入溢出表中