Java超詳細分析講解哈希表
哈希表概念
- 散列表,又稱為哈希表(Hash table),采用散列技術(shù)將記錄存儲在一塊連續(xù)的存儲空間中。
- 在散列表中,我們通過某個函數(shù)f,使得存儲位置 = f(關(guān)鍵字),這樣我們可以不需要比較關(guān)鍵字就可獲得需要的記錄的存儲位置。
- 散列技術(shù)的記錄之間不存在什么邏輯關(guān)系,它只與關(guān)鍵字有關(guān)聯(lián)。因此,散列主要是面向查找的存儲結(jié)構(gòu)。
哈希函數(shù)的構(gòu)造
構(gòu)造原則:
- 計算簡單
散列函數(shù)的計算時間不應(yīng)該超過其他查找技術(shù)與關(guān)鍵字比較的時間。
- 散列地址分布均勻
解決沖突最好的辦法就是盡量讓散列地址均勻地分布在存儲空間中。
- 保證存儲空間的有效利用,并減少為處理沖突而耗費的時間。
構(gòu)造方法:
平均數(shù)取中法
假設(shè)關(guān)鍵字是1234,那么它的平方就是1522756.在抽取中間的3位就是227,用作散列地址。再比如關(guān)鍵字4321,那么它的平方就是18671041,抽中間三位數(shù)就是671或710。平方去中法比較適合不知道關(guān)鍵字的分布,而位數(shù)又不是很多的情況。
折疊法
折疊法是將關(guān)鍵字從左到右分割成位數(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。
有時可能這還不能夠保證分布均勻,不妨從一端向另一端來回折疊后對齊相加。比如我們將987和321反轉(zhuǎn),再與654和0相加,變成789+654+123+0=1566,此時散列地址為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; }
哈希沖突問題以及解決方法
哈希沖突就是,兩個不同的關(guān)鍵字,但是通過散列函數(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ù)能夠使關(guān)鍵字不聚集。
公共溢出區(qū)法
在原先基礎(chǔ)表的基礎(chǔ)上再添加一個溢出表
當發(fā)生沖突時,就將該數(shù)據(jù)放到溢出表中
在查找時,對給定值通過散列函數(shù)計算出散列地址后,先與基本表的相應(yīng)位置進行對比,如果相等就查找成功,如果不相等,則到溢出表進行順序查找。
鏈式地址法
就時用鏈表將發(fā)生沖突的數(shù)據(jù)鏈起來,在查找時,只需要遍歷鏈表即可,此方法也是最常用的方法。
如圖:
哈希表的填充因子
填充因子就是 :填入表中的鍵值對個數(shù) / 哈希表長度
填充因子標志著哈希表的裝滿程度,散列表的平均查找長度取決于填充因子,而不是取決于查找集合的鍵值對個數(shù)。Java中的HashMap默認初始容量為16,默認加載因子為0.75(當?shù)讓訑?shù)組容量占用75%時,數(shù)組開始擴容,擴容后容量是原容量的二倍),此時雖然浪費了一定空間,但是換來的是查找效率的大大提升。
代碼實現(xiàn)
下面用鏈式地址法來實現(xiàn)哈希表。
public class HashTableDemo { //哈希表每個位置鏈表的節(jié)點 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; //哈希表存的鍵值對個數(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; }
到此這篇關(guān)于Java超詳細分析講解哈希表的文章就介紹到這了,更多相關(guān)Java哈希表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
java Spring 5 新特性函數(shù)式Web框架詳細介紹
正如昨天Juergen博客中所提到的,Spring 5.0的第二個里程碑是引入了一個新的函數(shù)式web框架。在這篇文章中,我們將給出關(guān)于這個框架的更多信息,,需要的朋友可以參考下2016-12-12Java concurrency線程池之線程池原理(三)_動力節(jié)點Java學(xué)院整理
這篇文章主要為大家詳細介紹了Java concurrency線程池之線程池原理第三篇,具有一定的參考價值,感興趣的小伙伴們可以參考一下2017-06-06SpringBoot整合GRPC微服務(wù)遠程通信的實現(xiàn)示例
本文主要介紹了SpringBoot整合GRPC微服務(wù)遠程通信的實現(xiàn)示例,包含gRPC的工作原理,以及如何在Spring Boot應(yīng)用中集成gRPC,具有一定的參考價值,感興趣的可以了解一下2024-02-02mybatis insert 返回自增主鍵的實現(xiàn)示例
mybatis 在新增之后怎么也獲取不到自增主鍵,本文主要介紹了mybatis insert 返回自增主鍵的實現(xiàn)示例,具有一定的參考價值,感興趣的可以了解一下2024-06-06Java switch 語句如何使用 String 參數(shù)
這篇文章主要介紹了Java switch 語句如何使用 String 參數(shù),文中通過示例代碼介紹的非常詳細,對大家的學(xué)習或者工作具有一定的參考學(xué)習價值,,需要的朋友可以參考下2019-06-06記錄jdk21連接SQLServer因為TLS協(xié)議報錯問題
在使用Druid連接池連接SQL Server時,可能會遇到因TLS版本不匹配導(dǎo)致的連接失敗問題,具體表現(xiàn)為客戶端使用TLS1.3或TLS1.2,而SQL Server僅支持TLS1.0,導(dǎo)致無法建立安全連接,解決方法是修改JDK的安全配置,啟用TLS1.02024-10-10