散列的演算法

① 什麼是哈希表和哈希演算法

哈希演算法並不是一個特定的演算法而是一類演算法的統稱。哈希演算法也叫散列演算法,一般來說滿足這樣的關系:f(data)=key,輸入任意長度的data數據,經過哈希演算法處理後輸出一個定長的數據key。同時這個過程是不可逆的,無法由key逆推出data。如果是一個data數據集,經過哈希演算法處理後得到key的數據集,然後將keys與原始數據進行一一映射就得到了一個哈希表。一般來說哈希表M符合M[key]=data這種形式。哈希表的好處是當原始數據較大時,我們可以用哈希演算法處理得到定長的哈希值key,那麼這個key相對原始數據要小得多。我們就可以用這個較小的數據集來做索引,達到快速查找的目的。稍微想一下就可以發現,既然輸入數據不定長,而輸出的哈希值卻是固定長度的,這意味著哈希值是一個有限集合,而輸入數據則可以是無窮多個。那麼建立一對一關系明顯是不現實的。所以"碰撞"(不同的輸入數據對應了相同的哈希值)是必然會發生的,所以一個成熟的哈希演算法會有較好的抗沖突性。同時在實現哈希表的結構時也要考慮到哈希沖突的問題。密碼上常用的MD5,SHA都是哈希演算法,因為key的長度(相對大家的密碼來說)較大所以碰撞空間較大,有比較好的抗碰撞性,所以常常用作密碼校驗。
麻煩採納，謝謝!