一文徹底搞定Java哈希表和哈希沖突
一、什么是哈希表？
哈希表也叫散列表，它是基于數(shù)組的。這間接帶來了一個優(yōu)點：查找的時間復(fù)雜度為 O(1)、當(dāng)然，它的插入時間復(fù)雜度也是 O(1)。還有一個缺點：數(shù)組創(chuàng)建后擴容成本較高。
哈希表中有一個“主流”思想：轉(zhuǎn)換。一個重要的概念是將「鍵」或「關(guān)鍵字」轉(zhuǎn)換成數(shù)組下標(biāo)。這由“哈希函數(shù)”完成。
二、什么是哈希函數(shù)？
由上，其作用就是將非 int 的鍵/關(guān)鍵字轉(zhuǎn)化為 int 的值，使可以用來做數(shù)組下標(biāo)。
比如，HashMap 中就這樣實現(xiàn)了哈希函數(shù)：
static final int hash(Object key){
int h;
return (key==null)?0:(h=key.hashCode())^(h>>>16); // 通過異或提高hash的“散列度”，降低沖突
}
其中利用了 hashCode 完成轉(zhuǎn)換。雖然哈希函數(shù)有很多種實現(xiàn)，但都應(yīng)當(dāng)滿足這三點：
- 計算得到的是非負(fù)整數(shù)；
- 如果
key1==key2，則hash(key1)==hash(key2)； - 如果
key1!=key2，則hash(key1)!=hash(key2)；
并不是所有的鍵/關(guān)鍵字都需要被轉(zhuǎn)換才能做下標(biāo)（索引）就像 JS 中也有類似的、但僅用于檢測鍵是否能用來做數(shù)組下標(biāo)的方法：JavaScript數(shù)組索引檢測中的數(shù)據(jù)類型問題
三、什么是哈希沖突？
上面提到了 hashMap —— 一個java中提供的數(shù)據(jù)集。我們先來了解下：首先，hashMap 本質(zhì)上是一個容器，它為了達到快速索引的目的，使用了數(shù)組結(jié)構(gòu)“快速定位”的特性。
hashMap 中為了更快找到插入的值，建立了插入值和數(shù)組下標(biāo)的關(guān)系：pos(下標(biāo))=key(值)%size(數(shù)組大小)。
比如：數(shù)組長度為10
1.插入100，有100%10=0；
2.插入201，有201%10=1；
3.插入403，有403%10=3；
但是如果這樣設(shè)計的話，我現(xiàn)在再插入200，會怎么樣？
這就是數(shù)組的一個缺點：插入特殊值比較“費勁”。不如我們干脆將數(shù)組涉及成這樣：
引入鏈表特性，一個節(jié)點就包括一個值和一個next指針。
現(xiàn)在再插入上面那些值，就變成了這樣：
這時候如果再插入值300，怎么做？
類似這樣（當(dāng)兩個或以上的key的pos相同，且key不同）其實就是我們提到的“hash沖突”，而 hashMap 中解決hash沖突的方法就是上面說的“單鏈表”！
但是這又有一個問題：雖然用有序鏈表的方式可以減少不成功的查找時間(因為只要有一項比查找值大，就說明沒有我們需要查找的值)，但是不能加快成功的查找。如果沖突的鏈表太長，則鏈表查找時需要從“頭”遍歷的劣勢就暴露出來了 —— 針對這個問題，JDK1.8后用 紅黑樹 做了優(yōu)化！
但是我們先撇開紅黑樹，用單鏈表的形式說明一下哈希表的操作：
/**
* 鏈表基類：鏈表法解決哈希沖突用的是有序鏈表！
*/
public class SortedLinkList {
private Link first;
public SortedLinkList(){
first = null;
}
/**
* 鏈表插入
* @param link
*/
public void insert(Link link){
int key = link.getKey();
Link previous = null;
Link current = first;
while (current!=null && key >current.getKey()){
previous = current;
current = current.next;
}
if (previous == null)
first = link;
else
previous.next = link;
link.next = current;
}
/**
* 鏈表刪除
* @param key
*/
public void delete(int key){
Link previous = null;
Link current = first;
while (current !=null && key !=current.getKey()){
previous = current;
current = current.next;
}
if (previous == null)
first = first.next;
else
previous.next = current.next;
}
/**
* 鏈表查找
* @param key
* @return
*/
public Link find(int key){
Link current = first;
while (current !=null && current.getKey() <=key){
if (current.getKey() == key){
return current;
}
current = current.next;
}
return null;
}
}
鏈表法哈希表插入：
public void insert(int data) {
Link link = new Link(data);
int key = link.getKey();
int hashVal = hash(key);
array[hashVal].insert(link);
}
鏈表法哈希表查找：
public Link find(int key) {
int hashVal = hash(key);
return array[hashVal].find(key);
}
鏈表法哈希表刪除：
public Link find(int key) {
int hashVal = hash(key);
return array[hashVal].find(key);
}
除了鏈表法，解決哈希沖突還有一個方法：開放尋址法。
在開放地址法中，若數(shù)據(jù)不能直接存放在哈希函數(shù)計算出來的數(shù)組下標(biāo)時，就需要尋找其他位置來存放。在開放地址法中有三種方式來尋找其他的位置，分別是
- 線性探測
- 二次探測
- 再哈希法
到此這篇關(guān)于一文徹底搞定Java哈希表和哈希沖突的文章就介紹到這了,更多相關(guān)Java哈希表和哈希沖突內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Java接口方法默認(rèn)靜態(tài)實現(xiàn)代碼實例
這篇文章主要介紹了Java接口方法默認(rèn)靜態(tài)實現(xiàn),文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-06-06
淺談SpringBoot如何封裝統(tǒng)一響應(yīng)體
今天帶各位小伙伴學(xué)習(xí)SpringBoot如何封裝統(tǒng)一響應(yīng)體,文中有非常詳細(xì)的介紹及代碼示例,對正在學(xué)習(xí)java的小伙伴們有非常好的幫助,需要的朋友可以參考下2021-05-05
Java實現(xiàn)warcraft?java版游戲的示例代碼
致敬經(jīng)典的warcraft，《warcraft?java版》是一款即時戰(zhàn)略題材單機游戲，采用魔獸原味風(fēng)格和機制。本文將用java語言實現(xiàn)，采用了swing技術(shù)進行了界面化處理，感興趣的可以了解一下2022-09-09
這篇文章主要介紹了Java的Object類九個方法技巧，Java的Object?類的完整路徑是java.lang.Object?，是所有類的父類編譯，下文相關(guān)資料,需要的朋友可以參考一下2022-04-04
Java實現(xiàn)經(jīng)典游戲俄羅斯方塊(升級版)的示例代碼
俄羅斯方塊是一款風(fēng)靡全球，從一開始到現(xiàn)在都一直經(jīng)久不衰的電腦、手機、掌上游戲機產(chǎn)品，是一款游戲規(guī)則簡單，但又不缺乏樂趣的簡單經(jīng)典小游戲。本文將用Java語言實現(xiàn)這一經(jīng)典游戲，需要的可以參考一下2022-09-09
在Java中全局變量和局部變量是兩種不同作用域的變量,這篇文章主要給大家介紹了關(guān)于Java中全局變量和局部變量的相關(guān)資料,文中通過代碼介紹的非常詳細(xì),大家看這篇就夠了,需要的朋友可以參考下2023-11-11
這篇文章主要介紹了springboot遠程執(zhí)行服務(wù)器指令,本例是java遠程連接到服務(wù)器,去抓取查詢kubesphere中的etcd日志,并返回,需要的朋友可以參考下2023-09-09
maven如何利用springboot的配置文件進行多個環(huán)境的打包
這篇文章主要介紹了maven如何利用springboot的配置文件進行多個環(huán)境的打包,在Spring Boot中多環(huán)境配置文件名需要滿足application-{profiles.active}.properties的格式，其中{profiles.active}對應(yīng)你的環(huán)境標(biāo)識，本文給大家詳細(xì)講解，需要的朋友可以參考下2023-02-02
這篇文章主要給大家介紹了關(guān)于Java中如何靈活獲取excel中的數(shù)據(jù),在日常工作中我們常常會進行文件讀寫操作,除去我們最常用的純文本文件讀寫,更多時候我們需要對Excel中的數(shù)據(jù)進行讀取操作,需要的朋友可以參考下2023-07-07
這篇文章主要為大家詳細(xì)介紹了使用Spring框架實現(xiàn)用戶登錄，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-09-09