java開放地址法和鏈地址法解決hash沖突的方法示例
hashMap對各位小伙們來說,沒有不知道的了,使用過的人想必或多或少的都了解一點hashMap的底層實現(xiàn)原理,總結(jié)來說就是,數(shù)組+鏈表,至于源碼的實現(xiàn),大家可參看源碼,今天想說的是hashMap是怎么解決hash沖突的呢?
首先看一張圖,
從這張圖也大概可以看出來,hashMap維護(hù)的是一個數(shù)組,數(shù)組里面的每個單元又是一個個鏈表,那么為什么會產(chǎn)生hash沖突呢?這也就是接下來要探討的問題。
既是數(shù)組,必然會有長度,當(dāng)我們在往數(shù)組中插入數(shù)據(jù)的時候,不管是什么類型的數(shù)據(jù),對于數(shù)組來說,就是占據(jù)了某個下標(biāo)對應(yīng)的空間,那么當(dāng)加入的數(shù)據(jù)越來越多的時候,是否會出現(xiàn)多個數(shù)據(jù)占據(jù)同一個位置呢?答案是肯定的,這就是hash沖突產(chǎn)生的原始因素;
首先,我們先弄清楚幾個概念,對于hashMap或者其他類似的map來說,我們往里面添加數(shù)據(jù)的時候,并不是直接往數(shù)組里面加,而是通過計算這個插入數(shù)據(jù)的hash值,即通過一個hash的算法,然后把這個值加進(jìn)去,以后再去查找數(shù)據(jù)的時候,hashMap同樣會根據(jù)你的key,倒推出這個hash值然后取出數(shù)據(jù),即這個hash值可以理解為插入值對應(yīng)的數(shù)組下表;
但通過實驗我們可以發(fā)現(xiàn),hash函數(shù)計算不同的key的時候,可能得到相同的hash值,這樣一來,如果再用這個hash值作為數(shù)組的標(biāo)識這個值的下標(biāo),就無法定位這個值了,這個時候沖突就發(fā)生了;
下面我們用代碼來模擬一下這個使用開發(fā)地址法解決hash沖突的問題,首先定義一個對象,這里為Info,為了更接近真實場景,我們這里的屬性都為字符串,
什么是開放地址法呢?
當(dāng)沖突發(fā)生的時候,通過查找數(shù)組的一個空位,將數(shù)據(jù)插入進(jìn)去,而不再用hash函數(shù)計算獲取數(shù)的下標(biāo),這個方法就叫做開發(fā)地址法;
public class Info { private String key; //關(guān)鍵字,或者能標(biāo)識對象的唯一屬性 private String name; //值域 public Info(String key, String name) { this.key = key; this.name = name; } public String getKey() { return key; } public void setKey(String key) { this.key = key; } public String getName() { return name; } public void setName(String name) { this.name = name; } }
接下來手工寫一個hashTable,用于模擬hashMap,
/** * 模擬hashMap * */ public class HashTable { private Info[] arr; /** * 默認(rèn)的構(gòu)造方法 */ public HashTable() { arr = new Info[100]; } /** * 指定數(shù)組初始化大小 */ public HashTable(int maxSize) { arr = new Info[maxSize]; } /** * 插入數(shù)據(jù) */ public void insert(Info info) { //獲得關(guān)鍵字 String key = info.getKey(); //關(guān)鍵字所自定的哈希數(shù) int hashVal = hashCode(key); //如果這個索引已經(jīng)被占用,而且里面是一個未被刪除的數(shù)據(jù) while(arr[hashVal] != null && arr[hashVal].getName() != null) { //進(jìn)行遞加,避免漏找 ++hashVal; //循環(huán) hashVal %= arr.length; } arr[hashVal] = info; } /** * 查找數(shù)據(jù) */ public Info find(String key) { int hashVal = hashCode(key); while(arr[hashVal] != null) { if(arr[hashVal].getKey().equals(key)) { return arr[hashVal]; } ++hashVal; hashVal %= arr.length; } return null; } /** * 刪除數(shù)據(jù) */ public Info delete(String key) { int hashVal = hashCode(key); //循環(huán)查找,數(shù)組中下標(biāo)為hashVal的值,沒有找到返回null while(arr[hashVal] != null) { if(arr[hashVal].getKey().equals(key)) { Info tmp = arr[hashVal]; tmp.setName(null); return tmp; } ++hashVal; //由于數(shù)組的值是連續(xù)的,為了避免漏找,需要依次往下找 hashVal %= arr.length; } return null; } /** * 獲得關(guān)鍵字的hash值,也可以自定義 */ public int hashCode(String key) { BigInteger hashVal = new BigInteger("0"); BigInteger pow27 = new BigInteger("1"); for(int i = key.length() - 1; i >= 0; i--) { int letter = key.charAt(i) - 96; BigInteger letterB = new BigInteger(String.valueOf(letter)); hashVal = hashVal.add(letterB.multiply(pow27)); pow27 = pow27.multiply(new BigInteger(String.valueOf(27))); } return hashVal.mod(new BigInteger(String.valueOf(arr.length))).intValue(); } }
可以看到,我們是通過對要插入的數(shù)值先進(jìn)行hash編碼,再對數(shù)值的長度進(jìn)行取模i,這樣得到的位置總能夠落在數(shù)值的長度內(nèi),
里面有個地方可能不太好理解,就是在插入數(shù)據(jù)的時候,我們使用while循環(huán)進(jìn)行插入,既然是開發(fā)地址,也就是說數(shù)組的每一個閑置的空間我們都能使用,前提是這個位置沒有被其他的值占用,由于數(shù)組是連續(xù)的,所以我們需要循環(huán)的去尋找一個這樣的位置,所以才有 ++hashVal這段代碼,直到找到了一個空位,然后我們把數(shù)據(jù)插入進(jìn)去,
運行測試main方法,我們看到,數(shù)據(jù)成功插入,但通過hash函數(shù)計算得到的“a”和"ct"卻是一樣的,再一次印證了我們前面所說的問題,
以上便是所說的采用開發(fā)地址法解決hash沖突的解決方法,但這樣就萬無一失了嗎?
我們考慮一下,數(shù)據(jù)的長度是有限的,但我們可能會往數(shù)組里面添加很多數(shù)據(jù)進(jìn)去,數(shù)組總有被填滿的時候,那樣開發(fā)地址法也不管用了,當(dāng)然,實際業(yè)務(wù)中,如果可以預(yù)料數(shù)據(jù)的大小,我們可以采用這樣的方式解決部分問題,但問題是這樣確實不是萬無一失的解決辦法,
更合適的方式是什么呢?其實就是hashMap中使用較多的鏈地址法,也就是一開始我們圖中展示的,基本結(jié)構(gòu)仍然是一個數(shù)組,但是數(shù)組的每個單元維護(hù)的不再是一個個數(shù)據(jù),而是一個個鏈表,也就是類似于linkedList這樣的結(jié)構(gòu),當(dāng)新插入的多個數(shù)據(jù)通過計算hash函數(shù)得到的是相同的數(shù)組下標(biāo)時候,我們只需要把值往這個索引位置維護(hù)的鏈表中插入即可,什么是鏈地址法呢?
**
在hash表每個單元中設(shè)置鏈表,某個要插入的數(shù)據(jù)項的關(guān)鍵字還是像通常那樣映射到hash表的某個單元中,而數(shù)據(jù)項的本身則被插入到該單元維護(hù)的鏈表中;
**
下面用代碼來實現(xiàn)一下這個過程,同上面所有不同的是,鏈表中的結(jié)構(gòu)我們通過是維護(hù)者一個個節(jié)點,即Node ,對鏈表結(jié)構(gòu)不熟悉的同學(xué)可以先自行百度一下,不是很難,
1、定義一個對象Info,
public class Info { private String key; private String name; public Info(String key, String name) { this.key = key; this.name = name; } public String getKey() { return key; } public void setKey(String key) { this.key = key; } public String getName() { return name; } public void setName(String name) { this.name = name; } }
2、定義一個Node作為鏈表中的基本存儲單元,
public class Node { // 數(shù)據(jù)域 public Info info; // 指針域,指向?qū)ο乱粋€節(jié)點引用 public Node next; public Node(Info info) { this.info = info; } }
3、定義一個鏈表,
/** * 模擬linkedList * * @author asus * */ public class LinkList { // 頭結(jié)點 private Node first; public LinkList() { first = null; } // 插入一個節(jié)點 public void insertFirst(Info info) { Node node = new Node(info); node.next = first; first = node; } // 刪除一個節(jié)點,在頭結(jié)點后進(jìn)行刪除 public Node deleteFirst() { Node temp = first; first = temp.next; return temp; } /** * 查找方法 */ public Node find(String key) { Node current = first; while (!key.equals(current.info.getKey())) { if (current.next == null) { return null; } current = current.next; } return current; } /** * 刪除方法 */ public Node delete(String key) { Node current = first; Node previous = first; while (!key.equals(current.info.getKey())) { if (current.next == null) { return null; } previous = current; current = current.next; } if (current == first) { first = first.next; } else { previous.next = current.next; } return current; } }
4、模擬hashMap的幾個方法,
public class HashTable { private LinkList[] arr; /** * 默認(rèn)的構(gòu)造方法 */ public HashTable() { arr = new LinkList[100]; } /** * 指定數(shù)組初始化大小 */ public HashTable(int maxSize) { arr = new LinkList[maxSize]; } /** * 插入數(shù)據(jù) */ public void insert(Info info) { String key = info.getKey(); // 獲取關(guān)鍵字的自定義hash函數(shù) int hashVal = hashCode(key); if (arr[hashVal] == null) { //如果數(shù)組某個單元的位置為空,則需要重新構(gòu)造一個linkList arr[hashVal] = new LinkList(); } arr[hashVal].insertFirst(info); } /** * 查找數(shù)據(jù) */ public Info find(String key) { int hashVal = hashCode(key); return arr[hashVal].find(key).info; } /** * 刪除數(shù)據(jù) */ public Info delete(String key){ int hashVal = hashCode(key); return arr[hashVal].delete(key).info; } /** * 自定義計算hash的函數(shù) */ public int hashCode(String key) { BigInteger hashVal = new BigInteger("0"); BigInteger pow27 = new BigInteger("1"); for (int i = key.length() - 1; i >= 0; i--) { int letter = key.charAt(i) - 96; BigInteger letterB = new BigInteger(String.valueOf(letter)); hashVal = hashVal.add(letterB.multiply(pow27)); pow27 = pow27.multiply(new BigInteger(String.valueOf(27))); } return hashVal.mod(new BigInteger(String.valueOf(arr.length))).intValue(); } }
和上面開發(fā)地址法插入數(shù)據(jù)和查找數(shù)據(jù)不同,此種方式進(jìn)行數(shù)據(jù)查找的時候,其實是進(jìn)行兩次查到的,第一次定位數(shù)組中的位置,第二次去到鏈表中,調(diào)用鏈表的查找方法進(jìn)行查找,這一點值得注意,插入和刪除的思想也是類似,
下面我們來測試一下,可以看到,依然達(dá)到了效果,說明我們模擬的鏈地址法也生效了,
以上就是通過開發(fā)地址法和鏈地址法解決hash沖突的兩種方式,希望對大家理解hashMap的底層原理有所幫助…感謝觀看!也希望大家多多支持腳本之家。
相關(guān)文章
Java?synchronized底層實現(xiàn)原理以及鎖優(yōu)化
Synchronized是Java中解決并發(fā)問題的一種最常用的方法,也是最簡單的一種方法,下面這篇文章主要給大家介紹了關(guān)于Java?synchronized底層實現(xiàn)原理以及鎖優(yōu)化的相關(guān)資料,需要的朋友可以參考下2022-02-02基于servlet的執(zhí)行原理與生命周期(全面解析)
下面小編就為大家分享一篇servlet的執(zhí)行原理與生命周期全面解析,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2017-12-12解決maven常見錯誤:Dependency is duplicated in
這篇文章主要介紹了解決maven常見錯誤:Dependency is duplicated in file(s):問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-04-04Java中連接Mongodb進(jìn)行增刪改查的操作詳解
MongoDB是一個基于分布式文件存儲的數(shù)據(jù)庫,由C++語言編寫,旨在為WEB應(yīng)用提供可擴展的高性能數(shù)據(jù)存儲解決方案,本文給大家介紹了Java中連接Mongodb進(jìn)行操作,文中有詳細(xì)的代碼示例供大家參考,需要的朋友可以參考下2024-06-06