2.9.1散列思想
????散列表用的是數(shù)組支持按照下標(biāo)隨機(jī)訪問(wèn)數(shù)據(jù)的特性，所以散列表其實(shí)就是數(shù)組的一種擴(kuò)展横堡，由數(shù)組演化而來(lái)莺丑。
????舉一個(gè)簡(jiǎn)單的例子：89小學(xué)生參加運(yùn)功會(huì)比賽，每個(gè)人都有一個(gè)參賽號(hào)结榄，參賽號(hào)是通過(guò)年級(jí)班級(jí)加序號(hào)來(lái)組成中贝，例如051101，表示五年級(jí)11班臼朗，后面是01-89編號(hào)邻寿。想要存儲(chǔ)選手的信息，來(lái)支持通過(guò)編號(hào)快速查詢選手信息视哑。不可以直接把編號(hào)當(dāng)做數(shù)組的下標(biāo)绣否，但是可以截取編號(hào)的后兩位來(lái)作為數(shù)組下標(biāo)。這時(shí)：參賽選手的編號(hào)就是鍵或者關(guān)鍵字挡毅，通過(guò)把參賽編號(hào)轉(zhuǎn)換成數(shù)組下標(biāo)的映射方法就叫做散列函數(shù)蒜撮，而通過(guò)散列函數(shù)計(jì)算得到的值就叫做散列值。
散列函數(shù)設(shè)計(jì)的基本要求：
①．散列函數(shù)計(jì)算得到的散列值是一個(gè)非負(fù)整數(shù)跪呈。
②．如果key1=key2段磨，那hash(key1)==hash(key2);
③．如果key1≠key2，那hash(key1) ≠ hash(key2);
????第三點(diǎn)看起來(lái)合情合理耗绿，要想找到一個(gè)不同的key對(duì)應(yīng)的散列值都不一樣的散列函數(shù)幾乎是不可能的苹支，即便是業(yè)界著名的MD5，SHA误阻，CRC等哈希算法也無(wú)法完全避免這種散列沖突债蜜。而且，數(shù)組的存儲(chǔ)空間有限究反，也會(huì)加大這種散列沖突的概率寻定。常用的解決散列沖突的方法有兩類：開放尋址法、鏈表法奴紧。
2.9.2開放尋址法
????開放尋址法核心思想是如果出現(xiàn)了散列沖突特姐，就重新檢測(cè)一個(gè)空閑位置，將其插入黍氮，而如何檢測(cè)新的位置唐含，可以運(yùn)用線性探測(cè)：當(dāng)往散列表中插入數(shù)據(jù)時(shí)，如果某個(gè)數(shù)據(jù)經(jīng)過(guò)散列函數(shù)散列之后沫浆，存儲(chǔ)位置已經(jīng)被占用了捷枯，就從頭開始依次往后查找，看是否有空閑位置专执，直到找到為止淮捆。如下圖來(lái)表示：橙色代表已填充，黃色代表未填充。x經(jīng)過(guò)散列函數(shù)計(jì)算后攀痊，被散列到位置下標(biāo)為7的位置桐腌，但在7的位置上已經(jīng)有了數(shù)據(jù)，于是就從表頭開始找苟径，直到找到空閑位置2案站，于是將其插入到這個(gè)位置上。
????在散列表中查找元素有點(diǎn)類似于插入棘街，通過(guò)散列函數(shù)求出要查找的元素的鍵值對(duì)應(yīng)的散列值蟆盐，然后比較數(shù)組中下標(biāo)為鍵值的元素和要查找的元素，如果相等遭殉，就是要查找的元素石挂，如果不相等，就從頭按照順序依次查找险污，如果遍歷到數(shù)組中空閑位置痹愚，還沒(méi)有找到，就說(shuō)明要查找的元素不在散列表中（因?yàn)樯鲜霾迦脒^(guò)程罗心，如果出現(xiàn)散列沖突的情況里伯，就是從頭比遍歷插入到空閑位置了）。而當(dāng)散列表中數(shù)據(jù)越來(lái)越多時(shí)渤闷，散列沖突的可能性越來(lái)越高疾瓮，空閑位置會(huì)越來(lái)越少，線性檢測(cè)時(shí)間就越來(lái)越久飒箭。最壞情況下時(shí)間復(fù)雜度會(huì)達(dá)到O(n)狼电。為了保證散列表的操作效率，一般情況下弦蹂，會(huì)盡可能的保存散列表中有一定比例的空閑槽位肩碟，用裝載因子來(lái)表示空位的多少。裝載因子越大表示空閑位置越少凸椿，沖突越多削祈，散列表的性能會(huì)下降。
? ??散列表的裝載因子=填入表中的元素個(gè)數(shù) / 散列表的長(zhǎng)度
????而如果進(jìn)行刪除操作脑漫，不可以單純的直接將元素刪除髓抑，因?yàn)橹苯觿h除的話查找的時(shí)候就是出問(wèn)題，所以會(huì)將刪除掉的元素進(jìn)行特殊標(biāo)記為delected优幸。當(dāng)線性探測(cè)時(shí)吨拍，遇到delected不會(huì)停下來(lái)，而會(huì)繼續(xù)向前檢測(cè)网杆。
????開發(fā)地址法中除了線性探測(cè)還有兩種經(jīng)典的方法羹饰，二次探測(cè)和雙重散列伊滋，所謂二次探測(cè)和線性探測(cè)很像，線性探測(cè)每次步長(zhǎng)是1队秩，二次探測(cè)步長(zhǎng)變成了原來(lái)的二次方笑旺。雙重散列意思就是不止一個(gè)散列函數(shù)，第一個(gè)散列函數(shù)計(jì)算得到的存儲(chǔ)位置如果已經(jīng)被占用刹碾，就用第二個(gè)散列函數(shù)進(jìn)行計(jì)算...第三個(gè)燥撞，第四個(gè)，直到找到空閑的存儲(chǔ)位置迷帜。
????線性探測(cè)的下表序列就是：hash(key)+0,hash(key)+1,hash(key)+2...
????二次探測(cè)的下標(biāo)序列就是：hash(key)+0,hash(key)+12,hash(key)+22...
2.9.3鏈表法
????鏈表法要更加常用，而且簡(jiǎn)單得多色洞，如下圖戏锹，這就是之前面試時(shí)候所說(shuō)的數(shù)組形的鏈表，在散列表中每個(gè)“槽”會(huì)對(duì)應(yīng)一條鏈表火诸，所有散列值相同的元素都放到相同槽位對(duì)應(yīng)的鏈表中锦针。這樣的話，插入的時(shí)間復(fù)雜度是O(1)置蜀，插入和刪除的時(shí)間復(fù)雜度是和鏈表的長(zhǎng)度相關(guān)的奈搜，假設(shè)鏈表長(zhǎng)度為k，時(shí)間復(fù)雜度就是O(k)盯荤，對(duì)于散列比較均勻的散列函數(shù)馋吗，假設(shè)n表示散列中元素?cái)?shù)，m表示“槽數(shù)”秋秤，理論上k=n/m宏粤。
2.9.4課后思考
①假設(shè)有10萬(wàn)條URL，如何根據(jù)訪問(wèn)次數(shù)給URL進(jìn)行排序灼卢。
????以URL為key绍哎，訪問(wèn)次數(shù)為value存放到散列表中，同時(shí)記錄訪問(wèn)次數(shù)的最大值K鞋真，時(shí)間復(fù)雜度為O(n)崇堰，如果K不是很大，可以用桶排序涩咖，如果K很大海诲，比如說(shuō)大于10萬(wàn)，可以用快排抠藕。
②有兩個(gè)字符串?dāng)?shù)組饿肺，每個(gè)數(shù)組大約有10 萬(wàn)條字符串，如何快速找出兩個(gè)數(shù)組中相同的字符串盾似？
????將第一個(gè)數(shù)組存放到一個(gè)散列表中敬辣，以字符串為key雪标，以出現(xiàn)次數(shù)為value，然后遍歷第二個(gè)數(shù)組溉跃，以第二個(gè)數(shù)組的字符串為key在散列表中查找村刨，如果value大于0，則說(shuō)明存在相同的字符串撰茎，時(shí)間復(fù)雜度為O(n)嵌牺。
2.9.5如何打造一個(gè)工業(yè)級(jí)水平的散列表？
????在極端情況下龄糊，散列表時(shí)間復(fù)雜度可能會(huì)達(dá)到O(n)逆粹，而一個(gè)工業(yè)級(jí)別的散列表一定是要避免這些問(wèn)題的，它跟散列函數(shù)炫惩、裝載因子僻弹、解決散列沖突都有關(guān)系。
? ??散列函數(shù)：散列函數(shù)的設(shè)計(jì)不能太復(fù)雜他嚷，過(guò)于復(fù)雜蹋绽，計(jì)算時(shí)間長(zhǎng)，一定會(huì)影響效率筋蓖，散列函數(shù)分布要均勻卸耘。對(duì)于數(shù)據(jù)集合變動(dòng)不頻繁的靜態(tài)集合來(lái)說(shuō)，比較容易設(shè)計(jì)出完美的散列函數(shù)粘咖，因?yàn)楫吘箶?shù)據(jù)都是已知的蚣抗。
? ??裝載因子：裝載因子過(guò)大，在查詢時(shí)可能要多次尋址涂炎，或者會(huì)有很長(zhǎng)的鏈表忠聚，結(jié)果就會(huì)很慢。對(duì)于動(dòng)態(tài)散列表來(lái)說(shuō)唱捣，數(shù)據(jù)集合頻繁變動(dòng)两蟀，所以要申請(qǐng)一個(gè)足夠大的散列表，隨著數(shù)據(jù)量不斷增多震缭，裝載因子不斷變大赂毯，散列沖突到不可接受，就要進(jìn)行動(dòng)態(tài)擴(kuò)容拣宰。針對(duì)數(shù)組的擴(kuò)容党涕，數(shù)據(jù)搬移比較簡(jiǎn)單，但是散列表的擴(kuò)容就比較麻煩了巡社，因?yàn)樾枰匦掠?jì)算每個(gè)數(shù)據(jù)的存儲(chǔ)位置膛堤。對(duì)于動(dòng)態(tài)散列表，隨著數(shù)據(jù)的刪除晌该，散列表中的數(shù)據(jù)量減少肥荔，裝載因子減小绿渣，如果對(duì)于空間消耗十分敏感，可以進(jìn)行動(dòng)態(tài)縮容燕耿。裝載因子閾值的設(shè)置要權(quán)衡時(shí)間中符、空間。如果對(duì)空間要求不高誉帅，可以把閾值設(shè)小一點(diǎn)淀散，反之...
1）如何避免低效擴(kuò)容：
????在一個(gè)動(dòng)態(tài)列表進(jìn)行插入數(shù)據(jù)，最好情況時(shí)間復(fù)雜度是O(1)蚜锨，最壞情況是需要進(jìn)行擴(kuò)容档插，這次會(huì)特別的慢，最壞情況時(shí)間復(fù)雜度是O(n)踏志，用攤還分析法進(jìn)行分析阀捅，平均情況時(shí)間復(fù)雜度就是O(1)。但是對(duì)于用戶體驗(yàn)來(lái)說(shuō)针余，偶爾的一次會(huì)特別慢到讓人無(wú)法接受，所以這樣就不合適了凄诞。為了解決一次性擴(kuò)容耗時(shí)過(guò)多的問(wèn)題圆雁，可以將擴(kuò)容穿插在插入操作中，分批完成帆谍，當(dāng)裝載因子達(dá)到閾值時(shí)伪朽，只申請(qǐng)新空間，但不進(jìn)行搬移汛蝙，在插入新數(shù)據(jù)時(shí)烈涮，將新數(shù)據(jù)插入到新的散列表中，同時(shí)從舊的散列表中搬移一個(gè)數(shù)據(jù)到新散列表窖剑，這樣就快多了坚洽。
????在此期間的查詢操作，為了兼顧新老散列表中的數(shù)據(jù)西土，先從新散列表中進(jìn)行查詢讶舰，找不到再?gòu)呐f散列表中進(jìn)行查詢。
2）如何選擇散列沖突解決方法：
????在java中LinkedHashMap采用鏈表法解決沖突需了，ThreadLocalMap采用開放尋址法解決散列沖突跳昼。
????1.開放尋址法：優(yōu)點(diǎn)是可以有效地利用CPU緩存加快查詢速度，而且序列化起來(lái)簡(jiǎn)單肋乍。缺點(diǎn)是刪除數(shù)據(jù)比較麻煩鹅颊，而且數(shù)據(jù)全部存儲(chǔ)在一個(gè)數(shù)組中，沖突解決的代價(jià)更高墓造，而且裝載因子不能太大堪伍。適合用于數(shù)據(jù)量較小锚烦，裝載因子小
????2.鏈表法：優(yōu)點(diǎn)是對(duì)于內(nèi)存的利用率要比開放尋址法高，因?yàn)殒湵斫Y(jié)點(diǎn)可以需要的時(shí)候在創(chuàng)建杠娱，而不需要事先申請(qǐng)挽牢，這也是鏈表比數(shù)組好的地方，鏈表法對(duì)裝載因子的容忍度更高摊求，只要散列函數(shù)分布均勻禽拔，即使鏈表長(zhǎng)度很大，雖然查找效率有所下降室叉，但是還是比順序查找快睹栖。缺點(diǎn)是鏈表法會(huì)對(duì)內(nèi)存有一些浪費(fèi)，因?yàn)橐鎯?chǔ)指針茧痕，對(duì)于比較小的對(duì)象的存儲(chǔ)野来，是比較消耗內(nèi)存的，當(dāng)然如果對(duì)象很大就無(wú)所謂了踪旷。實(shí)際上曼氛，對(duì)鏈表法進(jìn)行改造，可以實(shí)現(xiàn)更高效的散列表令野，就是將鏈表法中的鏈表替換成更高效的數(shù)據(jù)結(jié)構(gòu)舀患，比如說(shuō)跳表，紅黑樹气破。這樣就算是極端情況下聊浅，所有的數(shù)據(jù)全都散列到一個(gè)桶里，時(shí)間復(fù)雜度也是O(logn)现使。適合大對(duì)象低匙，大數(shù)據(jù)量的散列表。而且更靈活
3）工業(yè)級(jí)散列表舉例分析：來(lái)分析HashMap
????a.?初始大刑夹狻：HashMap的初始大小是16顽冶，如果事先知道數(shù)據(jù)量大概有多大，可以修改默認(rèn)初始大小殴胧，避免動(dòng)態(tài)擴(kuò)容渗稍，提高性能。
????b.?裝載因子和動(dòng)態(tài)擴(kuò)容：最大裝載因子是0.75团滥，當(dāng)超過(guò)0.75時(shí)就會(huì)自動(dòng)擴(kuò)容竿屹，每次擴(kuò)容為之前的兩倍。
????c.?散列沖突解決方法：鏈表法上進(jìn)行改進(jìn)灸姊，JDK1.8中HashMap的散列沖突解決方法是鏈表法（默認(rèn)值為8）拱燃，鏈表就轉(zhuǎn)換成紅黑樹，當(dāng)結(jié)點(diǎn)個(gè)數(shù)小于6時(shí)力惯，又會(huì)轉(zhuǎn)換回鏈表碗誉，因?yàn)樵跀?shù)據(jù)量較小時(shí)召嘶，紅黑樹優(yōu)勢(shì)并不明顯。
????d.?散列函數(shù)：
4）工業(yè)級(jí)的散列表應(yīng)該具有什么特點(diǎn)
????a. 支持快速查詢弄跌、插入、刪除操作尝苇；
????b. 內(nèi)存占用合理铛只，不能浪費(fèi)過(guò)多空間；
????c. 性能穩(wěn)定糠溜，極端情況下淳玩，散列表的性能也不會(huì)退化到無(wú)法接受的情況。
5）如何實(shí)現(xiàn)這樣的一個(gè)散列表
????a. 設(shè)計(jì)一個(gè)合適的散列函數(shù)
????b. 定義裝載因子閾值非竿，并且設(shè)計(jì)動(dòng)態(tài)擴(kuò)容策略
????c. 選擇合適的散列沖突解決方法
2.9.5散列表和鏈表
1）LRU緩存算法
????當(dāng)要緩存某個(gè)數(shù)據(jù)時(shí)蜕着，先在鏈表中查找這個(gè)數(shù)據(jù)，如果有的話就從原位置刪除红柱，把他插入到頭部承匣，如果沒(méi)有的話就直接插入在頭部，如果緩存空間已滿锤悄，就把尾結(jié)點(diǎn)數(shù)據(jù)刪除悄雅，而仍將，然后將新的數(shù)據(jù)插入到鏈表的頭部铁蹈。這樣的話緩存的時(shí)間復(fù)雜度為O(n)。
????一個(gè)緩存系統(tǒng)一般包括三個(gè)操作：往緩存中添加一個(gè)數(shù)據(jù)众眨、從緩存中刪除一個(gè)數(shù)據(jù)握牧、在緩存中查找數(shù)據(jù)，這三個(gè)操作都涉及“查找”操作娩梨。要實(shí)現(xiàn)LRU算法沿腰，如果單純采用鏈表的話，時(shí)間復(fù)雜度就是O(n)狈定，如果將散列表和鏈表兩種數(shù)據(jù)結(jié)構(gòu)結(jié)合颂龙，可以將這三個(gè)操作的時(shí)間復(fù)雜度都降到O(1)。
????如上圖通過(guò)雙向鏈表來(lái)存儲(chǔ)數(shù)據(jù)纽什，鏈表中每個(gè)結(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)data措嵌，前驅(qū)指針pre，后繼指針next芦缰，還新增一個(gè)字段hnext企巢。因?yàn)樯⒘斜硗ㄟ^(guò)鏈表法解決散列沖突，所以每個(gè)結(jié)點(diǎn)會(huì)在兩條鏈中让蕾。一個(gè)是剛剛提到的雙向鏈表浪规，另一個(gè)鏈?zhǔn)巧⒘斜碇械睦溁蛱Ｇ膀?qū)和后繼指針為了將結(jié)點(diǎn)串在雙向鏈表中，hnext指針為了將結(jié)點(diǎn)串在散列表的拉鏈中笋婿。在雙向鏈表中誉裆，所以時(shí)間是從大到小的，在hnext的拉表中缸濒，時(shí)間也是從左到右依次減小的足丢。（都是因?yàn)樵谶@里優(yōu)先的都是設(shè)定在鏈表的頭結(jié)點(diǎn)）
? ??查找數(shù)據(jù)：通過(guò)散列表可以很快的在散列表中查到一個(gè)數(shù)據(jù)，查到之后還需要將他移動(dòng)到雙向鏈表的頭部绍填。
? ??刪除數(shù)據(jù)：找到要查找數(shù)據(jù)的結(jié)點(diǎn)哗脖，借助散列表，可以在O(1)時(shí)間復(fù)雜度內(nèi)找到要?jiǎng)h除結(jié)點(diǎn)预麸，因?yàn)殒湵硎请p向鏈表夜郁，查找的時(shí)間復(fù)雜度是O(1)，所以在雙向鏈表中卿闹，刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度是O(1)揭糕。（刪除數(shù)據(jù)，這里如果是要?jiǎng)h除雙向鏈表中的某個(gè)值锻霎，不是也得從頭遍歷著角，這樣的話時(shí)間復(fù)雜度不應(yīng)該是O(n)嗎）
? ??添加數(shù)據(jù)：添加數(shù)據(jù)比較麻煩，首先看這個(gè)數(shù)據(jù)是否在緩存中旋恼。如果已經(jīng)在其中吏口，需要將他移動(dòng)到雙向鏈表的頭部，如果不在冰更，看緩存有沒(méi)有滿产徊，如果滿的情況下，將雙向鏈表的尾結(jié)點(diǎn)刪除蜀细，然后將它放在頭結(jié)點(diǎn)位置舟铜；如果沒(méi)有滿，直接將數(shù)據(jù)放在鏈表頭結(jié)點(diǎn)奠衔。查找谆刨、刪除、插入數(shù)據(jù)的平均時(shí)間復(fù)雜度都是O(1)归斤，所以這樣就實(shí)現(xiàn)了一個(gè)高效的LRU緩存淘汰算法的緩存系統(tǒng)模型痊夭。
2）Redis的有序集合
????在redis的有序集合中，每個(gè)成員對(duì)象有兩個(gè)重要屬性官册，key（鍵值）和score（分值）生兆。不僅會(huì)通過(guò)score來(lái)查找數(shù)據(jù)，還可以通過(guò)key來(lái)查找數(shù)據(jù)。
????比如有一個(gè)用戶積分排行榜：包含ID鸦难、姓名和積分的用戶信息就是成員對(duì)象根吁，用戶的ID就是key，積分就是score合蔽』鞯校可以通過(guò)ID來(lái)查找積分，也可以通過(guò)積分區(qū)間來(lái)查找ID或者姓名信息拴事。
????細(xì)化一下redis有序集合的操作沃斤，①添加一個(gè)成員對(duì)象②按照鍵值來(lái)刪除一個(gè)成員對(duì)象③按照鍵值來(lái)查找一個(gè)成員對(duì)象④按照分值區(qū)間，查找某個(gè)區(qū)間內(nèi)的成員對(duì)象⑤按照分值從小到大排序成員變量刃宵。
????如果按照分值將成員對(duì)象組織成跳表的結(jié)構(gòu)衡瓶，那如果按照鍵值來(lái)刪除、查詢對(duì)象就會(huì)變得很慢牲证，對(duì)此的解決方法和LRU淘汰算法類似哮针，可以按照鍵值在構(gòu)建一個(gè)散列表，這樣按照key來(lái)進(jìn)行操作時(shí)間復(fù)雜度就變?yōu)镺(1)了坦袍。所以目前來(lái)看redis的有序集合是通過(guò)跳表和散列表這種組合結(jié)構(gòu)來(lái)實(shí)現(xiàn)的十厢。（后續(xù)還有一種操作，比如說(shuō)查找成員對(duì)象的排名捂齐，又是通過(guò)其他的結(jié)構(gòu)來(lái)實(shí)現(xiàn)的）蛮放。
3）LinkedHashMap
????LinkedHashMap相對(duì)于HashMap又多了一個(gè)Linked，那么是不是通過(guò)鏈表法來(lái)解決散列沖突的HashMap奠宜，是這樣但不僅僅是這樣包颁，的確是通過(guò)鏈表法來(lái)解決散列沖突，Linked其實(shí)指的是雙向鏈表压真，看一下下面這段代碼：
????由上可以發(fā)現(xiàn)LinkedHashMap在每次調(diào)用put()函數(shù)時(shí)徘六，都會(huì)將數(shù)據(jù)加到鏈表的尾部，舉例說(shuō)明來(lái)看榴都，而且它不僅支持按照插入順序來(lái)遍歷數(shù)據(jù)，還按照訪問(wèn)順序來(lái)遍歷數(shù)據(jù)漠其。所以才會(huì)3,1,5,2變?yōu)?,2,3,5嘴高。可以發(fā)現(xiàn)LinkedHashMap本身就是支持LRU緩存淘汰策略的緩存系統(tǒng)（只不過(guò)最近訪問(wèn)數(shù)據(jù)都是放在尾部和屎，實(shí)現(xiàn)原理是一樣的）
（本文是個(gè)人聽(tīng)課筆記拴驮，不少東西摘取于王爭(zhēng)老師的原文，原文鏈接http://gk.link/a/10aMZ）
