Hash演算法原理

1樓：慣性水瓶

雜湊演算法將任意長度的二進位制值對映為較短的固定長度的二進位制值，這個小的二進位制值稱為雜湊值。

雜湊演算法用來產生一些資料片段（例如訊息或會話項）的雜湊值的演算法。使用好的雜湊演算法，在輸入資料中所做的更改就可以更改結果雜湊值中的所有位；因此，雜湊對於檢測資料物件（例如訊息）中的修改很有用。

雜湊表（hash table，也叫雜湊表），是根據關鍵碼值(key value)而直接進行訪問的資料結構。也就是說，它通過把關鍵碼值對映到表中一個位置來訪問記錄，以加快查詢的速度。這個對映函式叫做雜湊函式，存放記錄的陣列叫做雜湊表。

雜湊函式的計算結果是一個儲存單位地址，每個儲存單位稱為「桶」。設一個雜湊表有m個桶，則雜湊函式的值域應為 [0,m-1]。

hash演算法原理

2樓：匿名使用者

雜湊表,它是基於高速存取的角度設計的，也是一種典型的「空間換時間」的做法。顧名思義，該資料結構能夠理解為一個線性表，可是當中的元素不是緊密排列的，而是可能存在空隙。

雜湊表（hash table，也叫雜湊表），是依據關鍵碼值(key value)而直接進行訪問的資料結構。也就是說，它通過把關鍵碼值對映到表中一個位置來訪問記錄，以加快查詢的速度。這個對映函式叫做雜湊函式，存放記錄的陣列叫做雜湊表。

比方我們儲存70個元素，但我們可能為這70個元素申請了100個元素的空間。70/100=0.7，這個數字稱為負載因子。

我們之所以這樣做，也是為了「高速存取」的目的。我們基於一種結果儘可能隨機平均分佈的固定函式h為每一個元素安排儲存位置，這樣就能夠避免遍歷性質的線性搜尋，以達到高速存取。可是因為此隨機性，也必定導致一個問題就是衝突。

所謂衝突，即兩個元素通過雜湊函式h得到的地址同樣，那麼這兩個元素稱為「同義詞」。這類似於70個人去一個有100個椅子的飯店吃飯。雜湊函式的計算結果是一個儲存單位地址，每一個儲存單位稱為「桶」。

設一個雜湊表有m個桶，則雜湊函式的值域應為[0,m-1]。

3樓：匿名使用者

這個問題有點難度，不是很好說清楚。我來做一個比喻吧。

我們有很多的小豬，每個的體重都不一樣，假設體重分佈比較平均(我們考慮到公斤級別)，我們按照體重來分,劃分成100個小豬圈。

然後把每個小豬，按照體重趕進各自的豬圈裡，記錄檔案。好了，如果我們要找某個小豬怎麼辦呢？我們需要每個豬圈，每個小豬的比對嗎？

當然不需要了。我們先看看要找的這個小豬的體重，然後就找到了對應的豬圈了。

在這個豬圈裡的小豬的數量就相對很少了。

我們在這個豬圈裡就可以相對快的找到我們要找到的那個小豬了。對應於hash演算法。

就是按照hashcode分配不同的豬圈，將hashcode相同的豬放到一個豬圈裡。

查詢的時候，先找到hashcode對應的豬圈，然後在逐個比較裡面的小豬。所以問題的關鍵就是建造多少個豬圈比較合適。如果每個小豬的體重全部不同（考慮到毫克級別)，每個都建一個豬圈，那麼我們可以最快速度的找到這頭豬。

缺點就是，建造那麼多豬圈的費用有點太高了。如果我們按照10公斤級別進行劃分，那麼建造的豬圈只有幾個吧，那麼每個圈裡的小豬就很多了。我們雖然可以很快的找到豬圈，但從這個豬圈裡逐個確定那頭小豬也是很累的。

所以，好的hashcode，可以根據實際情況，根據具體的需求，在時間成本(更多的豬圈，更快的速度)和空間本(更少的豬圈，更低的空間需求)之間平衡。