一、Hash的概念和基本特征
哈希(Hash)也稱為散列，就是把任意長度的輸入，通過散列算法，變換成固定長度的輸出，這個輸出值就是散列值。

二、碰撞處理方法(2種)
在上面的例子中，我們發(fā)現(xiàn)有些在Hsh中很多位置可能要存兩個甚至多個元素，很明顯單純的數(shù)組是不行的，這種兩個不同的輸入值，根據(jù)同一散列函數(shù)計算出的散列值相同的現(xiàn)象叫做碰撞。
那該怎么解決呢？常見的方法有：開放定址法(Java里的Threadlocal)、鏈地址法(Java里的ConcurrentHashMap)、再哈希法（布隆過濾器）、建立公共溢出區(qū)。后兩種用的比較少，重點看前兩個。

1.開放定址法
開放定址法就是一旦發(fā)生了沖突，就去尋找下一個空的散列地址，只要散列表足夠大，空的散列地址總能找到，并將記錄存入。
例如上面要繼續(xù)存7,8,9的時候，7沒問題，可以直接存到索引為0位置。8本來應(yīng)該存到索引為1的位置，但是已經(jīng)滿了，所以繼續(xù)向后找，索引3的位置是空的，所以8存到3位置。同理9存到索引6位置。
這里是否有一個疑惑：這樣鳩占鵲巢的方法會不會引起混亂？比如再存3和6的話，本來自己的位置好好的，但是被外來戶占領(lǐng)了，該如何處理呢？這個問題直到我在學(xué)習(xí)Java里的ThreadLocal才解開。具體過程可以學(xué)習(xí)一下相關(guān)內(nèi)容，我們這里只說一下基本思想。ThreadLocal?有一個專門存儲元素的TheadLocalMap,每次在get和set元素的時候，會先將目標位置前后的空間搜索一下，將標記為nul的位置回收掉，這樣大部分不用的位置就收回來了。這就像假期后你到公司，每個人都將自己的位子附近打掃干凈，結(jié)果整個工作區(qū)就很干凈了。當然Hsh處理該問題的整個過程非常復(fù)雜，涉及弱引用等等，這些都是Java技術(shù)面試里的高頻考點。

2.鏈地址法
將哈希表的每個單元作為鏈表的頭結(jié)點，所有哈希地址為的元素構(gòu)成一個同義詞鏈表。即發(fā)生沖突時就把該關(guān)鍵字鏈在以該單元為頭結(jié)點的鏈表的尾部。

這種處理方法的問題是處理起來代價還是比較高的，要落地還要進行很多優(yōu)化，例如在Java里的ConcurrentHashMap中就使用了這種方式，其中涉及元素盡量均勻、訪問和操作速度要快、線程安全、擴容等很多問題。
?