什么是哈希表东揣？
哈希表（Hash table，也叫散列表）铲敛，是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)待错。也就是說(shuō)籽孙，它通過(guò)把關(guān)鍵碼值映射到表中一個(gè)位置來(lái)訪問(wèn)記錄，以加快查找的速度火俄。這個(gè)映射函數(shù)叫做散列函數(shù)犯建，存放記錄的數(shù)組叫做散列表。
記錄的存儲(chǔ)位置=f(關(guān)鍵字)
這里的對(duì)應(yīng)關(guān)系f稱為散列函數(shù)瓜客，又稱為哈希（Hash函數(shù)）适瓦，采用散列技術(shù)將記錄存儲(chǔ)在一塊連續(xù)的存儲(chǔ)空間中竿开，這塊連續(xù)存儲(chǔ)空間稱為散列表或哈希表（Hash table）。
哈希表hashtable(key玻熙，value) 就是把Key通過(guò)一個(gè)固定的算法函數(shù)既所謂的哈希函數(shù)轉(zhuǎn)換成一個(gè)整型數(shù)字否彩，然后就將該數(shù)字對(duì)數(shù)組長(zhǎng)度進(jìn)行取余，取余結(jié)果就當(dāng)作數(shù)組的下標(biāo)揭芍，將value存儲(chǔ)在以該數(shù)字為下標(biāo)的數(shù)組空間里胳搞。（或者：把任意長(zhǎng)度的輸入（又叫做預(yù)映射，
pre-image）称杨，通過(guò)散列算法，變換成固定長(zhǎng)度的輸出筷转，該輸出就是散列值姑原。這種轉(zhuǎn)換是一種壓縮映射，也就是呜舒，散列值的空間通常遠(yuǎn)小于輸入的空間锭汛，不同的輸入可能會(huì)散列成相同的輸出，而不可能從散列值來(lái)唯一的確定輸入值袭蝗。簡(jiǎn)單的說(shuō)就是一種將任意長(zhǎng)度的消息壓縮到某一固定長(zhǎng)度的消息摘要的函數(shù)唤殴。）
而當(dāng)使用哈希表進(jìn)行查詢的時(shí)候，就是再次使用哈希函數(shù)將key轉(zhuǎn)換為對(duì)應(yīng)的數(shù)組下標(biāo)到腥，并定位到該空間獲取value朵逝，如此一來(lái)，就可以充分利用到數(shù)組的定位性能進(jìn)行數(shù)據(jù)定位乡范。
數(shù)組的特點(diǎn)是：尋址容易配名，插入和刪除困難；
而鏈表的特點(diǎn)是：尋址困難晋辆，插入和刪除容易渠脉。
那么我們能不能綜合兩者的特性，做出一種尋址容易瓶佳，插入刪除也容易的數(shù)據(jù)結(jié)構(gòu)芋膘？答案是肯定的，這就是我們要提起的哈希表霸饲，哈希表有多種不同的實(shí)現(xiàn)方法为朋，我接下來(lái)解釋的是最常用的一種方法——拉鏈法，我們可以理解為“鏈表的數(shù)組”贴彼，如圖：
左邊很明顯是個(gè)數(shù)組潜腻，數(shù)組的每個(gè)成員包括一個(gè)指針，指向一個(gè)鏈表的頭器仗，當(dāng)然這個(gè)鏈表可能為空融涣，也可能元素很多童番。我們根據(jù)元素的一些特征把元素分配到不同的鏈表中去，也是根據(jù)這些特征威鹿，找到正確的鏈表剃斧，再?gòu)逆湵碇姓页鲞@個(gè)元素。
Hash的應(yīng)用
1忽你、Hash主要用于信息安全領(lǐng)域中加密算法幼东，它把一些不同長(zhǎng)度的信息轉(zhuǎn)化成雜亂的128位的編碼,這些編碼值叫做Hash值.
也可以說(shuō)，Hash就是找到一種數(shù)據(jù)內(nèi)容和數(shù)據(jù)存放地址之間的映射關(guān)系科雳。
2根蟹、查找：哈希表，又稱為散列糟秘，是一種更加快捷的查找技術(shù)简逮。我們之前的查找，都是這樣一種思路：集合中拿出來(lái)一個(gè)元素尿赚，看看是否與我們要找的相等散庶，如果不等，縮小范圍凌净，繼續(xù)查找悲龟。而哈希表是完全另外一種思路：當(dāng)我知道key值以后，我就可以直接計(jì)算出這個(gè)元素在集合中的位置冰寻，根本不需要一次又一次的查找须教！
舉一個(gè)例子，假如我的數(shù)組A中性雄，第i個(gè)元素里面裝的key就是i没卸，那么數(shù)字3肯定是在第3個(gè)位置，數(shù)字10肯定是在第10個(gè)位置秒旋。哈希表就是利用利用這種基本的思想约计，建立一個(gè)從key到位置的函數(shù)，然后進(jìn)行直接計(jì)算查找迁筛。
3煤蚌、Hash表在海量數(shù)據(jù)處理中有著廣泛應(yīng)用。
Hash Table的查詢速度非常的快细卧，幾乎是O(1)的時(shí)間復(fù)雜度尉桩。
hash就是找到一種數(shù)據(jù)內(nèi)容和數(shù)據(jù)存放地址之間的映射關(guān)系。
散列法：元素特征轉(zhuǎn)變?yōu)閿?shù)組下標(biāo)的方法贪庙。
我想大家都在想一個(gè)很嚴(yán)重的問(wèn)題：“如果兩個(gè)字符串在哈希表中對(duì)應(yīng)的位置相同怎么辦蜘犁？”,畢竟一個(gè)數(shù)組容量是有限的，這種可能性很大。解決該問(wèn)題的方法很多吠式，我首先想到的就是用“鏈表”。我遇到的很多算法都可以轉(zhuǎn)化成鏈表來(lái)解決笋粟，只要在哈希表的每個(gè)入口掛一個(gè)鏈表屈扎，保存所有對(duì)應(yīng)的字符串就OK了埃唯。
當(dāng)存儲(chǔ)記錄時(shí)，通過(guò)散列函數(shù)計(jì)算出記錄的散列地址
當(dāng)查找記錄時(shí)鹰晨，我們通過(guò)同樣的是散列函數(shù)計(jì)算記錄的散列地址墨叛，并按此散列地址訪問(wèn)該記錄
關(guān)鍵字——散列函數(shù)（哈希函數(shù)）——散列地址
優(yōu)點(diǎn)：一對(duì)一的查找效率很高；
缺點(diǎn)：一個(gè)關(guān)鍵字可能對(duì)應(yīng)多個(gè)散列地址模蜡；需要查找一個(gè)范圍時(shí)漠趁，效果不好。
散列沖突：不同的關(guān)鍵字經(jīng)過(guò)散列函數(shù)的計(jì)算得到了相同的散列地址哩牍。
好的散列函數(shù)=計(jì)算簡(jiǎn)單+分布均勻（計(jì)算得到的散列地址分布均勻）
哈希表是種數(shù)據(jù)結(jié)構(gòu)棚潦，它可以提供快速的插入操作和查找操作。
優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：不論哈希表中有多少數(shù)據(jù)膝昆，查找、插入叠必、刪除（有時(shí)包括刪除）只需要接近常量的時(shí)間即0(1）的時(shí)間級(jí)荚孵。實(shí)際上，這只需要幾條機(jī)器指令纬朝。
哈希表運(yùn)算得非呈找叮快，在計(jì)算機(jī)程序中共苛，如果需要在一秒種內(nèi)查找上千條記錄通常使用哈希表（例如拼寫檢查器)哈希表的速度明顯比樹快判没，樹的操作通常需要O(N)的時(shí)間級(jí)。哈希表不僅速度快隅茎，編程實(shí)現(xiàn)也相對(duì)容易澄峰。
如果不需要有序遍歷數(shù)據(jù)，并且可以提前預(yù)測(cè)數(shù)據(jù)量的大小辟犀。那么哈希表在速度和易用性方面是無(wú)與倫比的俏竞。
缺點(diǎn)：它是基于數(shù)組的，數(shù)組創(chuàng)建后難于擴(kuò)展堂竟，某些哈希表被基本填滿時(shí)魂毁，性能下降得非常嚴(yán)重，所以程序員必須要清楚表中將要存儲(chǔ)多少數(shù)據(jù)（或者準(zhǔn)備好定期地把數(shù)據(jù)轉(zhuǎn)移到更大的哈希表中出嘹，這是個(gè)費(fèi)時(shí)的過(guò)程）席楚。
元素特征轉(zhuǎn)變?yōu)閿?shù)組下標(biāo)的方法就是散列法。散列法當(dāng)然不止一種税稼，下面列出三種比較常用的：
1烦秩，除法散列法
最直觀的一種垮斯，上圖使用的就是這種散列法，公式：
index = value % 16
學(xué)過(guò)匯編的都知道闻镶，求模數(shù)其實(shí)是通過(guò)一個(gè)除法運(yùn)算得到的甚脉，所以叫“除法散列法”。
2铆农，平方散列法
求index是非常頻繁的操作牺氨，而乘法的運(yùn)算要比除法來(lái)得省時(shí)（對(duì)現(xiàn)在的CPU來(lái)說(shuō)，估計(jì)我們感覺(jué)不出來(lái)）墩剖，所以我們考慮把除法換成乘法和一個(gè)位移操作猴凹。公式：
index = (value * value) >> 28（右移，除以2^28岭皂。記法：左移變大郊霎，是乘。右移變小爷绘，是除书劝。）
如果數(shù)值分配比較均勻的話這種方法能得到不錯(cuò)的結(jié)果，但我上面畫的那個(gè)圖的各個(gè)元素的值算出來(lái)的index都是0——非常失敗土至。也許你還有個(gè)問(wèn)題购对，value如果很大，value
* value不會(huì)溢出嗎陶因？答案是會(huì)的骡苞，但我們這個(gè)乘法不關(guān)心溢出，因?yàn)槲覀兏静皇菫榱双@取相乘結(jié)果楷扬，而是為了獲取index解幽。
3，斐波那契（Fibonacci）散列法
平方散列法的缺點(diǎn)是顯而易見的烘苹，所以我們能不能找出一個(gè)理想的乘數(shù)躲株，而不是拿value本身當(dāng)作乘數(shù)呢？答案是肯定的螟加。
1徘溢，對(duì)于16位整數(shù)而言，這個(gè)乘數(shù)是40503
2捆探，對(duì)于32位整數(shù)而言然爆，這個(gè)乘數(shù)是2654435769
3，對(duì)于64位整數(shù)而言黍图，這個(gè)乘數(shù)是11400714819323198485
這幾個(gè)“理想乘數(shù)”是如何得出來(lái)的呢曾雕？這跟一個(gè)法則有關(guān)，叫黃金分割法則助被，而描述黃金分割法則的最經(jīng)典表達(dá)式無(wú)疑就是著名的斐波那契數(shù)列剖张，即如此形式的序列：0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610切诀，
987, 1597, 2584, 4181, 6765, 10946，…搔弄。另外幅虑，斐波那契數(shù)列的值和太陽(yáng)系八大行星的軌道半徑的比例出奇吻合。
對(duì)我們常見的32位整數(shù)而言顾犹，公式：
index = (value * 2654435769) >> 28
如果用這種斐波那契散列法的話倒庵，那上面的圖就變成這樣了：
注：用斐波那契散列法調(diào)整之后會(huì)比原來(lái)的取摸散列法好很多。
適用范圍
快速查找炫刷，刪除的基本數(shù)據(jù)結(jié)構(gòu)擎宝，通常需要總數(shù)據(jù)量可以放入內(nèi)存。
基本原理及要點(diǎn)
hash函數(shù)選擇浑玛，針對(duì)字符串绍申，整數(shù)，排列顾彰，具體相應(yīng)的hash方法极阅。
碰撞處理，一種是open hashing涨享，也稱為拉鏈法涂屁；另一種就是closed hashing，也稱開地址法灰伟，opened addressing。
散列沖突的解決方案：
1.建立一個(gè)緩沖區(qū)儒旬，把凡是拼音重復(fù)的人放到緩沖區(qū)中栏账。當(dāng)我通過(guò)名字查找人時(shí)，發(fā)現(xiàn)找的不對(duì)栈源，就在緩沖區(qū)里找挡爵。
2.進(jìn)行再探測(cè)。就是在其他地方查找甚垦。探測(cè)的方法也可以有很多種茶鹃。
（1）在找到查找位置的index的index-1，index+1位置查找艰亮，index-2闭翩，index+2查找，依次類推迄埃。這種方法稱為線性再探測(cè)疗韵。
（2）在查找位置index周圍隨機(jī)的查找。稱為隨機(jī)在探測(cè)侄非。
（3）再哈希蕉汪。就是當(dāng)沖突時(shí)流译，采用另外一種映射方式來(lái)查找。
這個(gè)程序中是通過(guò)取模來(lái)模擬查找到重復(fù)元素的過(guò)程者疤。對(duì)待重復(fù)元素的方法就是再哈希：對(duì)當(dāng)前key的位置+7福澡。最后，可以通過(guò)全局變量來(lái)判斷需要查找多少次驹马。我這里通過(guò)依次查找26個(gè)英文字母的小寫計(jì)算的出了總的查找次數(shù)革砸。顯然，當(dāng)總的查找次數(shù)/查找的總元素?cái)?shù)越接近1時(shí)窥翩，哈希表更接近于一一映射的函數(shù)业岁，查找的效率更高。
擴(kuò)展
d-left
hashing中的d是多個(gè)的意思寇蚊，我們先簡(jiǎn)化這個(gè)問(wèn)題笔时，看一看2-left hashing。2-left
hashing指的是將一個(gè)哈希表分成長(zhǎng)度相等的兩半仗岸，分別叫做T1和T2允耿，給T1和T2分別配備一個(gè)哈希函數(shù)，h1和h2扒怖。在存儲(chǔ)一個(gè)新的key時(shí)较锡，同
時(shí)用兩個(gè)哈希函數(shù)進(jìn)行計(jì)算，得出兩個(gè)地址h1[key]和h2[key]盗痒。這時(shí)需要檢查T1中的h1[key]位置和T2中的h2[key]位置蚂蕴，哪一個(gè)
位置已經(jīng)存儲(chǔ)的（有碰撞的）key比較多，然后將新key存儲(chǔ)在負(fù)載少的位置俯邓。如果兩邊一樣多骡楼，比如兩個(gè)位置都為空或者都存儲(chǔ)了一個(gè)key，就把新key
存儲(chǔ)在左邊的T1子表中稽鞭，2-left也由此而來(lái)鸟整。在查找一個(gè)key時(shí)，必須進(jìn)行兩次hash朦蕴，同時(shí)查找兩個(gè)位置篮条。
問(wèn)題實(shí)例（海量數(shù)據(jù)處理）
我們知道hash 表在海量數(shù)據(jù)處理中有著廣泛的應(yīng)用，下面吩抓，請(qǐng)看另一道百度面試題：
題目：海量日志數(shù)據(jù)涉茧，提取出某日訪問(wèn)百度次數(shù)最多的那個(gè)IP。
方案：IP的數(shù)目還是有限的琴拧，最多2^32個(gè)降瞳，所以可以考慮使用hash將ip直接存入內(nèi)存，然后進(jìn)行統(tǒng)計(jì)。
聲明：轉(zhuǎn)自http://blog.csdn.net/duan19920101/article/details/51579136
