一瘦赫、集合框架源碼分析
- 集合框架 （第 01 篇） 源碼分析：Collection<E> 框架總覽
- 集合框架 （第 02 篇） 源碼分析：Map<K,V > 框架總覽
- 集合框架 （第 03 篇） 源碼分析：ArrayList<E>
- 集合框架 （第 04 篇） 源碼分析：LinkedList
- 集合框架 （第 05 篇） 源碼分析：Map<K, V>接口與其內(nèi)部接口Entry<K,V>
- 集合框架 （第 06 篇） 源碼分析：哈希沖突(哈希碰撞)與解決算法
- 集合框架 （第 07 篇） 源碼分析：jdk1.7版 HashMap
- 集合框架 （第 08 篇） 源碼分析：HashMap、Hashtable血筑、ConcurrentHashMap之間的區(qū)別
- 集合框架 （第 09 篇） 源碼分析：jdk1.7版 ConcurrentHashMap
- 集合框架 （第 10 篇） 源碼分析：二叉樹痒钝、平衡二叉樹迅皇、二叉查找樹从铲、AVL樹纫骑、紅黑樹
- 集合框架 （第 11 篇） 源碼分析：jdk1.8版 HashMap
- 集合框架 （第 12 篇） 源碼分析：jdk1.8版 ConcurrentHashMap
- 集合框架 （第 13 篇） 源碼分析：LinkedHashMap
- 集合框架 （第 14 篇） 源碼分析：TreeMap
- 集合框架 （第 15 篇） 源碼分析：Set<E> 集合
- 集合框架 （第 16 篇） 源碼分析：BlockingQueue 接口
- 集合框架 （第 17 篇） 源碼分析：CopyOnWriteArrayList 與 CopyOnWriteArraySet
原文持續(xù)更新鏈接: https://github.com/about-cloud/JavaCore
正文
一蝎亚、Hash沖突（哈希碰撞??）
1.1、什么是沖突先馆？
在一間教室里有一排座椅颖对，這一排座椅線性排列對應(yīng)的數(shù)據(jù)結(jié)構(gòu)是 數(shù)組，數(shù)組的特點是可以根據(jù)下標(biāo)(索引)快速??訪問磨隘，通過下標(biāo)(索引)訪問的位置
table[i]稱為 槽（slot）缤底，在伴隨著哈希算法計算的槽稱為 哈希槽。假設(shè)這排座椅共16個座位??番捂，編號從0,1,2…開始直到15个唧。學(xué)校有很多學(xué)生，他們的編號也是從0,1,2…起始设预，有很多同學(xué)喜歡坐在一起徙歼，學(xué)校??為了讓他們散列分開坐，采用模運算的方式鳖枕。比如 1號同學(xué)的對座椅長度16模運算得1魄梯，那么你坐在1號位置，5號同學(xué)對座椅長度16模運算得5宾符，那么他坐在5號位置酿秸，以此類推。1號座位已經(jīng)被1號同學(xué)占用魏烫，新來的17號同學(xué)對16作模運算也得1辣苏，按照原來的算法，他也應(yīng)該坐在1號哄褒，此時17號同學(xué)和1號同學(xué)的座位??就 沖突稀蟋。
1.2、哈希算法與哈希沖突
實際上 “編號” 多種多樣呐赡，如果它們共有某種特性退客、聚集密度增加，沖突 概率就有可能增大链嘀，為了防止這些 項(元素) 過于集中萌狂，而將它們按照某種算法 散列 分布，這種算法稱為 Hash算法管闷，翻譯成散列算法粥脚，根據(jù)音譯常翻譯成哈希算法，通過 哈希算法 計算后的值稱為哈希碼或 散列碼(HashCode)包个。假如
1.1中學(xué)生的編號不是數(shù)字刷允，而是其他字符組合冤留，比如學(xué)生周星星的編號是ZXX9573，非Number類型的字符串是不能進(jìn)行數(shù)學(xué)模運算的树灶，即使能使用模運算也不能最大化的將他們散列開纤怒。所以使用 哈希算法 計算出 哈希碼，然后根據(jù)模運算來決定它們該進(jìn)入哪個 槽天通，這里的槽也稱為 哈希槽泊窘。這個通過 散列 方式存儲元素的陣列容器稱為 散列表 (hashtable)，不過大多數(shù)人喜歡叫它哈希表像寒。
如果跟據(jù) 哈希算法 計算得到的 哈希碼 有多個相同的烘豹，那么模運算后得到的 哈希槽 也一定相同，也就產(chǎn)生了新的沖突诺祸，這種沖突稱為 哈希沖突(哈希碰撞??)携悯。
[圖片上傳失敗...(image-520e14-1550719911569)]
<h3 style="padding-bottom:6px; padding-left:20px; color:#ffffff; background-color:#E74C3C;">二、哈希沖突解決算法</h3>
2.1筷笨、開放定址法（open addressing）
一個元素與另一個元素關(guān)于某個地址(或槽)發(fā)生了沖突憔鬼，將開放其他地址給此元素使用，這種算法稱開放定址法 或 開放地址法胃夏。如何尋找適合的開放地址給此元素使用轴或，這種尋找的過程或者技術(shù)稱為探測技術(shù)。常見的 “尋找技術(shù)” 有如下幾種：
線性探測
接上面的故事仰禀，假設(shè) 1號座位已經(jīng)有人照雁，然后根據(jù)哈希算法計算出
周星星應(yīng)該落到 1號 座位，這時出現(xiàn)哈希沖突悼瘾，然后按照線性方式探測下 1 個座位（哈希槽）囊榜，如果2號座位（哈希槽）也有人审胸，然后再按照線性方式探測下 1 個座位（哈希槽）... 以此類推亥宿。此種方式就是 線性探測。其中 “下 1 個” 指的是 步長（也稱為增量）砂沛，你也可以將步長定為2烫扼，那就是下2個。實際上根據(jù)步長計算出的一批地址碍庵，這批地址稱為地址序列映企。
二次探測（平方探測）
將步長(增量)改為
這種增量序列。從 增量i 可以看出正負(fù)交替静浴，特點是在探測時左右??跳躍式探測堰氓。線性跳躍
偽隨機探測
原來線性探測的步長都是已知數(shù)，現(xiàn)在將每個步長改為隨機獲取苹享。實際過程也是隨機產(chǎn)生一批隨機數(shù)双絮，也就是 隨機序列。
2.2、再哈希法
再哈希法是有多個哈希函數(shù)(算法)囤攀，當(dāng)?shù)谝淮萎a(chǎn)生哈希沖突時软免，就使用第二個哈希函數(shù)，如果還產(chǎn)生哈希沖突就使用第三個焚挠，以此類推膏萧，再次哈希，直達(dá)無沖突蝌衔，這樣的做法會增加哈希計算時間榛泛。
2.3、鏈地址法（鏈表法）
當(dāng)多個元素產(chǎn)生哈希沖突時噩斟，它們的哈希碼是一定相同挟鸠，落腳的哈希槽也相同。將它們通過地址引用一一相連亩冬，也就是形成 鏈表 的形式艘希。這樣它們既可以存儲，又不會占用其他哈希槽的位置硅急。這種通過鏈表形式解決哈希沖突的算法稱為鏈表法覆享。由不同元素、相同哈希碼經(jīng)過組織形成的數(shù)據(jù)結(jié)構(gòu)稱為 哈希桶Bucket营袜，或者說這個容器是 哈希桶撒顿。哈希槽的位置也就是哈希桶號 。
2.4荚板、建立公共溢出區(qū)
為所有產(chǎn)生哈希沖突的元素建立一個公共溢出區(qū)域來存放溢出的元素凤壁。在查找時，如果通過計算發(fā)現(xiàn)對應(yīng)的哈希槽處沒該元素跪另，則進(jìn)入公共溢出區(qū) 進(jìn)行查找拧抖，溢出的元素相對于 散列表 來說是比較小的。原來的表稱為基本表免绿，公共溢出區(qū)又稱溢出表唧席。
