????????HashMap又稱之為散列表，這是一種使查找，插入和刪除都具備良好性能的數(shù)據(jù)結(jié)構(gòu)庐镐，其查找的時間復雜度為O( $logn$ )。散列表的核心技術(shù)就是散列变逃，其核心原理就是依賴一個標識符來確定數(shù)據(jù)的位置必逆，散列又分為靜態(tài)散列和動態(tài)散列，下邊來分析一下這兩種散列方式：

1.靜態(tài)散列

1.1散列表

? ? ? ? 在靜態(tài)散列表中揽乱，會將所有的標識符存在一張表中名眉，這張表就叫做散列表。通過一個函數(shù) $f(x)$ 可以確定 $x$ 在散列表中位置凰棉，這個函數(shù)就叫做散列函數(shù)损拢。散列表往往存放在一個連續(xù)的空間中，這個空間會被切割成n個空間撒犀，被稱之為散列桶福压。每個散列桶可能又被切割成n個空間，被稱之為槽或舞，往往一個散列桶只包含一個槽荆姆。

散列表的基本結(jié)構(gòu)

? ? ? ? ?為了統(tǒng)計衡量散列表的效率，分別用 $T$ 映凳， $b$ 和 $s$ 來表示一個散列表的標識符密度和裝載密度胆筒。其中 $T$ 表示標識符可能不同的組合次數(shù), $T=\sum_{i=0}^1 x^i * x$ ,例如a和b兩個字符，合組成如下a,b,aa,bb,ab,ba的6中組合魏宽。則標識符密度就為 $n/T$ ,即為 $2/7$ 腐泻。若散列表一共有 $b$ 個散列桶决乎，每個散列桶有 $s$ 個槽队询，那么裝載密度或者裝載因子 $\alpha =n/(sb)$ ,按上圖算即為 $2/（3*6）$ 派桩。當兩個不同的標識符 $x_{1}$ 和 $x_{2}$ ，通過散列函數(shù)得到 $f(x_{1} )=f(x_{2} )$ ,那么則稱 $x_{1}$ 和 $x_{2}$ 為同義詞蚌斩，只要散列桶中有空閑的槽铆惑，就可以將互不相同的同義詞放到同一個散列桶中，這種現(xiàn)象被稱之為散列沖突送膳。但是如果將一個同義詞放入到一個已滿的散列桶中员魏，那么就會發(fā)生溢出。

1.2散列函數(shù)

? ? ? ? 散列函數(shù) $f$ 的作用就是將表示符 $x$ 轉(zhuǎn)換成散列表中的地址叠聋。一個優(yōu)秀的散列函數(shù)應該是不側(cè)重某一個散列桶撕阎，而是均勻分布的。

1.3散列沖突和溢出處理

?1.3.1線性探測法?

? ? ? ? 散列表被存儲為一個線性數(shù)組碌补，其下標從0到散列表的期望大小-1虏束。當插入一個 $x$ 時，如果通過 $f(x)$ 計算的位置沒有值厦章，那么則將 $x$ 存儲在這個位置上镇匀，如果這個位置的散列桶已滿，那么就將其存儲在離 $f(x)$ 最近的并且未滿的散列桶中袜啃，這種解決散列沖突的方法就被稱之為線性探測法汗侵。

線性探測法

? ? ? ? 從上圖可以看出ab和af是同義詞當插入af的時候，首先會去找散列表下標為1的位置群发，發(fā)現(xiàn)這個位置有值了晰韵，并且不是af，那么繼續(xù)往下找熟妓，一直找到下表為3的地方發(fā)現(xiàn)了一個未滿的散列桶宫屠，將af存儲在這個位置。

1.3.2拉鏈法

? ? ? ? 通過上邊的分析滑蚯，我們可以看出線性探測法的效率是很低浪蹂，容易形成標識符堆積。還有一種常用的方法就是拉鏈法告材。如上圖ac和af是同義詞坤次，那么我們可以用一個單向的鏈表來存儲同義詞。

拉鏈法

