Hash表

天天AC,日日驚喜。每天學(xué)點算法，每天進步一點點。

1.哈希表的定義 ? ? ? 散列表（Hash table，也叫哈希表），是根據(jù)關(guān)鍵字（Key value）而直接訪問在內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把鍵值通過一個函數(shù)的計算，映射到表中一個位置來訪問記錄，這加快了查找速度。這個映射函數(shù)稱做散列函數(shù)，存放記錄的數(shù)組稱做散列表。（維基）

? ? ? 個人的理解：舉個例子，你想去圖書館找本書，你不會從第一本找到最后一本，你會看下那本書是歸為小說類還是 IT 類，然后直接去那一類里面查找，哈希表就相當(dāng)于圖書的歸類。 ? ? ? 哈希表和數(shù)組的區(qū)別：可以想象一下，你通過數(shù)組下標(biāo)直接去找到數(shù)組的值，而哈希表是根據(jù)關(guān)鍵字 k ，計算 f(k)去找到值。 ? ? ? 哈希表結(jié)構(gòu)上介于鏈表和二叉樹之間，哈希表是一個固定大小的數(shù)組，數(shù)組的每個元素是一個鏈表（單向或雙向）的頭指針。如果Key一樣，則在一起，如果Key不一樣，則不在一起。哈希表的查詢是飛快的。因為它不需要從頭搜索，它利用Key的“哈希算法”直接定位，查找非?？欤鞣N數(shù)據(jù)庫中的數(shù)據(jù)結(jié)構(gòu)基本都是它。但帶來的問題是，哈希表的尺寸、哈希算法。 若關(guān)鍵字為，則其值存放在的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應(yīng)關(guān)系為散列函數(shù)（Hash function），按這個思想建立的表為散列表。對不同的關(guān)鍵字可能得到同一散列地址，即，而，這種現(xiàn)象稱碰撞（Collision）。具有相同函數(shù)值的關(guān)鍵字對該散列函數(shù)來說稱做同義詞。綜上所述，根據(jù)散列函數(shù)和處理碰撞的方法將一組關(guān)鍵字映象到一個有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“象”作為記錄在表中的存儲位置，這種表便稱為散列表，這一映象過程稱為散列造表或散列，所得的存儲位置稱散列地址。若對于關(guān)鍵字集合中的任一個關(guān)鍵字，經(jīng)散列函數(shù)映象到地址集合中任何一個地址的概率是相等的，則稱此類散列函數(shù)為均勻散列函數(shù)（Uniform Hash function），這就是使關(guān)鍵字經(jīng)過散列函數(shù)得到一個“隨機的地址”，從而減少碰撞。2.構(gòu)造散列函數(shù)

散列函數(shù)能使對一個數(shù)據(jù)序列的訪問過程更加迅速有效，通過散列函數(shù)，數(shù)據(jù)元素將被更快定位。

直接尋址法：取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為散列地址。即或，其中為常數(shù)（這種散列函數(shù)叫做自身函數(shù)）數(shù)字分析法：假設(shè)關(guān)鍵字是以r為基的數(shù)，并且哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的，則可取關(guān)鍵字的若干數(shù)位組成哈希地址。平方取中法：取關(guān)鍵字平方后的中間幾位為哈希地址。通常在選定哈希函數(shù)時不一定能知道關(guān)鍵字的全部情況，取其中的哪幾位也不一定合適，而一個數(shù)平方后的中間幾位數(shù)和數(shù)的每一位都相關(guān)，由此使隨機分布的關(guān)鍵字得到的哈希地址也是隨機的。取的位數(shù)由表長決定。折疊法：將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同），然后取這幾部分的疊加和（舍去進位）作為哈希地址。隨機數(shù)法除留余數(shù)法：取關(guān)鍵字被某個不大于散列表表長m的數(shù)p除后所得的余數(shù)為散列地址。即,?。不僅可以對關(guān)鍵字直接取模，也可在折疊法、平方取中法等運算之后取模。對p的選擇很重要，一般取素數(shù)或m，若p選擇不好，容易產(chǎn)生碰撞。3.處理碰撞的方法 為了知道碰撞產(chǎn)生的相同散列函數(shù)地址所對應(yīng)的關(guān)鍵字，必須選用另外的散列函數(shù)，或者對碰撞結(jié)果進行處理。在算法導(dǎo)論里面介紹了三種方法：開放尋址，單獨鏈表，雙散列。

4.查找效率 數(shù)據(jù)本身分布是否均勻，還有就是散列表的載荷因子。散列表的載荷因子定義為：?= 填入表中的元素個數(shù) / 散列表的長度