什麼是hash

Hash中文翻譯為散列，又成為「哈希」，是一類函數的統稱，其特點是定義域無限，值域有限。把任意長度的輸入（又叫做預映射， pre-image），通過散列算法，變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小於輸入的空間，不同的輸入可能會散列成相同的輸出，所以不可能從散列值來確定唯一的輸入值。

簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。

Hash的作用

hash就是將任意長度的消息壓縮成某一固定長度的消息摘要的函數。相當於文件的指紋。

由於文件是無限的，而映射後的字符串能表示的位數是有限的。因此可能會存在不同的key對應相同的Hash值。這就是存在碰撞的可能。

Hash存儲數據

hash表的本質其實就是數組，hash表中通常存放的是鍵值對Entry。

這裡的學號是個key，哈希表就是根據key值來通過哈希函數計算得到一個值，這個值就是下標值，用來確定這個Entry要存放在哈希表中哪個位置。

hash碰撞的解決方法

hash碰撞的解決方式是開放尋址法和拉鏈法。

開放尋址法指的是，當前數組位置1被占用了，就放到下一個位置2上去，如果2也被占用了，就繼續往下找，直到找到空位置。

拉鏈法採用的是鍊表的方式，這個時候位置1就不單單存放的是Entry了，此時的Entry還要額外保存一個next指針，指向數組外的另一個位置，將李四安排在這裡，張三那個Entry中的next指針就指向李四的這個位置，也就是保存的這個位置的內存地址。如果還有衝突，就把又衝突的那個Entry放到一個新位置上，然後李四的Entry指向它，這樣就形成一個鍊表。

開放尋址法和拉鏈法都是想辦法找到下一個空位置來存發生衝突的值。

Hash的實際用途

唯一性驗證

• java中用於判斷變量是否相等都放進 hashCode() 中，⼀起⽣成⼀個儘量不會碰撞的整數

數據完整性驗證：

• 從⽹絡上下載⽂件後，通過⽐對⽂件的 Hash 值（例如 MD5、SHA1），可以確認下載的⽂件是否有損壞。如果下載的⽂件 Hash 值和⽂件提供⽅給出的 Hash 值⼀致，則證明下載的⽂件是完好⽆損的

快速查找：

• HashMap

隱私保護：

• 當重要數據必須暴露的時候，有事可以選擇暴露它的 Hash 值（例如 MD5），以保障原數據的安全。例如⽹站登錄時，可以只保存⽤戶密碼的 Hash 值，在每次登錄驗證時只需要將輸⼊的密碼的 Hash 值和資料庫中保存的 Hash 值作⽐對就好，⽹站⽆需知道⽤戶的密碼。這樣，當⽹站數據失竊時，⽤戶不會因為⾃⼰的密碼被盜導致其他⽹站的安全也受到威脅。

作者：Arrom
連結：https://juejin.cn/post/7127862424887099406
來源：稀土掘金