Hash表

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

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

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

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

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

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