特點(diǎn)
? ??散列表用的是數(shù)組支持按照下標(biāo)隨機(jī)訪問(wèn)數(shù)據(jù)的特性环戈，是數(shù)組的一種擴(kuò)展黍特，由數(shù)組演化而來(lái)
? ? 關(guān)鍵詞
? ??????鍵(key)或者關(guān)鍵字
? ??????散列函數(shù)(或“哈希函數(shù)”): Key轉(zhuǎn)化為數(shù)組下標(biāo)的映射方法
? ??????散列函數(shù)(或“哈希函數(shù)”): 散列函數(shù)計(jì)算得到的值
? ? 散列函數(shù)
? ??????它是一個(gè)函數(shù)吃沪，可以把它定義成hash(key)????
????????其中key表示元素的鍵值犀呼，hash(key)的值表示經(jīng)過(guò)散列函數(shù)計(jì)算得到的散列值
? ??????散列函數(shù)設(shè)計(jì)的基本要求
? ??????????1.散列函數(shù)計(jì)算得到的散列值是一個(gè)非負(fù)整數(shù)抡驼；(因?yàn)閿?shù)組下標(biāo)是從0開(kāi)始的)
????????????2.如果key1 = key2争占，那hash(key1) == hash(key2)；
????????????3.如果key1 ≠ key2闷袒，那hash(key1) ≠ hash(key2)坑律。
? ??????散列沖突
? ??????????常用的散列沖突解決方法:??
? ? ? ? ? ? 1.開(kāi)放尋址法(open addressing)
? ??????????????核心思想: 如果出現(xiàn)了散列沖突，我們就重新探測(cè)一個(gè)空閑位置囊骤，將其插入
? ??????????????那如何重新探測(cè)新的位置?
????????????????線性探測(cè)(Linear Probing)
? ? ? ? ? ? ? ? ? ? 往散列表插入數(shù)據(jù)時(shí)晃择，如果某個(gè)數(shù)據(jù)經(jīng)過(guò)散列函數(shù)散列后，存儲(chǔ)位置已經(jīng)被占用
? ? ? ? ? ? ? ? ? ? 我們就從當(dāng)前位置開(kāi)始也物，依次往后查找宫屠，看是否有空閑位置，直到找到為止
? ??????????示例: ?色色塊表示空閑位置滑蚯，橙色色塊表示已經(jīng)存儲(chǔ)數(shù)據(jù)浪蹂，往散列表插入X如下:
? ??????????散列表中查找元素過(guò)程
? ? ? ? ? ? ? ? 通過(guò)散列函數(shù)求出要查找元素的鍵值對(duì)應(yīng)的散列值，
????????????????然后比較數(shù)組中下標(biāo)為散列值的元素和要查找的元素告材。
????????????????如果相等坤次，則說(shuō)明就是我們要找的元素；否則就順序往后依次查找斥赋。
????????????????如果遍歷到數(shù)組中的空閑位置缰猴，還沒(méi)有找到，就說(shuō)明要查找的元素并沒(méi)有在散列表中
? ? ? ? ? ? 散列表中刪除元素過(guò)程
? ??????????????不能把要?jiǎng)h除的元素設(shè)為空(如這個(gè)空閑位置是后來(lái)刪除的疤剑，導(dǎo)致原來(lái)查找算法失效)
????????????????我們可以將刪除的元素滑绒，特殊標(biāo)記為deleted胰舆。
????????????????當(dāng)線性探測(cè)查找時(shí)，遇到標(biāo)記為deleted的空間蹬挤，并不是停下來(lái)，而是繼續(xù)往下探測(cè)
? ? ? ? ? ? 缺陷
? ??????????????當(dāng)散列表中插入的數(shù)據(jù)越來(lái)越多時(shí)棘幸，散列沖突發(fā)生的可能性就會(huì)越來(lái)越大焰扳，
????????????????空閑位置會(huì)越來(lái)越少，線性探測(cè)的時(shí)間就會(huì)越來(lái)越久误续，
? ??????????????極端情況下吨悍，我們可能需要探測(cè)整個(gè)散列表，所以最壞情況下的時(shí)間復(fù)雜度為O(n)
? ??????????????在刪除和查找時(shí)蹋嵌，也會(huì)線性探測(cè)整張散列表育瓜，才能找到要查找或者刪除的數(shù)據(jù)
? ??????????二次探測(cè)(Quadratic probing)
????????????????線性探測(cè)每次探測(cè)的步?是1，那它探測(cè)的下標(biāo)序列就是hash(key)+遞增序號(hào)
? ? ? ? ? ? ? ? 二次探測(cè)探測(cè)步?為原來(lái)的“二次方”栽烂，它探測(cè)的下標(biāo)序列就hash(key)+遞增序號(hào)^2
????????????雙重散列(Double hashing)
? ??????????????不僅要使用一個(gè)散列函數(shù)
? ? ? ? ? ? ? ? 使用一組散列函數(shù)躏仇，先用第一個(gè)散列函數(shù)，如果計(jì)算得到的存儲(chǔ)位置已經(jīng)被占用腺办，
????????????????再用第二個(gè)散列函數(shù)焰手，依次類(lèi)推，直到找到空閑的存儲(chǔ)位置
? ? ? ? ? ? 探測(cè)方法總結(jié)
? ??????????????不管采用哪種探測(cè)方法怀喉，當(dāng)散列表中空閑位置不多時(shí)书妻，散列沖突的概率就會(huì)大大提高
? ??????????????一般情況下，我們會(huì)盡可能保證散列表中有一定比例的空閑槽位
? ??????????????裝載因子(load factor)來(lái)表示空位的多少
? ??????????????????散列表的裝載因子=填入表中的元素個(gè)數(shù)/散列表的?度
? ??????????????裝載因子越大躬拢，說(shuō)明空閑位置越少躲履，沖突越多，散列表的性能會(huì)下降
? ? ? ? ? ? ?2.鏈表法(chaining)
? ??????????????一種更加常用的散列沖突解決辦法
? ??????????????在散列表中聊闯，每個(gè)“桶(bucket)”或“槽(slot)”對(duì)應(yīng)一條鏈表工猜，
????????????????所有散列值相同的元素我們都放到相同槽位對(duì)應(yīng)的鏈表中
? ? ? ? ? ? ? ? 插入只需通過(guò)散列函數(shù)計(jì)算出對(duì)應(yīng)的槽位，將其插入到對(duì)應(yīng)鏈表菱蔬，時(shí)間復(fù)雜度為O(1)
? ??????????????查找/刪除元素時(shí)通過(guò)散列函數(shù)計(jì)算出對(duì)應(yīng)的槽域慷，然后遍歷鏈表查找或者刪除
? ? ? ? ? ? ? ? ? ? 操作時(shí)間復(fù)雜度跟鏈表的?度k成正比，也就是O(k)
????????????????????對(duì)于散列比較均勻的散列函數(shù)來(lái)說(shuō)汗销，理論上k=n/m
????????????????????其中n表示散列中數(shù)據(jù)的個(gè)數(shù)犹褒，m表示散列表中“槽”的個(gè)數(shù)
如何設(shè)計(jì)散列函數(shù)？
? ??首先弛针，散列函數(shù)的設(shè)計(jì)不能太復(fù)雜
? ??其次叠骑，散列函數(shù)生成的值要盡可能隨機(jī)并且均勻分布
? ? 其他，需要考慮因素有關(guān)鍵字的?度削茁、特點(diǎn)宙枷、分布掉房、還有散列表的大小等
裝載因子過(guò)大了怎么辦？
? ??當(dāng)散列表的裝載因子超過(guò)某個(gè)閾值時(shí)慰丛，就需要進(jìn)行擴(kuò)容
? ??裝載因子閾值的設(shè)置要權(quán)衡時(shí)間卓囚、空間復(fù)雜度。
????如果內(nèi)存空間不緊張诅病，對(duì)執(zhí)行效率要求很高哪亿，可以降低負(fù)載因子的閾值；
????相反贤笆，如果內(nèi)存空間緊張蝇棉，對(duì)執(zhí)行效率要求又不高，可以增加負(fù)載因子的值芥永，甚至可以大于1
如何避免低效地?cái)U(kuò)容篡殷？
? ??為了解決一次性擴(kuò)容耗時(shí)過(guò)多的情況，可以將擴(kuò)容操作穿插在插入操作的過(guò)程中埋涧，分批完成板辽。
????當(dāng)裝載因子觸達(dá)閾值之后，我們只申請(qǐng)新空間棘催，但并不將老的數(shù)據(jù)搬移到新散列表中
? ??通過(guò)均攤的方法戳气，將一次性擴(kuò)容的代價(jià)均攤到多次操作中，避免一次性擴(kuò)容耗時(shí)過(guò)多的情況巧鸭。
????這種實(shí)現(xiàn)方式瓶您，任何情況下，插入一個(gè)數(shù)據(jù)的時(shí)間復(fù)雜度都是O(1)
如何選擇沖突解決方法纲仍？
? ??1.開(kāi)放尋址法:? ??
? ??????當(dāng)數(shù)據(jù)量比較小呀袱、裝載因子小的時(shí)候，適合采用開(kāi)放尋址法郑叠。
????????這也是Java中ThreadLocalMap使用開(kāi)放尋址法解決散列沖突的原因
? ??2.鏈表法:?
? ??????鏈表法對(duì)內(nèi)存的利用率比開(kāi)放尋址法要高(鏈表結(jié)點(diǎn)可以在需要的時(shí)候再創(chuàng)建)
? ??????鏈表法比起開(kāi)放尋址法夜赵，對(duì)大裝載因子的容忍度更高
? ??????基于鏈表的散列沖突處理方法比較適合存儲(chǔ)大對(duì)象、大數(shù)據(jù)量的散列表乡革，
????????而且比起開(kāi)放尋址法寇僧，它更加靈活，支持更多的優(yōu)化策略沸版，比如用紅黑樹(shù)代替鏈表
? ??????于是在JDK1.8版本中嘁傀，為了對(duì)HashMap做進(jìn)一步優(yōu)化，引入了紅黑樹(shù)视粮。
? ? ? ? 當(dāng)鏈表?度太?(默認(rèn)為8)時(shí)细办，鏈表轉(zhuǎn)為紅黑樹(shù)，利用紅黑樹(shù)快速增刪改查來(lái)提高性能;
????????當(dāng)紅黑樹(shù)結(jié)點(diǎn)個(gè)數(shù)少于8時(shí)蕾殴，紅黑樹(shù)轉(zhuǎn)為鏈表笑撞，小數(shù)據(jù)量時(shí)紅黑樹(shù)要維護(hù)平衡岛啸，性能無(wú)優(yōu)勢(shì)
工業(yè)級(jí)的散列表應(yīng)該具有哪些特性？
? ? 1.支持快速的查詢(xún)茴肥、插入坚踩、刪除操作；
? ? 2.內(nèi)存占用合理瓤狐，不能浪費(fèi)過(guò)多的內(nèi)存空間瞬铸；
? ? 3.性能穩(wěn)定，極端情況下芬首，散列表的性能也不會(huì)退化到無(wú)法接受的情況
如何實(shí)現(xiàn)這樣一個(gè)散列表呢？
? ? 1.設(shè)計(jì)一個(gè)合適的散列函數(shù)逼裆；
? ? 2.定義裝載因子閾值郁稍，并且設(shè)計(jì)動(dòng)態(tài)擴(kuò)容策略；
? ? 3.選擇合適的散列沖突解決方法
散列表和鏈表都是如何組合起來(lái)使用?
? ??LRU緩存淘汰算法
? ? ? ? 借助鏈表+散列表將時(shí)間復(fù)雜度降低為O(1)
? ? ? ? 單純鏈表實(shí)現(xiàn)LRU緩存淘汰算法步驟
? ??????????維護(hù)一個(gè)按照訪問(wèn)時(shí)間從大到小有序排列的鏈表結(jié)構(gòu)胜宇。
????????????因緩存大小有限耀怜，當(dāng)緩存空間不夠，需要淘汰一個(gè)數(shù)據(jù)時(shí)桐愉，直接將鏈表頭部的結(jié)點(diǎn)刪除
? ??????????當(dāng)要緩存某個(gè)數(shù)據(jù)時(shí)财破，先在鏈表中查找這個(gè)數(shù)據(jù)。
????????????如果沒(méi)有找到从诲，則直接將數(shù)據(jù)放到鏈表的尾部左痢；
????????????如果找到了，我們就把它移動(dòng)到鏈表的尾部系洛。
????????????因?yàn)椴檎覕?shù)據(jù)需要遍歷鏈表俊性，所以用鏈表實(shí)現(xiàn)的時(shí)間復(fù)雜度為O(n)
? ? ? ? ? ? 總結(jié)以上步驟,總共有三步,都涉及到查找,只用鏈表實(shí)現(xiàn)到時(shí)間復(fù)雜度為O(n)
? ??????????????往緩存中添加一個(gè)數(shù)據(jù)
? ??????????????從緩存中刪除一個(gè)數(shù)據(jù)
? ??????????????在緩存中查找一個(gè)數(shù)據(jù)
? ? ? ? 鏈表+散列表實(shí)現(xiàn)LUR緩存淘汰算法步驟
????????????雙向鏈表存儲(chǔ)數(shù)據(jù)，每個(gè)結(jié)點(diǎn)包括數(shù)據(jù)(data)描扯、前驅(qū)指針(prev)定页、后繼指針(next)、hnext
? ??????????因?yàn)槲覀兊纳⒘斜硎峭ㄟ^(guò)鏈表法解決散列沖突的绽诚，所以每個(gè)結(jié)點(diǎn)會(huì)在兩條鏈中
? ??????????一個(gè)鏈?zhǔn)莿倓偽覀兲岬降碾p向鏈表典徊，另一個(gè)鏈?zhǔn)巧⒘斜碇械睦湣?/p>
????????????前驅(qū)和后繼指針是將結(jié)點(diǎn)串在雙向鏈表中，hnext指針是將結(jié)點(diǎn)串在散列表的拉鏈中
? ??????????這整個(gè)過(guò)程涉及的查找操作都可以通過(guò)散列表來(lái)完成
? ??????????其他的操作恩够，比如刪除頭結(jié)點(diǎn)卒落、鏈表尾部插入數(shù)據(jù)等，可以在O(1)的時(shí)間復(fù)雜度內(nèi)完成
? ? ? ? ? ? 添加蜂桶、查找导绷、刪除三個(gè)操作的時(shí)間復(fù)雜度都為O(1)
? ??????????至此通過(guò)組合使用，實(shí)現(xiàn)了一個(gè)高效的屎飘、支持LRU緩存淘汰算法的緩存系統(tǒng)原型
? ? Java LinkedHashMap
????????HashMap底層是通過(guò)散列表這種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的妥曲。
????????而LinkedHashMap是通過(guò)雙向鏈表和散列表這兩種數(shù)據(jù)結(jié)構(gòu)組合實(shí)現(xiàn)的贾费。
????????LinkedHashMap中的“Linked”實(shí)際上是指的是雙向鏈表，并非指用鏈表法解決散列沖突
