小白： 慶哥，什麼是哈希表？這個哈希好熟悉，記得好像有HashMap和HashTable之類的吧，這是一樣的嘛？
慶哥： 這個哈希确實經常見，足以說明它是個使用非常頻繁的玩意兒，而且像你說的HashMap和HashTable之類的與哈希這個詞肯定是有關系的，那哈希是個啥玩意啊，這個咱們還是得先來搞明白啥是個哈希表。
我們看看百科解釋吧：
散清單（Hash table，也叫哈希表），是根據鍵（Key）而直接通路在記憶體存儲位置的資料結構。也就是說，它通過計算一個關于鍵值的函數，将所需查詢的資料映射到表中一個位置來通路記錄，這加快了查找速度。這個映射函數稱做散列函數，存放記錄的數組稱做散清單。
怎麼樣？看到這個，你知道哈希表是什麼了嘛？
小白： 我之前是對哈希表一竅不通啊，不過看了這個百科的解釋，我知道如下這些關于哈希表的簡單知識點：
1、哈希表其實也叫散清單，兩個是一個玩意，英文是Hash Table
2、哈希表是一個資料結構
這兩個概念是比較清晰的，至于其他的說什麼映射函數叫做散列函數，存放記錄的數組叫做散清單這個就有點模糊了，尤其說存放記錄的數組稱為散清單，那意思是哈希表是個數組？
慶哥： 首先你說的很清晰的兩點說的是很準确的，哈希表也叫做散清單，這隻不過是叫法而已，英文單詞是Hash table，看到這個英文單詞基本上就能猜到，哈希表其實就是直接根絕英文單詞音譯過來的，至此你應該知道了啥是哈希了吧，對于另外一點，那就很重要了，那就是<code>哈希表其實是一種資料結構。</code>
要知道資料結構有很多中，每一種都有各自的特點，那麼哈希表既然也是一種資料結構，那它有什麼特點呢？按照百科的解釋，我們大緻能知道：可以根據一個key值來直接通路資料，是以查找速度快
對了，你知道最基本的幾個資料結構中，哪個的查詢效率是最高的嘛？
小白： 據我所知，應該是數組吧，我們可以直接使用數組下标來通路資料，是以查詢效率是很高滴
慶哥： 對，非常對，哈希表其實本質上就是一個數組 。
小白： 那為啥還叫哈希表呢？，哈希表肯定有啥特别的吧，為啥本質上是一個數組呢？
慶哥： 必須滴啊，哈希表本質上是個數組，隻能說它的底層實作是用到了數組，簡單點說，在數組的這個基礎上再捯饬捯饬，加工加工，變得更加有特色了，然後人家就自立門戶，叫哈希表
小白： 這是咋個回事啊
慶哥： 為什麼說哈希表的本質是個數組呢？那就得看看，哈希表是怎麼來實作的了，一般來說啊，實作哈希表我們可以采用兩種方法：
1、數組+連結清單
2、數組+二叉樹
簡單點就有這麼兩種方式，其實說白了，無論哪個都是必須有數組啊，都是再數組的基礎上取搞其他的，而且比如第一種數組+連結清單的形式，本質上是出現哈希沖突的一種解決辦法，使用連結清單存放，是以綜合起來叫做數組+連結清單的方式來實作一個哈希表，另外數組中一般就是存放的單一的資料，而哈希表中存放的是一個鍵值對，這是個差別吧！
小白： 停！！！有點迷糊，什麼哈希沖突，什麼玩意兒啊
慶哥： ，好吧好吧，我說的有點着急了，你就記住，哈希表在本質上就是個數組就ok了。
小白： 可是我還是像知道為啥啊？
慶哥： 别着急啊，咱慢慢來講，另外在百科上有這麼一個例子，可以幫助你更好的了解哈希表是個啥，它是這樣說的：
怎麼樣？看的懂嘛？
小白： 反正是有點模糊，這其中提到的函數關系啊，關鍵字啊，散列函數還有什麼函數法則的有點迷迷糊糊的
慶哥： 确實，這都是哈希表中很重要的幾個概念，那咱就先搞懂這幾個概念吧，我用大白話給你說說這個例子。
比如說，我現在給你個電話本，上面記錄的有姓名和對應的手機号，我想讓你幫我找王二的手機号是多少，那麼你會怎麼做呢？
小白： 這樣啊，那我就挨個找王二呗？
慶哥： 确實可以，那麼你有沒有想過，如果這個王二是在最後幾頁，那你去豈不是前面幾頁都白找了，有沒有更快的方式呢？
小白： 也是哦，那這樣的話，是不是可以按照人名給分個類，比如按照首字母來排序，就abcd那樣的順序，這樣根據王二我就知道去找w這些，這樣不久快很多了
慶哥： 的确，我們可以按照人名的首字母去弄一個表格，比如像這樣：
你看，假如現在我讓你去幫我找王二的手機号，你一下子就能找到，不用再挨個的去查找了，這效率就高的多了，那麼現在重點來了，人家本來叫王二，你為啥用一個w來标記人家呢？讓你找王二為啥你不直接找王二而是去找w呢？
小白： 這個？用w可以更快速的去定位到王二啊
慶哥： 說的很對，我們取姓名的首字母作為一個标志，就可以很快的找到以這個字母開頭的人名了，那麼王二也就能更快的被我們找到，我們也不用再費力氣去找什麼張二和李二的，因為人家的名字首字母都不是w。
小白： 那必須啊，這個方法好吧
慶哥： 對對對，你說到點子上了，那就是方法二字，這裡我們就是采用一種方法，什麼方法呢？那就是取姓名的首字母做一個排序，那麼這是不是就是通過一些特定的方法去得到一個特定的值，比如這裡取人名的首字母，那麼如果是放到數學中，是不是就是類似一個函數似的，給你一個值，經過某些加工得到另外一個值，就像這裡的給你個人名，經過些許加工我們拿到首字母，那麼這個函數或者是這個方法在哈希表中就叫做散列函數，其中規定的一些操作就叫做函數法則，這下你知道什麼是散列函數了吧
小白： 嗯呢，這下真的是很清楚了，說白了，不就是給我一個值，經過捯饬一下，變成另外一個值嗎？花個圖的話就是這個樣子：
哈哈，是不是這樣？
慶哥： 簡單來說就是這樣滴，咋樣，這下知道什麼是散列函數了吧？
小白： 這下知道了，很清楚，那這個關鍵字key是個啥玩意？
慶哥： 這個也好了解啊，就像你畫的這個圖，1是怎麼得出來得，是不是根據未加工之前得101得出來得，這個加工過程其實就是個散列函數，而丢給它的這個101就是這個關鍵值啊，為啥叫它關鍵值嘞，那是因為我們要對它做加工才能得出我們想要的1啊，你說它關不關鍵
小白： 哦哦，原來是這樣啊，這下就明白啦！對了，我現在有這樣的一個了解，你看看對不對啊，那就是哈希表就是通過将關鍵值也就是key通過一個散列函數加工處理之後得到一個值，這個值就是資料存放的位置，我們就可以根據這個值快速的找到我們想要的資料，是不是這樣啊？
慶哥： 說的很正确，那你現在對之前那個百科的例子懂了嘛？
小白： 嗯呢，這下懂了
慶哥： 嗯呢，那就好，其實吧，上面的那中情況并不好，為啥嘞？你想啊，王二在那個位置，如果再來個王三呢？人家的首字母也是w啊，這咋辦，位置被王二占了，那王三咋辦？這就是哈希沖突啊，撞衫啦
小白： 阿西吧，又是哈希沖突，它到底似乎個啥玩意啊
慶哥： 不着急，咱們繼續來探究哈希表。
慶哥： 我們在之前已經知道了哈希表的本質其實是個數組，數組有啥特點啊？
小白： 數組嘛，那就是下表從0開始啊，連續的，直接通過下标通路，比如下面這樣：
有一個數組a，我們可以直接通過a[1]的形式來通路到數值7，是以查詢效率很高。
慶哥： 完全正确，那麼哈希表本質上是個數組，那它跟這個類似嗎？我們來再深入探究一下，首先看個圖：
這張圖可是資訊量很大啊，你看出來個啥了嘛？
小白： 這個？我看到了哈希函數，這是啥？它跟散列函數有啥差別啊？還有Entry是個什麼鬼，還有鍵值對，蒙圈啊
慶哥： 别蒙圈啊，我來仔細跟你說說，其實這個哈希函數就是我們之前說的散列函數，為啥嘞？這就跟哈希表也叫做散清單一樣啊，你叫作散清單的時候有個散列函數，那你叫哈希表的時候，也得有個哈希函數啊，這樣才公平嘛，咋樣，知道了吧？
小白： 我去，原來是這麼回事啊，那鍵值對跟Entry嘞？
慶哥： 這個可是值得好好說道說道，我們知道哈希表本質上是個數組，難道就跟數組的基本使用那樣，存個數值，然後通過下表讀取之類的嘛？當然不是啦，對于哈希表，它經常存放的是一些鍵值對的資料，啥是鍵值對啊，就是我們經常說的key-value啊，簡單點說就是一個值對應另外一個值，比如a對應b，那麼a就是key，b是value，哈希表存放的就是這樣的鍵值對，在哈希表中是通過哈希函數将一個值映射到另外一個值的，是以在哈希表中，a映射到b，a就叫做鍵值，而b呢？就叫做a的哈希值，也就是hash值。
咋樣，這塊明白了嘛？
小白： 嗯嗯，明白的，慶哥繼續！
慶哥： 那好，我們繼續，鍵值對說的簡單點就是有一個key和一個value對應着，比如這張圖裡的學生資訊：
學生的學号和姓名就是一個鍵值對啊，根據這個學号就能找到這個學生的姓名，那啥是Entry嘞，我們都知道鍵值對，在很多語言中也許都有鍵值對，說白了就是個大衆臉啊，咋弄，在咱jdk中可不能那麼俗氣，不能再叫鍵值對了，叫啥嘞，那就叫Entry吧
咋樣，知道啥是鍵值對和Entry了吧！
小白： 必須滴啊，講的那麼生動，這張圖感覺遠不止如此啊，慶哥繼續啊
慶哥： 好滴，那咱們就繼續，來說說哈希表是如何存放資料的，記得看上面的圖啊，我們按照這個圖來說，我們已經知道了哈希表本質是個數組，是以這裡有個數組，長度是8，現在我們要做的是把這個學生資訊存放到哈希表中，也就是這個數組中去，那我們需要考慮怎麼去存放呢？
這裡的學号是個key，我們之前也知道了，哈希表就是根據key值來通過哈希函數計算得到一個值，這個值就是用來确定這個Entry要存放在哈希表中的位置的，實際上這個值就是一個下标值，來确定放在數組的哪個位置上。
比如這裡的學号是101011，那麼經過哈希函數的計算之後得到了1，這個1就是告訴我們應該把這個Entry放到哪個位置，這個1就是數組的确切位置的下标，也就是需要放在數組中下表為1的位置，如圖中所示。
我們之前已經介紹過什麼是Entry了，是以這裡你要知道，數組中1的位置存放的是一個Entry，它不是一個簡單的單個數值，而是一個鍵值對，也就是存放了key和value，key就是學号101011，value就是張三，我們經過哈希函數計算得出的1隻是為了确定這個Entry該放在哪個位置而已。
現在我們就成功把這個Entry放到了哈希表中了，怎麼樣，這塊聽懂了嘛？
小白： 嗯嗯，聽懂了，不過看到這裡我産生了一個疑問，那就是這個哈希函數，是不是有一個特定的加工過程，比如可以經過某種計算把101011轉換成1，那麼有沒有可能其他的學号經過哈希函數的計算也得出1呢？那這個時候是不是就撞衫啦
慶哥： 的确，你分析得很正确，我們再來看下面這張圖：
你說的這種情況就像圖中展示的那樣，學号為102011的李四，他的學号經過哈希函數的計算也得出了1，那麼也要放到數組中為1的位置，可是這個位置之前已經被張三占了啊，這怎麼辦？這種情況就是哈希沖突或者也叫哈希碰撞。
既然出現了這情況，不能不管李四啊，總得給他找個位置啊，怎麼找呢？
小白： 我猜肯定有什麼方法可以給李四找位置
慶哥： 那必須滴啊，有什麼方法呢？其實關于哈希沖突的解決辦法有好幾種嘞，但是我這裡隻介紹兩種主要的方法，一個是開放尋址法，一個是拉鍊法。
那什麼是開放尋址法呢？我們繼續來看圖：
我覺得看圖就足以說明問題了，這裡所說的開放尋址法其實簡單來說就是，既然位置被占了，那就另外再找個位置不就得了，怎麼找其他的位置呢？這裡其實也有很多的實作，我們說個最基本的就是既然目前位置被占用了，我們就看看該位置的後一個位置是否可用，也就是1的位置被占用了，我們就看看2的位置，如果沒有被占用，那就放到這裡呗，當然，也有可能2的位置也被占用了，那咱就繼續往下找，看看3的位置，一次類推，直到找到空位置。
對了，Java中的ThreadLocal就是利用了開放尋址法。
小白： 啥是ThreadLocal啊
慶哥： 咋滴，你不知道啊，沒事，慶哥最近會寫一篇ThreadLocal的文章，到時候記得來看哦！
小白： 嗯嗯，我會好好看看的。那什麼是拉鍊法啊？
慶哥： 拉鍊法也是比較常用的，像之前你說的HashMap就是使用了這種方法，那這個方法是怎麼個回事呢？我們繼續來看圖：
之前說的開放尋址法采用的方式是在數組上另外找個新位置，而拉鍊法則不同，還是在該位置，可是，該位置被占用了咋整，總不能打一架，誰赢是誰的吧，當然不是這樣，這裡采用的是連結清單，什麼意思呢？就像圖中所示，現在張三和李四都要放在1找個位置上，但是張三先來的，已經占了這個位置，待在了這個位置上了，那李四呢？解決辦法就是連結清單，這時候這個1的位置存放的不單單是之前的那個Entry了，此時的Entry還額外的儲存了一個next指針，這個指針指向數組外的另外一個位置，将李四安排在這裡，然後張三那個Entry中的next指針就指向李四的這個位置，也就是儲存的這個位置的記憶體位址，如果還有沖突，那就把又沖突的那個Entry放在一個新位置上，然後李四的Entry中的next指向它，這樣就形成了一個連結清單。
好啦，這就是拉鍊法，咋樣，明白不
小白： 資訊量不少啊，好在慶哥講的比較清楚，明白啦
慶哥： 明白了就好，那我問你一個問題啊，針對開放尋址和拉鍊法，你有沒有覺得會産生什麼問題呢？
小白： 嗯嗯，我還真有問題，首先是這個拉鍊法啊，如果沖突的很多，那這個增加的連結清單豈不是很長，這樣也不咋好吧
慶哥： 的确，如果沖突過多的話，這塊的連結清單會變得比較長，怎麼處理呢？這裡舉個例子吧，拿java集合類中的HashMap來說吧，如果這裡的連結清單長度大于等于8的話，連結清單就會轉換成樹結構，當然如果長度小于等于6的話，就會還原連結清單。以此來解決連結清單過長導緻的性能問題。
小白： 為啥是小于等于6啊，咋不是7嘞
慶哥： 這樣設計是因為中間有個7作為一個內插補點，來避免頻繁的進行樹和連結清單的轉換，因為轉換頻繁也是影響性能的啊。
小白： 嗯嗯，這個知道了，關于開放尋址也有個疑問，那就是如果一直找不到空的位置咋整啊？
慶哥： 這個不會的，為啥嘞？你這樣想，是因為你考慮了一個前提，那就是位置已經被占光了，沒有空位置了，但是實際情況是位置不會被占光的，因為有一定量的位置被占了的時候就會發生擴容。
小白： 阿西吧，還有擴容，那這個擴容是咋回事呢？
慶哥： 其實這裡不僅僅是因為你說的那種情況才會擴容，還有一個很重要的原因就是當哈希表被占的位置比較多的時候，出現哈希沖突的機率也就變高了，是以很有必要進行擴容。
那麼這個擴容是怎麼擴的呢？這裡一般會有一個增長因子的概念，也叫作負載因子，簡單點說就是已經被占的位置與總位置的一個百分比，比如一共十個位置，現在已經占了七個位置，就觸發了擴容機制，因為它的增長因子是0.7，也就是達到了總位置的百分之七十就需要擴容。
還拿HashMap來說，當它目前的容量占總容量的百分之七十五的時候就需要擴容了。
而且這個擴容也不是簡單的把數組擴大，而是新建立一個數組是原來的2倍，然後把原數組的所有Entry都重新Hash一遍放到新的數組。
小白： 這個重新Hash一遍是啥意思啊？
慶哥： 因為數組擴大了，是以一般哈希函數也會有變化，這裡的Hash也就是把之前的資料通過新的哈希函數計算出新的位置來存放。
小白： 嗯嗯，原來是這麼回事啊，懂了，對了，那哈希表的資料讀取怎麼操作的啊？
慶哥： 要知道這個讀取操作，我們還來看這個圖：
比如我們現在要通過學号102011來查找學生的姓名，怎麼操作呢？我們首先通過學号利用哈希函數得出位置1，然後我們就去位置1拿資料啊，拿到這個Entry之後我們得看看這個Entry的key是不是我們的學号102011，一看是101011，什麼鬼，一邊去，這不是我們要的key啊，然後根據這個Entry的next知道下一給位置，在比較key，好成功找到李四。
小白： 哦哦，原來是這麼回事啊，那對于開放尋址那種是不是也是這個思路，先确定到這個位置，然後再看這個位置上的key是不是我們要的，如過不是那就看看下一個位置的。
慶哥： 可以的，完全正确，好了現在我們對哈希表的講解已經差不多了，那麼你覺得對于哈希表而言，什麼是核心呢？
小白： 我覺得應該是哈希函數吧，經過上面的講解，我覺得，如果一個哈希函數設計的足夠好的話，就會減少哈希沖突的機率，如果設計的不好，那就會經常撞衫，那就很影響性能了，比如剛開始我們舉的那個例子，拿姓名的首字母來确定位置，這個哈希函數的設計就不咋滴，比如王二，王三，王四什麼的，這都會沖突啊
慶哥： 的确，在哈希表中，哈希函數的設計很重要，一個好的哈希函數可以極大的提升性能，而且如果你的哈希函數設計的比較簡單粗陋，那很容易被那些不懷好意的人搗亂，比如知道了你哈希函數的規則，故意制造容易沖突的key值，那就有意思了，你的哈希表就會一直撞啊，一直撞啊
小白： 哈哈，那設計哈希函數有什麼方法嗎？
慶哥： 必須有啊，比如有直接定址法，數字分析法，折疊法，随機數法和除留餘數法等等，要不要繼續講啊
小白： 我去，還是不要了吧，消化不了啊，這次先到這吧，謝謝慶哥
感謝各位大大的閱讀