Hash

Hash，一般翻譯做"散列"，也有直接音譯為"哈希"的，就是把任意長度的輸入(又叫做預映射， pre-image)，通過散列算法，變換成固定長度的輸出，該輸出就是散列值。這種轉(zhuǎn)換是一種壓縮映射，也就是，散列值的空間通常遠小于輸入的空間，不同的輸入可能會散列成相同的輸出，所以不可能從散列值來唯一的確定輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數(shù)。

HASH函數(shù)(計算機算法領域)

若結(jié)構(gòu)中存在和關鍵字K相等的記錄，則必定在f(K)的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應關系f為散列函數(shù)(Hash function)，按這個思想建立的表為散列表。

對不同的關鍵字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，這種現(xiàn)象稱碰撞。具有相同函數(shù)值的關鍵字對該散列函數(shù)來說稱做同義詞。綜上所述，根據(jù)散列函數(shù)H(key)和處理沖突的方法將一組關鍵字映象到一個 有限的連續(xù)的地址集(區(qū)間)上，并以關鍵字在地址集中的"象" 作為記錄在表中的存儲位置，這種表便稱為散列表，這一映象過程稱為散列造表或散列，所得的存儲位置稱散列地址。

若對于關鍵字集合中的任一個關鍵字，經(jīng)散列函數(shù)映象到地址集合中任何 一個地址的概率是相等的，則稱此類散列函數(shù)為均勻散列函數(shù)(Uniform Hash function)，這就是使關鍵字經(jīng)過散列函數(shù)得到一個"隨機的地址"，從而減少沖突。

常用HASH函數(shù)

·直接取余法:f(x):= x mod maxM； maxM一般是不太接近 2^t 的一個質(zhì)數(shù)。

·乘法取整法:f(x):=trunc((x/maxX) * maxlongit) mod maxM，主要用于實數(shù)。

·平方取中法:f(x):=(x * x div 1000 ) mod 1000000)； 平方后取中間的，每位包含信息比較多。