? ? ? ? 這種結(jié)構(gòu)可以說比線性探測法要好上很多斥赋，插入的時候只需要計算散列值缰猴，將同義詞放在一張同義詞鏈表中，查找的時候只需要查找這張同義詞鏈表即可疤剑。

2.動態(tài)散列

? ? ? ? 靜態(tài)散列有一個非常致命的缺點滑绒，那就是我們無法確定靜態(tài)散列表的期望大小闷堡，如果過小，非常容易產(chǎn)生溢出疑故，如果過大杠览，因為靜態(tài)散列表要提前非配好內(nèi)存，這樣就會造成內(nèi)存浪費纵势。而動態(tài)散列就是能夠動態(tài)的對散列表進行擴展的一中技術(shù)踱阿。?

? ? ? ? 對于動態(tài)散列表來說，散列桶被稱之為頁面钦铁。假如說一個頁面容量為2软舌，有以下幾個標識符和散列值

以二進制對標識符進行散列

? ? ? ? 要求根據(jù)散列值的低兩位來確定標識符所處頁面的位置，0選擇上邊的分支牛曹，1選擇下邊的分支佛点，則有如下的存儲

0在上邊一個分支，1在下邊一個分支

? ? ? ? ? ? ? ? 加入說這個時候插入一個 $d$ 黎比，并且 $f(d)=100010010$ ,那么可以看到這個時候就會產(chǎn)生溢出了超营，如果溢出了動態(tài)散列表會怎么處理呢？

溢出之后新增一個頁面

? ? ? ? 因為一個頁面的容量為2，a,b,c三者的低兩位都為10，這個時候就會產(chǎn)生溢出锦担，那么就新增一個頁面静暂，按照低三位來進行索引，這樣就實現(xiàn)了動態(tài)擴容，所以動態(tài)散列的散列函數(shù)就是將標識符轉(zhuǎn)換成二進制表示，來對標識符的在散列表中的位置進行索引。

3.散列表的實現(xiàn)及分析-----Java中的HashMap

? ? ? ? HashMap是Java中一個非常重要的集合见间，其基本原理也是基于散列表進行擴展而實現(xiàn)的，下邊來仔細分析一下其核心代碼工猜。

數(shù)據(jù)節(jié)點的定義米诉，相當于上文“標識符”

? ? ? ? 可以看出數(shù)據(jù)節(jié)點中包含了一個節(jié)點的hash值，key篷帅，value已經(jīng)一個next節(jié)點史侣，通過這個基本可以看出它是采用拉鏈法來解決散列沖突的。

散列表定義

? ? ? ? 這段代碼定義了HashMap的散列表魏身，可以看出它是一個線性數(shù)組惊橱。使用的是靜態(tài)散列表的方式。其散列函數(shù)很簡單箭昵，即節(jié)點元素的hashCode無符號右移16位即可税朴，就不重點介紹了下邊重點來分析它的插入和查找方法。

HashMap插入的核心邏輯

? ? ? ? ?通過代碼我們可以看到Java中的HashMap是這樣插入一條新數(shù)據(jù)的，首先通過散列函數(shù)來計算出節(jié)點所處于的散列桶位置正林，如果為空泡一，那么直接將該節(jié)點放入到這個位置，如果這個位置不為空觅廓，但是插入的節(jié)點和老節(jié)點的key相同鼻忠，那么會將新的value值賦予到這個節(jié)點上，如果不滿足這一條件哪亿，即產(chǎn)生了散列沖突粥烁，那么這個時候就采用拉鏈法進行處理贤笆，當然Java中的HashMap在這里有一個細節(jié)蝇棉，即當散列桶的鏈表長度超過8時，將其轉(zhuǎn)換成紅黑樹芥永，紅黑樹的好處下一章節(jié)來進行分析篡殷。

HashMap查找的核心邏輯

? ? ? ? 這個邏輯就很簡單了，首先判斷第一個元素是不是要找的元素埋涧，如果是直接返回板辽，如果不是，就遍歷這個鏈表棘催，找到了就返回這個元素劲弦，沒找到就返回null值。

HashMap底層原理分析

HashMap底層原理分析

1.靜態(tài)散列

2.動態(tài)散列

3.散列表的實現(xiàn)及分析-----Java中的HashMap