1.HashMap的數(shù)據(jù)結(jié)構(gòu)

　　數(shù)組的特點(diǎn)是：尋址容易,，插入和刪除困難,；而鏈表的特點(diǎn)是：尋址困難，插入和刪除容易,。那么我們能不能綜合兩者的特性,，做出一種尋址容易，插入刪除也容易的數(shù)據(jù)結(jié)構(gòu),？答案是肯定的,，這就是我們要提起的哈希表，哈希表有多種不同的實(shí)現(xiàn)方法,，我接下來解釋的是最常用的一種方法—— 拉鏈法,，我們可以理解為“鏈表的數(shù)組” ，如圖：

　　從上圖我們可以發(fā)現(xiàn)哈希表是由數(shù)組+鏈表組成的,，一個(gè)長(zhǎng)度為16的數(shù)組中,，每個(gè)元素存儲(chǔ)的是一個(gè)鏈表的頭結(jié)點(diǎn)。那么這些元素是按照什么樣的規(guī)則存儲(chǔ)到數(shù)組中呢,。一般情況是通過hash(key)%len獲得,，也就是元素的key的哈希值對(duì)數(shù)組長(zhǎng)度取模得到。比如上述哈希表中,，12%16=12,28%16=12,108%16=12,140%16=12,。所以12、28,、108以及140都存儲(chǔ)在數(shù)組下標(biāo)為12的位置,。

　　HashMap其實(shí)也是一個(gè)線性的數(shù)組實(shí)現(xiàn)的,所以可以理解為其存儲(chǔ)數(shù)據(jù)的容器就是一個(gè)線性數(shù)組。這可能讓我們很不解,，一個(gè)線性的數(shù)組怎么實(shí)現(xiàn)按鍵值對(duì)來存取數(shù)據(jù)呢,？這里HashMap有做一些處理。

　　1.首先HashMap里面實(shí)現(xiàn)一個(gè)靜態(tài)內(nèi)部類Entry,，其重要的屬性有 key , value, next,，從屬性key,value我們就能很明顯的看出來Entry就是HashMap鍵值對(duì)實(shí)現(xiàn)的一個(gè)基礎(chǔ)bean，我們上面說到HashMap的基礎(chǔ)就是一個(gè)線性數(shù)組,，這個(gè)數(shù)組就是Entry[],，Map里面的內(nèi)容都保存在Entry[]里面。

2.HashMap的存取實(shí)現(xiàn)

     既然是線性數(shù)組,，為什么能隨機(jī)存??？這里HashMap用了一個(gè)小算法，大致是這樣實(shí)現(xiàn)：

//存儲(chǔ)時(shí):
int hash = key.hashCode();// 這個(gè)hashCode方法這里不詳述,只要理解每個(gè)key的hash是一個(gè)固定的int值
int index = hash % Entry[].length;
Entry[index] = value;

//取值時(shí):
int hash = key.hashCode();
int index = hash % Entry[].length;
return Entry[index];

到這里我們輕松的理解了HashMap通過鍵值對(duì)實(shí)現(xiàn)存取的基本原理

    3.疑問：如果兩個(gè)key通過hash%Entry[].length得到的index相同,，會(huì)不會(huì)有覆蓋的危險(xiǎn),？

　　這里HashMap里面用到鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)的一個(gè)概念。上面我們提到過Entry類里面有一個(gè)next屬性,，作用是指向下一個(gè)Entry,。打個(gè)比方， 第一個(gè)鍵值對(duì)A進(jìn)來,，通過計(jì)算其key的hash得到的index=0,，記做:Entry[0] = A,。一會(huì)后又進(jìn)來一個(gè)鍵值對(duì)B,，通過計(jì)算其index也等于0，現(xiàn)在怎么辦,？HashMap會(huì)這樣做:B.next = A,Entry[0] = B,如果又進(jìn)來C,index也等于0,那么C.next = B,Entry[0] = C,；這樣我們發(fā)現(xiàn)index=0的地方其實(shí)存取了A,B,C三個(gè)鍵值對(duì),他們通過next這個(gè)屬性鏈接在一起。所以疑問不用擔(dān)心,。也就是說數(shù)組中存儲(chǔ)的是最后插入的元素,。到這里為止，HashMap的大致實(shí)現(xiàn),，我們應(yīng)該已經(jīng)清楚了,。

　　當(dāng)然HashMap里面也包含一些優(yōu)化方面的實(shí)現(xiàn)，這里也說一下,。比如：Entry[]的長(zhǎng)度一定后,，隨著map里面數(shù)據(jù)的越來越長(zhǎng)，這樣同一個(gè)index的鏈就會(huì)很長(zhǎng),，會(huì)不會(huì)影響性能,？HashMap里面設(shè)置一個(gè)因素（也稱為因子），隨著map的size越來越大,，Entry[]會(huì)以一定的規(guī)則加長(zhǎng)長(zhǎng)度,。

3.解決hash沖突的辦法

1. 開放定址法（線性探測(cè)再散列，二次探測(cè)再散列,，偽隨機(jī)探測(cè)再散列）
2. 再哈希法
3. 鏈地址法
4. 建立一個(gè)公共溢出區(qū)

Java中hashmap的解決辦法就是采用的鏈地址法,。

4.實(shí)現(xiàn)自己的HashMap

Entry.java

View Code

MyHashMap.java

View Code

MyHashMapTest.java

View Code