Java超詳細(xì)分析講解哈希表
哈希表概念
- 散列表，又稱為哈希表（Hash table），采用散列技術(shù)將記錄存儲在一塊連續(xù)的存儲空間中。
- 在散列表中，我們通過某個(gè)函數(shù)f，使得存儲位置 = f（關(guān)鍵字），這樣我們可以不需要比較關(guān)鍵字就可獲得需要的記錄的存儲位置。
- 散列技術(shù)的記錄之間不存在什么邏輯關(guān)系，它只與關(guān)鍵字有關(guān)聯(lián)。因此，散列主要是面向查找的存儲結(jié)構(gòu)。
哈希函數(shù)的構(gòu)造
構(gòu)造原則：
- 計(jì)算簡單
散列函數(shù)的計(jì)算時(shí)間不應(yīng)該超過其他查找技術(shù)與關(guān)鍵字比較的時(shí)間。
- 散列地址分布均勻
解決沖突最好的辦法就是盡量讓散列地址均勻地分布在存儲空間中。
- 保證存儲空間的有效利用，并減少為處理沖突而耗費(fèi)的時(shí)間。
構(gòu)造方法：
平均數(shù)取中法
假設(shè)關(guān)鍵字是1234，那么它的平方就是1522756.在抽取中間的3位就是227，用作散列地址。再比如關(guān)鍵字4321，那么它的平方就是18671041，抽中間三位數(shù)就是671或710。平方去中法比較適合不知道關(guān)鍵字的分布，而位數(shù)又不是很多的情況。
折疊法
折疊法是將關(guān)鍵字從左到右分割成位數(shù)相等的幾部分（注意最后一部分位數(shù)不夠時(shí)可以短一些），然后將這幾部分疊加求和，并按散列表表長，取幾位作為散列表地址。
比如我們的關(guān)鍵字是9 8 7 6 5 4 3 2 1 0，散列表表長為3位，我們將它分為四組，987|654|321|0，然后將他們疊加求和987+654+321+0=1962，再求后3位得到散列地址為962。
有時(shí)可能這還不能夠保證分布均勻，不妨從一端向另一端來回折疊后對齊相加。比如我們將987和321反轉(zhuǎn)，再與654和0相加，變成789+654+123+0=1566，此時(shí)散列地址為566。
折疊法事先不需要知道關(guān)鍵字的分布，適合關(guān)鍵字位數(shù)較多的情況。
保留余數(shù)法
此方法為最常用的構(gòu)造哈希函數(shù)的方法。
公式為：
f(key) = key mod p (p <= m)
代碼如下：
public int hashFunc(int key){
return key % length;
}
哈希沖突問題以及解決方法
哈希沖突就是，兩個(gè)不同的關(guān)鍵字，但是通過散列函數(shù)得出來的地址是一樣的。
key1 ≠ key2，但是f（key1）= f（key2）
同義詞
此時(shí)的key1 和key2就被稱為這個(gè)散列函數(shù)的同義詞
那可不行啊，一件單人間怎么可以住兩個(gè)人呢？
別擔(dān)心，這個(gè)問題自然已經(jīng)被神通廣大的大佬們解決了。
開放地址法
開發(fā)定址法就是一旦發(fā)生了沖突，就去尋找下一個(gè)空的散列地址，只需要散列表足夠大，空的散列地址總能找到，并將記錄存入
例子：
19 01 23 14 55 68 11 86 37
要存儲在表長11的數(shù)組中，其中H（key）=key MOD 11
再哈希函數(shù)法
對于我們的哈希表來說，我們事先需要準(zhǔn)備多個(gè)哈希函數(shù)。每當(dāng)發(fā)生散列地址沖突時(shí)，就換一個(gè)哈希函數(shù)，總有一個(gè)哈希函數(shù)能夠使關(guān)鍵字不聚集。
公共溢出區(qū)法
在原先基礎(chǔ)表的基礎(chǔ)上再添加一個(gè)溢出表
當(dāng)發(fā)生沖突時(shí)，就將該數(shù)據(jù)放到溢出表中
在查找時(shí)，對給定值通過散列函數(shù)計(jì)算出散列地址后，先與基本表的相應(yīng)位置進(jìn)行對比，如果相等就查找成功，如果不相等，則到溢出表進(jìn)行順序查找。
鏈?zhǔn)降刂贩?/h3>
就時(shí)用鏈表將發(fā)生沖突的數(shù)據(jù)鏈起來，在查找時(shí)，只需要遍歷鏈表即可，此方法也是最常用的方法。
如圖：
哈希表的填充因子
填充因子就是 ：填入表中的鍵值對個(gè)數(shù) / 哈希表長度
填充因子標(biāo)志著哈希表的裝滿程度，散列表的平均查找長度取決于填充因子，而不是取決于查找集合的鍵值對個(gè)數(shù)。Java中的HashMap默認(rèn)初始容量為16，默認(rèn)加載因子為0.75(當(dāng)?shù)讓訑?shù)組容量占用75%時(shí)，數(shù)組開始擴(kuò)容,擴(kuò)容后容量是原容量的二倍)，此時(shí)雖然浪費(fèi)了一定空間，但是換來的是查找效率的大大提升。
代碼實(shí)現(xiàn)
下面用鏈?zhǔn)降刂贩▉韺?shí)現(xiàn)哈希表。
public class HashTableDemo {
//哈希表每個(gè)位置鏈表的節(jié)點(diǎn)
class Node{
//關(guān)鍵字
int key;
String value;
Node next;
//無參構(gòu)造
Node(){}
//有參構(gòu)造
Node(int key, String value){
this.key = key;
this.value = value;
next = null;
}
//重寫哈希表的equals()方法
public boolean equals(Node node){
if(this == node) return true;
else{
if(node == null) return false;
else{
return this.value == node.value && this.key == node.key;
}
}
}
}
//哈希表的長度
int length;
//哈希表存的鍵值對個(gè)數(shù)
int size;
//存儲數(shù)據(jù)容器
Node table[];
//不指定初始化長度的無參構(gòu)造
public HashTableDemo(){
length = 16;
size = 0;
table = new Node[length];
//為哈希表每一個(gè)位置初始化
for (int i = 0; i < length; i++) {
table[i] = new Node(i,null);
}
}
//指定初始化長度的有參構(gòu)造
public HashTableDemo(int length){
this.length = length;
size = 0;
table = new Node[length];
for (int i = 0; i < length; i++) {
table[i] = new Node(i,null);
}
}
}
哈希函數(shù)
public int hashFunc(int key){
return key % length;
}
添加數(shù)據(jù)
思路：
- 先通過哈希函數(shù)算出該鍵值對在table中的位置。
- 遍歷該處的鏈表的每一個(gè)節(jié)點(diǎn)，若發(fā)現(xiàn)某節(jié)點(diǎn)的key與傳入的key相等，那么就更新此處的value。
- 若未發(fā)現(xiàn)相等的key，那么在鏈表末尾添加新的節(jié)點(diǎn).
- 最后返回value。
代碼如下：
public String put(int key, String value){
int index = hashFunc(key);
//保證cur2始終是cur的前一個(gè)節(jié)點(diǎn)。
Node cur = table[index].next;
Node cur2 = table[index];
while(cur != null){
if(cur.key == key){
cur.value = value;
return value;
}
cur = cur.next;
cur2 = cur2.next;
}
cur2.next = new Node(key, value);
size++;
return value;
}
刪除數(shù)據(jù)
思路：
- 先通過哈希函數(shù)算出該鍵值對在table中的位置。
- 遍歷該處的鏈表的每一個(gè)節(jié)點(diǎn)，若發(fā)現(xiàn)某節(jié)點(diǎn)的key與傳入的key相等，那么就刪除此節(jié)點(diǎn)，并返回它的value。
- 若未發(fā)現(xiàn)相等的key，返回null。
代碼如下：
public String remove(int key){
int index = hashFunc(key);
Node cur = table[index];
while(cur.next != null){
if(cur.next.key == key){
size--;
String value = cur.next.value;
cur.next = cur.next.next;
return value;
}
cur = cur.next;
}
return null;
}
判斷哈希表是否為空
思路：判斷哈希表每個(gè)位置處的鏈表是否為空。
public boolean isEmpty(){
for(int i = 0; i < length; i++){
if(table[i].next != null)
return false;
}
return true;
}
遍歷哈希表
public void print(){
for(int i = 0; i < length; i++){
Node cur = table[i];
System.out.printf("第%d條鏈表: ",i);
if(cur.next == null){
System.out.println("null");
continue;
}
cur = cur.next;
while(cur != null){
System.out.print(cur.key + "---"+ cur.value + " ");
cur = cur.next;
}
System.out.println();
}
}
獲得哈希表已存鍵值對個(gè)數(shù)
//返回哈希表已存數(shù)據(jù)個(gè)數(shù)
public int size(){
return size;
}
到此這篇關(guān)于Java超詳細(xì)分析講解哈希表的文章就介紹到這了,更多相關(guān)Java哈希表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了Java調(diào)用linux shell腳本的方法,需要的朋友可以參考下2015-02-02
java Spring 5 新特性函數(shù)式Web框架詳細(xì)介紹
正如昨天Juergen博客中所提到的，Spring 5.0的第二個(gè)里程碑是引入了一個(gè)新的函數(shù)式web框架。在這篇文章中，我們將給出關(guān)于這個(gè)框架的更多信息，,需要的朋友可以參考下2016-12-12
這篇文章主要介紹了基于logback.xml不生效問題的解決方案，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-06-06
Java concurrency線程池之線程池原理(三)_動(dòng)力節(jié)點(diǎn)Java學(xué)院整理
這篇文章主要為大家詳細(xì)介紹了Java concurrency線程池之線程池原理第三篇，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-06-06
SpringBoot整合GRPC微服務(wù)遠(yuǎn)程通信的實(shí)現(xiàn)示例
本文主要介紹了SpringBoot整合GRPC微服務(wù)遠(yuǎn)程通信的實(shí)現(xiàn)示例,包含gRPC的工作原理,以及如何在Spring Boot應(yīng)用中集成gRPC,具有一定的參考價(jià)值,感興趣的可以了解一下2024-02-02
mybatis insert 返回自增主鍵的實(shí)現(xiàn)示例
mybatis 在新增之后怎么也獲取不到自增主鍵,本文主要介紹了mybatis insert 返回自增主鍵的實(shí)現(xiàn)示例,具有一定的參考價(jià)值,感興趣的可以了解一下2024-06-06
Java的動(dòng)態(tài)代理模式之JDK代理詳解
這篇文章主要介紹了Java的動(dòng)態(tài)代理模式之JDK代理詳解,代理對象,不需要實(shí)現(xiàn)接口,但是目標(biāo)對象要實(shí)現(xiàn)接口,否則不能用動(dòng)態(tài)代理,JDK?實(shí)現(xiàn)代理只需要使用?newProxyInstance?方法,但是該方法需要接收三個(gè)參數(shù),需要的朋友可以參考下2023-11-11
Java switch 語句如何使用 String 參數(shù)
這篇文章主要介紹了Java switch 語句如何使用 String 參數(shù),文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，,需要的朋友可以參考下2019-06-06
記錄jdk21連接SQLServer因?yàn)門LS協(xié)議報(bào)錯(cuò)問題
在使用Druid連接池連接SQL Server時(shí),可能會(huì)遇到因TLS版本不匹配導(dǎo)致的連接失敗問題,具體表現(xiàn)為客戶端使用TLS1.3或TLS1.2,而SQL Server僅支持TLS1.0,導(dǎo)致無法建立安全連接,解決方法是修改JDK的安全配置,啟用TLS1.02024-10-10
這篇文章主要給大家介紹了關(guān)于SpringBoot如何防止XSS注入攻擊的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-05-05