一直很好奇為啥哈希表(散列表)查詢的速度比數(shù)組快咪啡，然后自己看了幾篇文章首启，有了一點(diǎn)點(diǎn)自己的理解。
一瑟匆、散列表
什么是散列表呢闽坡？散列表其實(shí)是一個(gè)數(shù)組，通過key映射到這個(gè)數(shù)組的下標(biāo)愁溜，直接根據(jù)下標(biāo)獲取該元素疾嗅。數(shù)組中的每一個(gè)元素成為一個(gè)箱子。
當(dāng)我們根據(jù)key來查詢的時(shí)候冕象，首先獲取key的哈希值代承，哈希值是一個(gè)整型數(shù)，然后這個(gè)哈希值 模 數(shù)組的長度渐扮，得到key在這個(gè)數(shù)組的下標(biāo)论悴，這樣就不用遍歷數(shù)組查找key而是直接就拿到了key的下標(biāo)。但是不同的key可能會計(jì)算出相同的哈希值墓律。所以這就需要一個(gè)優(yōu)秀的哈希算法和解決出現(xiàn)生成相同哈希值(散列沖突)的方法膀估。
二、散列算法
散列算法的具體實(shí)現(xiàn)我肯定是不知道的耻讽，但是一個(gè)好的散列算法應(yīng)該具有以下特點(diǎn)：
- 從哈希值不能反向推導(dǎo)出原始數(shù)據(jù)（所以哈希算法也叫單向哈希算法）;
- 對輸入數(shù)據(jù)非常敏感察纯，哪怕原始數(shù)據(jù)只修改了一個(gè) Bit，最后得到的哈希值也大不相同针肥；
- 散列沖突的概率要很小饼记，對于不同的原始數(shù)據(jù)，哈希值相同的概率非常形空怼具则；
- 哈希算法的執(zhí)行效率要盡量高效，針對較長的文本具帮，也能快速地計(jì)算出哈希值博肋。
三低斋、解決散列沖突
解決散列沖突好像比較流行的就是拉鏈法和開放尋址法。
3.1 拉鏈法
所謂拉鏈法就是哈希表數(shù)組中的每一個(gè)箱子都是一個(gè)鏈表束昵，當(dāng)不同key的哈希值相同拔稳，得到相同的下邊，就存在同一個(gè)箱子的鏈表中锹雏，鏈表中每個(gè)元素保存一個(gè)鍵值對巴比。我們知道鏈表其實(shí)查詢速度不是很快，時(shí)間復(fù)雜度為O(n)礁遵，但是這個(gè)鏈表的長度其實(shí)很短轻绞，Java8在鏈表長度大于8時(shí)將鏈表改為紅黑樹∮赌停總結(jié)起來拉鏈法就是將散列沖突的鍵值對放在同一個(gè)鏈表中政勃。
3.2 開放尋址法
所謂開放尋址法就是當(dāng)一個(gè)key獲取了數(shù)組的下標(biāo)，發(fā)現(xiàn)這個(gè)箱子已經(jīng)被別的key占著了兼砖，那就往下找(也可能是按照其他規(guī)則找空的位置)奸远，直到找到空的位置。
四讽挟、擴(kuò)容
最后講講擴(kuò)容懒叛，前面說過哈希表是一個(gè)數(shù)組，那么當(dāng)插入的key多了之后耽梅，沖突就多了起來薛窥，這個(gè)時(shí)候我們就要對數(shù)組進(jìn)行擴(kuò)容了。有一個(gè)成員變量叫做負(fù)載因子來決定什么時(shí)候需要擴(kuò)容眼姐。負(fù)載因子的計(jì)算方法是：負(fù)載因子 = 鍵值對數(shù) ÷ 數(shù)組的長度诅迷，一般來說當(dāng)負(fù)載因子 ≥ 0.72的時(shí)候就需要對的數(shù)組進(jìn)行擴(kuò)容了，通常是擴(kuò)容為之前數(shù)組的兩倍众旗。
對數(shù)組進(jìn)行擴(kuò)容需要重新計(jì)算key的下標(biāo)罢杉，并且需要將鍵值對拷貝到新的數(shù)組，所以還是比較耗時(shí)的贡歧，尤其數(shù)據(jù)量大起來之后屑那。
