HASH 主要用于信息安全領(lǐng)域中加密算法，它把一些不同長(zhǎng)度的信息轉(zhuǎn)化成雜亂的128 位的編碼, 這些編碼值叫做HASH 值. 也可以說(shuō)，hash 就是找到一種數(shù)據(jù)內(nèi)容和數(shù)據(jù)存放地址之間的映射關(guān)系
例如字符串 hello 的哈希算法
char* value = "hello"; int key = (((((((27* (int)'h'+27)* (int)'e') + 27) * (int)'l') + 27) * (int)'l' +27) * 27 ) + (int)'o' ;。
數(shù)組的特點(diǎn)是：尋址容易，插入和刪除困難；而鏈表的特點(diǎn)是：尋址困難，插入和刪除容易。那么我們能不能綜合兩者的特性，做出一種尋址容易，插入刪除也容易 的數(shù)據(jù)結(jié)構(gòu)？答案是肯定的，這就是我們要提起的哈希表，哈希表有多種不同的實(shí)現(xiàn)方法，我接下來(lái)解釋的是最常用的一種方法—— 拉鏈法，我們可以理解為“ 鏈表 的數(shù)組” ，如圖：
HashMap其實(shí)也是一個(gè)線(xiàn)性的數(shù)組實(shí)現(xiàn)的,所以可以理解為其存儲(chǔ)數(shù)據(jù)的容器就是一個(gè)線(xiàn)性數(shù)組。這可能讓我們很不解，一個(gè)線(xiàn)性的數(shù)組怎么實(shí)現(xiàn)按鍵值對(duì)來(lái)存取數(shù)據(jù)呢？這里HashMap有做一些處理。
1.首先HashMap里面實(shí)現(xiàn)一個(gè)靜態(tài)內(nèi)部類(lèi)Entry 其重要的屬性有 key , value, next,從屬性key,value我們就能很明顯的看出來(lái)Entry就是HashMap鍵值對(duì)實(shí)現(xiàn)的一個(gè)基礎(chǔ)bean,我們上面說(shuō)到HashMap的基 礎(chǔ)就是一個(gè)線(xiàn)性數(shù)組,這個(gè)數(shù)組就是Entry[]，Map里面的內(nèi)容都保存在Entry[]里面。
2.既然是線(xiàn)性數(shù)組，為什么能隨機(jī)存取？這里HashMap用了一個(gè)小算法，大致是這樣實(shí)現(xiàn)：
Java代碼
- 存儲(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通過(guò)鍵值對(duì)實(shí)現(xiàn)存取的基本原理
3.疑問(wèn)：如果兩個(gè)key通過(guò)hash % Entry[].length得到的index相同，會(huì)不會(huì)有覆蓋的危險(xiǎn)？
這里HashMap里面用到鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)的一個(gè)概念.上面我們提到過(guò)Entry類(lèi)里面有一個(gè)next屬性,作用是指向下一個(gè)Entry。打個(gè)比方, 第一個(gè)鍵值對(duì)A進(jìn)來(lái),通過(guò)計(jì)算其key的hash得到的index=0，記做:Entry[0] = A.一會(huì)后又進(jìn)來(lái)一個(gè)鍵值對(duì)B,通過(guò)計(jì)算其index也等于0,現(xiàn)在怎么辦？HashMap會(huì)這樣做:B.next = A,Entry[0] = B,如果又進(jìn)來(lái)C,index也等于0,那么C.next = B,Entry[0] = C；這樣我們發(fā)現(xiàn)index=0的地方其實(shí)存取了A,B,C三個(gè)鍵值對(duì),他們通過(guò)next這個(gè)屬性鏈接在一起。所以疑問(wèn)不用擔(dān)心。
到這里為止，HashMap的大致實(shí)現(xiàn)，我們應(yīng)該已經(jīng)清楚了。
當(dāng)然HashMap里面也包含一些優(yōu)化方面的實(shí)現(xiàn)，這里也啰嗦一下。
比如：Entry[]的長(zhǎng)度一定后，隨著map里面數(shù)據(jù)的越來(lái)越長(zhǎng)，這樣同一個(gè)index的鏈就會(huì)很長(zhǎng)，會(huì)不會(huì)影響性能？
HashMap里面設(shè)置一個(gè)因素（也稱(chēng)為因子），隨著map的size越來(lái)越大，Entry[]會(huì)以一定的規(guī)則加長(zhǎng)長(zhǎng)度。
解決hash沖突的辦法
1）開(kāi)放定址法（線(xiàn)性探測(cè)再散列，二次探測(cè)再散列，偽隨機(jī)探測(cè)再散列）
2）再哈希法
3）鏈地址法
4）建立一 公共溢出區(qū)
java 中hashmap的解決辦法就是采用的鏈地址法
轉(zhuǎn)載文章