Java超詳細分析講解哈希表
哈希表概念
- 散列表，又稱為哈希表（Hash table），采用散列技術(shù)將記錄存儲在一塊連續(xù)的存儲空間中。
- 在散列表中，我們通過某個函數(shù)f，使得存儲位置 = f（關鍵字），這樣我們可以不需要比較關鍵字就可獲得需要的記錄的存儲位置。
- 散列技術(shù)的記錄之間不存在什么邏輯關系，它只與關鍵字有關聯(lián)。因此，散列主要是面向查找的存儲結(jié)構(gòu)。
哈希函數(shù)的構(gòu)造
構(gòu)造原則：
- 計算簡單
散列函數(shù)的計算時間不應該超過其他查找技術(shù)與關鍵字比較的時間。
- 散列地址分布均勻
解決沖突最好的辦法就是盡量讓散列地址均勻地分布在存儲空間中。
- 保證存儲空間的有效利用，并減少為處理沖突而耗費的時間。
構(gòu)造方法：
平均數(shù)取中法
假設關鍵字是1234，那么它的平方就是1522756.在抽取中間的3位就是227，用作散列地址。再比如關鍵字4321，那么它的平方就是18671041，抽中間三位數(shù)就是671或710。平方去中法比較適合不知道關鍵字的分布，而位數(shù)又不是很多的情況。
折疊法
折疊法是將關鍵字從左到右分割成位數(shù)相等的幾部分（注意最后一部分位數(shù)不夠時可以短一些），然后將這幾部分疊加求和，并按散列表表長，取幾位作為散列表地址。
比如我們的關鍵字是9 8 7 6 5 4 3 2 1 0，散列表表長為3位，我們將它分為四組，987|654|321|0，然后將他們疊加求和987+654+321+0=1962，再求后3位得到散列地址為962。
有時可能這還不能夠保證分布均勻，不妨從一端向另一端來回折疊后對齊相加。比如我們將987和321反轉(zhuǎn)，再與654和0相加，變成789+654+123+0=1566，此時散列地址為566。
折疊法事先不需要知道關鍵字的分布，適合關鍵字位數(shù)較多的情況。
保留余數(shù)法
此方法為最常用的構(gòu)造哈希函數(shù)的方法。
公式為：
f(key) = key mod p (p <= m)
代碼如下：
public int hashFunc(int key){
return key % length;
}
哈希沖突問題以及解決方法
哈希沖突就是，兩個不同的關鍵字，但是通過散列函數(shù)得出來的地址是一樣的。
key1 ≠ key2，但是f（key1）= f（key2）
同義詞
此時的key1 和key2就被稱為這個散列函數(shù)的同義詞
那可不行啊，一件單人間怎么可以住兩個人呢？
別擔心，這個問題自然已經(jīng)被神通廣大的大佬們解決了。
開放地址法
開發(fā)定址法就是一旦發(fā)生了沖突，就去尋找下一個空的散列地址，只需要散列表足夠大，空的散列地址總能找到，并將記錄存入
例子：
19 01 23 14 55 68 11 86 37
要存儲在表長11的數(shù)組中，其中H（key）=key MOD 11
再哈希函數(shù)法
對于我們的哈希表來說，我們事先需要準備多個哈希函數(shù)。每當發(fā)生散列地址沖突時，就換一個哈希函數(shù)，總有一個哈希函數(shù)能夠使關鍵字不聚集。
公共溢出區(qū)法
在原先基礎表的基礎上再添加一個溢出表
當發(fā)生沖突時，就將該數(shù)據(jù)放到溢出表中
在查找時，對給定值通過散列函數(shù)計算出散列地址后，先與基本表的相應位置進行對比，如果相等就查找成功，如果不相等，則到溢出表進行順序查找。
鏈式地址法
就時用鏈表將發(fā)生沖突的數(shù)據(jù)鏈起來，在查找時，只需要遍歷鏈表即可，此方法也是最常用的方法。
如圖：
哈希表的填充因子
填充因子就是 ：填入表中的鍵值對個數(shù) / 哈希表長度
填充因子標志著哈希表的裝滿程度，散列表的平均查找長度取決于填充因子，而不是取決于查找集合的鍵值對個數(shù)。Java中的HashMap默認初始容量為16，默認加載因子為0.75(當?shù)讓訑?shù)組容量占用75%時，數(shù)組開始擴容,擴容后容量是原容量的二倍)，此時雖然浪費了一定空間，但是換來的是查找效率的大大提升。
代碼實現(xiàn)
下面用鏈式地址法來實現(xiàn)哈希表。
public class HashTableDemo {
//哈希表每個位置鏈表的節(jié)點
class Node{
//關鍵字
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;
//哈希表存的鍵值對個數(shù)
int size;
//存儲數(shù)據(jù)容器
Node table[];
//不指定初始化長度的無參構(gòu)造
public HashTableDemo(){
length = 16;
size = 0;
table = new Node[length];
//為哈希表每一個位置初始化
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中的位置。
- 遍歷該處的鏈表的每一個節(jié)點，若發(fā)現(xiàn)某節(jié)點的key與傳入的key相等，那么就更新此處的value。
- 若未發(fā)現(xiàn)相等的key，那么在鏈表末尾添加新的節(jié)點.
- 最后返回value。
代碼如下：
public String put(int key, String value){
int index = hashFunc(key);
//保證cur2始終是cur的前一個節(jié)點。
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中的位置。
- 遍歷該處的鏈表的每一個節(jié)點，若發(fā)現(xiàn)某節(jié)點的key與傳入的key相等，那么就刪除此節(jié)點，并返回它的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;
}
判斷哈希表是否為空
思路：判斷哈希表每個位置處的鏈表是否為空。
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();
}
}
獲得哈希表已存鍵值對個數(shù)
//返回哈希表已存數(shù)據(jù)個數(shù)
public int size(){
return size;
}
到此這篇關于Java超詳細分析講解哈希表的文章就介紹到這了,更多相關Java哈希表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
AtomicInteger是java并發(fā)包下面提供的原子類,主要操作的是int類型的整型,通過調(diào)用底層Unsafe的CAS等方法實現(xiàn)原子操作,這篇文章主要給大家介紹了關于如何通過一文深入了解Java中AtomicInteger類的相關資料,需要的朋友可以參考下2024-02-02
新年將至，又開始掃福活動，每年的敬業(yè)福成了大家難過的坎。所以本文將介紹一個通過Java編寫的一款福字生成器，感興趣的小伙伴可以試一試2022-01-01
Java中四種訪問控制權(quán)限解析(private、default、protected、public)
java當中有4種訪問修飾限定符privat、default（默認訪問權(quán)限），protected以及public，本文就詳細的介紹一下這四種方法的具體使用，感興趣的可以了解一下2023-05-05
在本篇文章里我們給大家分享了java web實現(xiàn)分頁查詢的詳細方法知識點，有需要的朋友們參考學習下。2018-10-10
這篇文章主要介紹了SpringBoot中的main方法注入service操作，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-06-06
java使用TimerTask定時器獲取指定網(wǎng)絡數(shù)據(jù)
java.util.Timer定時器，實際上是個線程，定時調(diào)度所擁有的TimerTasks。一個TimerTask實際上就是一個擁有run方法的類，需要定時執(zhí)行的代碼放到run方法體內(nèi)，TimerTask一般是以匿名類的方式創(chuàng)建,下面的就用示例來學習他的使用方法2014-01-01
這篇文章主要介紹了Elasticsearch 基礎介紹及索引原理分析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-07-07
本文主要介紹了SpringBoot集成Auth0 JWT的示例代碼，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-08-08
這篇文章主要介紹了Springboot啟動停止命令的.sh腳本編寫方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-05-05
解析Java中所有錯誤和異常的父類java.lang.Throwable
這篇文章主要介紹了Java中所有錯誤和異常的父類java.lang.Throwable,文章中簡單地分析了其源碼,說明在代碼注釋中,需要的朋友可以參考下2016-03-03