哈希表（散列表）
哈希表监氢，也叫散列表，是根據(jù)關(guān)鍵碼值(key value)直接訪問的數(shù)據(jù)結(jié)構(gòu)藤违。也就是說浪腐，它通過把關(guān)鍵碼值映射到表中的一個位置來訪問記錄，以加快查找的速度顿乒。這個映射函數(shù)叫 散列函數(shù)牛欢，存放記錄的表叫 散列表。
優(yōu)點：一對一的查找效率很高淆游；
缺點：一個關(guān)鍵字可能對應多個散列地址傍睹；需要查找一個范圍時，效果不好犹菱。
實現(xiàn)方式
數(shù)組法
由于數(shù)組是連續(xù)的拾稳，于是可以根據(jù)下標在O(1)的讀寫任何元素，因此它的時間效率是很高的腊脱。我們可以根據(jù)數(shù)組時間效率高的優(yōu)點访得，用數(shù)組來實現(xiàn)簡單的哈希表：把數(shù)組的下標設(shè)為哈希表的鍵值，而把數(shù)組中每一個數(shù)字設(shè)為哈希表的值，這樣每一個下標及數(shù)組中就形成了鍵-值的配對悍抑。有了這樣的哈希表鳄炉，我們就能在O(1)的時間內(nèi)查找，從而快速搜骡、高效的解決很多問題拂盯。
就是把Key通過一個固定的算法函數(shù)既所謂的哈希函數(shù)轉(zhuǎn)換成一個整型數(shù)字，然后就將該數(shù)字對數(shù)組長度進行取余记靡，取余結(jié)果就當作數(shù)組的下標谈竿。將value存儲在以該數(shù)字為下標的數(shù)組空間里。（或者：把任意長度的輸入（又叫做預映射摸吠， pre-image）空凸，通過散列算法，變換成固定長度的輸出寸痢，該輸出就是散列值呀洲。這種轉(zhuǎn)換是一種壓縮映射，也就是啼止，散列值的空間通常遠小于輸入的空間道逗，不同的輸入可能會散列成相同的輸出，而不可能從散列值來唯一的確定輸入值族壳。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數(shù)。）
拉鏈法
數(shù)組的特點是： 尋址容易趣些，插入和刪除困難仿荆；
鏈表的特點是： 尋址困難，插入和刪除容易;
我們能不能綜合兩者的特性坏平，做出一種尋址容易拢操，插入刪除也容易的數(shù)據(jù)結(jié)構(gòu)？答案是肯定的舶替，這就是我們要提起的哈希表令境，哈希表有多種不同的實現(xiàn)方法，我接下來解釋的是最常用的一種方法——拉鏈法顾瞪，我們可以理解為“鏈表的數(shù)組”舔庶。如下圖所示。
左邊很明顯是個數(shù)組陈醒，數(shù)組的每個成員包括一個指針惕橙，指向一個鏈表的頭，當然這個鏈表可能為空钉跷，也可能元素很多弥鹦。我們根據(jù)元素的一些特征把元素分配到不同的鏈表中去，也是根據(jù)這些特征爷辙，找到正確的鏈表彬坏，再從鏈表中找出這個元素朦促。
Hash的應用
Hash主要用于信息安全領(lǐng)域中加密算法，它把一些不同長度的信息轉(zhuǎn)化成雜亂的128位的編碼,這些編碼值叫做Hash值. 也可以說栓始，Hash就是找到一種數(shù)據(jù)內(nèi)容和數(shù)據(jù)存放地址之間的映射關(guān)系务冕。
查找：哈希表，又稱為散列混滔，是一種更加快捷的查找技術(shù)洒疚。我們之前的查找，都是這樣一種思路：集合中拿出來一個元素坯屿，看看是否與我們要找的相等油湖，如果不等，縮小范圍领跛，繼續(xù)查找乏德。而哈希表是完全另外一種思路：當我知道key值以后，我就可以直接計算出這個元素在集合中的位置吠昭，根本不需要一次又一次的查找喊括！
Hash表在海量數(shù)據(jù)處理中有著廣泛應用。
散列函數(shù)
好的散列函數(shù)=計算簡單+分布均勻（計算得到的散列地址分布均勻）
散列沖突：不同的關(guān)鍵字經(jīng)過散列函數(shù)的計算得到了相同的散列地址矢棚。
除法散列法
最直觀的一種郑什，上圖使用的就是這種散列法，公式：
index = value % 16
學過匯編的都知道蒲肋，求模數(shù)其實是通過一個除法運算得到的蘑拯，所以叫“除法散列法”。
平方散列法
求index是非常頻繁的操作兜粘，而乘法的運算要比除法來得省時（對現(xiàn)在的CPU來說申窘，估計我們感覺不出來），所以我們考慮把除法換成乘法和一個位移操作孔轴。公式：
index = (value * value) >> 28 （右移剃法，除以2^28。記法：左移變大路鹰，是乘贷洲。右移變小，是除晋柱。）
如果數(shù)值分配比較均勻的話這種方法能得到不錯的結(jié)果恩脂，但我上面畫的那個圖的各個元素的值算出來的index都是0——非常失敗。也許你還有個問題趣斤，value如果很大俩块，value * value不會溢出嗎？答案是會的，但我們這個乘法不關(guān)心溢出玉凯，因為我們根本不是為了獲取相乘結(jié)果势腮，而是為了獲取index。
斐波那契（Fibonacci）散列法
平方散列法的缺點是顯而易見的漫仆，所以我們能不能找出一個理想的乘數(shù)捎拯，而不是拿value本身當作乘數(shù)呢？答案是肯定的盲厌。
1署照，對于16位整數(shù)而言，這個乘數(shù)是40503
2吗浩，對于32位整數(shù)而言建芙，這個乘數(shù)是2654435769
3，對于64位整數(shù)而言懂扼，這個乘數(shù)是11400714819323198485
這幾個“理想乘數(shù)”是如何得出來的呢禁荸？這跟一個法則有關(guān)，叫黃金分割法則阀湿，而描述黃金分割法則的最經(jīng)典表達式無疑就是著名的斐波那契數(shù)列赶熟，即如此形式的序列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377, 610， 987, 1597, 2584, 4181, 6765, 10946陷嘴，…映砖。另外，斐波那契數(shù)列的值和太陽系八大行星的軌道半徑的比例出奇吻合灾挨。
對我們常見的32位整數(shù)而言邑退，公式：
index = (value * 2654435769) >> 28
如果用這種斐波那契散列法的話，那上面的圖就變成這樣了：
用斐波那契散列法調(diào)整之后會比原來的取摸散列法好很多涨醋。
散列沖突處理法
1.建立一個緩沖區(qū)瓜饥，把凡是拼音重復的人放到緩沖區(qū)中逝撬。當我通過名字查找人時浴骂，發(fā)現(xiàn)找的不對，就在緩沖區(qū)里找宪潮。
2.進行再探測溯警。就是在其他地方查找。探測的方法也可以有很多種狡相。
（1）在找到查找位置的index的index-1梯轻，index+1位置查找，index-2尽棕，index+2查找喳挑，依次類推。這種方法稱為線性再探測。
（2）在查找位置index周圍隨機的查找伊诵。稱為隨機在探測单绑。
（3）再哈希。就是當沖突時曹宴，采用另外一種映射方式來查找搂橙。
參考資料
- [1] 哈希表（散列表）原理詳解
