本文的學(xué)習(xí)是通過：現(xiàn)代魔法學(xué)院——散列表
1. 散列表
散列表區(qū)分于順序表爸舒，順序表的查找是依次遍歷查詢，而散列表是直接指向具體的位置阁谆。我們需要通過某個(gè)函數(shù)f碳抄，使 value = f(key) 。在java中场绿，關(guān)于散列表如果想要深入理解可以看HashMap的源碼剖效。
2.如何查找
散列過程：1.通過散列函數(shù)計(jì)算某記錄的散列地址，并在此地址存儲(chǔ)該記錄 2.查找的時(shí)候焰盗，通過同樣的散列函數(shù)去計(jì)算散列地址璧尸，并依此訪問數(shù)據(jù)。
散列技術(shù)并不像線性表熬拒、樹爷光、圖，散列表沒法用連線給圖示出來(lái)澎粟，記錄與記錄之間不存在邏輯關(guān)系蛀序。記錄只與關(guān)鍵字有關(guān)，是面向查找的活烙。它的優(yōu)勢(shì)在于簡(jiǎn)化的比較過程徐裸，查的快，效率提升很大啸盏。缺點(diǎn)在于一一對(duì)應(yīng)重贺，并且無(wú)法給表中數(shù)據(jù)進(jìn)行排序。而且回懦，會(huì)有哈希沖突(碰撞)的可能性气笙。我們無(wú)法保證每個(gè)關(guān)鍵字通過散列函數(shù)計(jì)算都能得到不同的結(jié)果，也就是 x≠y 但是f(x)=f(y)怯晕，此時(shí)就發(fā)生了沖突潜圃，我們可以通過一些技術(shù)去處理這種情況。
3.散列函數(shù)
只能去盡可能的避免沖突舟茶，無(wú)法完全規(guī)避秉犹。
設(shè)計(jì)原則：
1.計(jì)算簡(jiǎn)單 （時(shí)間）
2.散列地址均勻 （空間）
具體方法有兩種比較典型：1.直接定址法 2.除留余數(shù)法
現(xiàn)在比較普遍的是DJBX33A蛉谜，沖突少，效率高崇堵，PHP的Hash采用的這個(gè)。
a.直接定址法
取關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址客燕。 f(key) = a × key + b
這個(gè)方法優(yōu)點(diǎn)在于不會(huì)產(chǎn)生沖突鸳劳，而且分布均勻，但是也搓！前提很苛刻赏廓，需要提前知道關(guān)鍵字的分布情況，適合查找表比較小且連續(xù)的情況傍妒。所以并不是特別常用幔摸。
b.除留余數(shù)法
此法為最常用的散列函數(shù)方法，公式為f(key)=key mod p (p<m)
m是容量颤练，mod為求余既忆，關(guān)鍵點(diǎn)在于選擇合適的p，p選取不好沖突可能就比較頻繁嗦玖。
(在學(xué)習(xí)的原文中患雇，有具體的例子，可以點(diǎn)擊文章開頭的鏈接跳過去看)
Q:如何合理取值呢宇挫？
A:如果表長(zhǎng)為m苛吱，p取小于等于m的最小質(zhì)數(shù)，或者是不包含小于20質(zhì)因子的合數(shù)器瘪。
既然沖突是無(wú)法避免的，就要找到?jīng)_突的處理方法橡疼。
a.開放定址法
沒什么是重新計(jì)算一次解決不了的援所，如果有，那就算兩次衰齐。
此方法任斋，一點(diǎn)沖突了，就去尋找下一個(gè)空的散列地址耻涛，只要散列表足夠大废酷，就一定能找到。
具體是使用一種探測(cè)技術(shù)在散列表形成一個(gè)探測(cè)序列抹缕，并以此逐個(gè)單元的查找澈蟆，直到找到給定的關(guān)鍵字，或者碰到一個(gè)開放的地址為止卓研。開放定址法是一種線性探測(cè)法趴俘。
公式：fi(key) = (f(key)+di) MOD m (di=1,2,3,......,m-1)
這里的di是從1開始睹簇，也就是說(shuō)，如果di=1重新計(jì)算之后發(fā)現(xiàn)還是不行寥闪，那么再次計(jì)算就di=2再算太惠。
比如我們有個(gè)集合{12,56,67,16,25,37,22,29,15,47,48,34} (這里就用原文章里面的例子了)
用散列函數(shù) f(key) =- key mod 12
直到25都是無(wú)沖突的，可以直接放進(jìn)去
當(dāng)我們key=37的時(shí)候疲憋，會(huì)發(fā)現(xiàn) 37 mod 12 = 1 凿渊，這個(gè)時(shí)候與關(guān)鍵字25發(fā)生了沖突。
那么要用上面的公式去重新取值 f(37)=(f(37)+1) mod 12 = 2 好的缚柳，那么就把這個(gè)值放到下標(biāo)為2的區(qū)域埃脏。
繼續(xù)放置：
好的接下來(lái)是48，我們計(jì)算f(48)=0 很明顯沒法直接放置了秋忙，我們?cè)偎?f(48)=(f(48)+1)mod12 = 1 依然不行彩掐，我們就di加1繼續(xù)算。f(48)=(f(48)+2)mod12 = 2 還不行灰追，那就繼續(xù)算堵幽，直到發(fā)現(xiàn)6這個(gè)位置。
現(xiàn)在應(yīng)該理解這種方法了吧监嗜，這種方法的缺點(diǎn)也應(yīng)該看出來(lái)了谐檀，很容易造成非同義詞搶占同一個(gè)地址的情況，這種情況叫做堆積裁奇，效率因此下降桐猬。
開放定址法的基本思路，有很多圍繞開放定址法的變形刽肠，這里歸類于同一種溃肪。什么線性探查、平方探查音五、二次探測(cè)惫撰，很多名號(hào)。躺涝。厨钻。
b.鏈地址法 (拉鏈法)
這個(gè)方法和開放定址法差別特別大，所有我個(gè)人認(rèn)為他才是第二種方法坚嗜。有沖突夯膀，可以不換地方嗎？就不能在原地給他處理了嗎苍蔬？诱建？？當(dāng)然可以碟绑！
將所有關(guān)鍵字為同義詞的記錄儲(chǔ)存在單鏈表中俺猿，這個(gè)叫做同義詞子表茎匠，在散列表中只存同義詞子表的頭指針即可。對(duì)于剛才的關(guān)鍵詞集合押袍，在這里表示就是這樣的诵冒，我要去盜圖了！Ｒ瓴选造烁！
這個(gè)思路妙就妙在避免了沖突換址。解決沖突的方法就是將關(guān)鍵字同義詞的節(jié)點(diǎn)鏈接在同一個(gè)鏈表里面午笛。
如果選定的散列表長(zhǎng)度為m，那么可以把散列表定義為一個(gè)由m個(gè)頭指針組成的指針數(shù)組T[0...m-1]苗桂，凡是散列地址為i的節(jié)點(diǎn)药磺，均插入到T[i]為頭指針的單鏈表、這里可以拿HashMap進(jìn)行舉例煤伟，HashMap中有兩個(gè)關(guān)鍵概念癌佩，initialCapacity 和 loadFactor。initialCapacity 是初始化容量便锨，loadFactor是負(fù)載因子围辙。
有一個(gè)公式：initailCapacity*loadFactor=HashMap的容量
所以出來(lái)，負(fù)載因子決定了散列表空間使用程度放案。負(fù)載因子越大姚建，散列表的裝填程度越高，能容納更多的元素吱殉，但是索引效率就會(huì)降低掸冤，反之亦然。
拉鏈法的優(yōu)點(diǎn)在于處理沖突的方式簡(jiǎn)單友雳，并且沒有堆積的情況出現(xiàn)稿湿，非同義詞不會(huì)發(fā)生沖突。鏈表上的節(jié)點(diǎn)空間是動(dòng)態(tài)申請(qǐng)的押赊。拉鏈法中增加的指針域幾乎可以忽略不計(jì)饺藤，節(jié)省空間。
刪除節(jié)點(diǎn)的操作比較容易實(shí)現(xiàn)流礁。這一點(diǎn)是開放定址法無(wú)法企及的涕俗。對(duì)于開放定址法來(lái)說(shuō)，刪除節(jié)點(diǎn)不能簡(jiǎn)單的把被刪節(jié)點(diǎn)的空間置空崇棠，因?yàn)檫@樣會(huì)截?cái)嘣谒筇钊肷⒘斜硗x詞節(jié)點(diǎn)的查找路徑咽袜，也就是我們用同樣的函數(shù)去查，發(fā)現(xiàn)查不到東西了枕稀，而數(shù)據(jù)再散列表中依舊是存在的询刹，開放定址法里面空地址單元代表著查詢失敗谜嫉。所以只能在被刪節(jié)點(diǎn)上做標(biāo)記，讓我們以為節(jié)點(diǎn)空間清出來(lái)了凹联。沐兰。。
拉鏈法的缺點(diǎn)幾乎可以忽略蔽挠，僅僅是指針需要一些額外的空間而已住闯。
