java開放地址法和鏈地址法解決hash沖突的方法示例
hashMap對各位小伙們來說，沒有不知道的了，使用過的人想必或多或少的都了解一點hashMap的底層實現(xiàn)原理，總結(jié)來說就是，數(shù)組+鏈表，至于源碼的實現(xiàn)，大家可參看源碼，今天想說的是hashMap是怎么解決hash沖突的呢？
首先看一張圖，
從這張圖也大概可以看出來，hashMap維護的是一個數(shù)組，數(shù)組里面的每個單元又是一個個鏈表，那么為什么會產(chǎn)生hash沖突呢？這也就是接下來要探討的問題。
既是數(shù)組，必然會有長度，當我們在往數(shù)組中插入數(shù)據(jù)的時候，不管是什么類型的數(shù)據(jù)，對于數(shù)組來說，就是占據(jù)了某個下標對應的空間，那么當加入的數(shù)據(jù)越來越多的時候，是否會出現(xiàn)多個數(shù)據(jù)占據(jù)同一個位置呢？答案是肯定的，這就是hash沖突產(chǎn)生的原始因素；
首先，我們先弄清楚幾個概念，對于hashMap或者其他類似的map來說，我們往里面添加數(shù)據(jù)的時候，并不是直接往數(shù)組里面加，而是通過計算這個插入數(shù)據(jù)的hash值，即通過一個hash的算法，然后把這個值加進去，以后再去查找數(shù)據(jù)的時候，hashMap同樣會根據(jù)你的key，倒推出這個hash值然后取出數(shù)據(jù)，即這個hash值可以理解為插入值對應的數(shù)組下表；
但通過實驗我們可以發(fā)現(xiàn)，hash函數(shù)計算不同的key的時候，可能得到相同的hash值，這樣一來，如果再用這個hash值作為數(shù)組的標識這個值的下標，就無法定位這個值了，這個時候沖突就發(fā)生了；
下面我們用代碼來模擬一下這個使用開發(fā)地址法解決hash沖突的問題，首先定義一個對象，這里為Info,為了更接近真實場景，我們這里的屬性都為字符串，
什么是開放地址法呢？
當沖突發(fā)生的時候，通過查找數(shù)組的一個空位，將數(shù)據(jù)插入進去，而不再用hash函數(shù)計算獲取數(shù)的下標，這個方法就叫做開發(fā)地址法；
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;
}
}
接下來手工寫一個hashTable，用于模擬hashMap,
/**
* 模擬hashMap
*
*/
public class HashTable {
private Info[] arr;
/**
* 默認的構(gòu)造方法
*/
public HashTable() {
arr = new Info[100];
}
/**
* 指定數(shù)組初始化大小
*/
public HashTable(int maxSize) {
arr = new Info[maxSize];
}
/**
* 插入數(shù)據(jù)
*/
public void insert(Info info) {
//獲得關鍵字
String key = info.getKey();
//關鍵字所自定的哈希數(shù)
int hashVal = hashCode(key);
//如果這個索引已經(jīng)被占用，而且里面是一個未被刪除的數(shù)據(jù)
while(arr[hashVal] != null && arr[hashVal].getName() != null) {
//進行遞加，避免漏找
++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ù)組中下標為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;
}
/**
* 獲得關鍵字的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ù)值先進行hash編碼，再對數(shù)值的長度進行取模i，這樣得到的位置總能夠落在數(shù)值的長度內(nèi)，
里面有個地方可能不太好理解，就是在插入數(shù)據(jù)的時候，我們使用while循環(huán)進行插入，既然是開發(fā)地址，也就是說數(shù)組的每一個閑置的空間我們都能使用，前提是這個位置沒有被其他的值占用，由于數(shù)組是連續(xù)的，所以我們需要循環(huán)的去尋找一個這樣的位置，所以才有 ++hashVal這段代碼，直到找到了一個空位，然后我們把數(shù)據(jù)插入進去，
運行測試main方法，我們看到，數(shù)據(jù)成功插入，但通過hash函數(shù)計算得到的“a”和"ct"卻是一樣的，再一次印證了我們前面所說的問題，
以上便是所說的采用開發(fā)地址法解決hash沖突的解決方法，但這樣就萬無一失了嗎？
我們考慮一下，數(shù)據(jù)的長度是有限的，但我們可能會往數(shù)組里面添加很多數(shù)據(jù)進去，數(shù)組總有被填滿的時候，那樣開發(fā)地址法也不管用了，當然，實際業(yè)務中，如果可以預料數(shù)據(jù)的大小，我們可以采用這樣的方式解決部分問題，但問題是這樣確實不是萬無一失的解決辦法，
更合適的方式是什么呢？其實就是hashMap中使用較多的鏈地址法，也就是一開始我們圖中展示的，基本結(jié)構(gòu)仍然是一個數(shù)組，但是數(shù)組的每個單元維護的不再是一個個數(shù)據(jù)，而是一個個鏈表，也就是類似于linkedList這樣的結(jié)構(gòu),當新插入的多個數(shù)據(jù)通過計算hash函數(shù)得到的是相同的數(shù)組下標時候，我們只需要把值往這個索引位置維護的鏈表中插入即可，什么是鏈地址法呢？
**
在hash表每個單元中設置鏈表，某個要插入的數(shù)據(jù)項的關鍵字還是像通常那樣映射到hash表的某個單元中，而數(shù)據(jù)項的本身則被插入到該單元維護的鏈表中；
**
下面用代碼來實現(xiàn)一下這個過程，同上面所有不同的是，鏈表中的結(jié)構(gòu)我們通過是維護者一個個節(jié)點，即Node ，對鏈表結(jié)構(gòu)不熟悉的同學可以先自行百度一下，不是很難，
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é)點后進行刪除
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;
/**
* 默認的構(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();
// 獲取關鍵字的自定義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ù)不同，此種方式進行數(shù)據(jù)查找的時候，其實是進行兩次查到的，第一次定位數(shù)組中的位置，第二次去到鏈表中，調(diào)用鏈表的查找方法進行查找，這一點值得注意，插入和刪除的思想也是類似，
下面我們來測試一下，可以看到，依然達到了效果，說明我們模擬的鏈地址法也生效了，
以上就是通過開發(fā)地址法和鏈地址法解決hash沖突的兩種方式，希望對大家理解hashMap的底層原理有所幫助…感謝觀看！也希望大家多多支持腳本之家。
相關文章
這篇文章主要為大家詳細介紹了JavaWeb文件上傳入門教程，分析了文件上傳原理、介紹了第三方上傳組件，感興趣的小伙伴們可以參考一下2016-06-06
這篇文章主要介紹了SpringBoot整合第三方技術,包括整合Junit、整合Mybatis,本文通過實例代碼相結(jié)合給大家介紹的非常詳細，需要的朋友可以參考下2022-08-08
解讀CommandLineRunner或者ApplicationRunner接口
這篇文章主要介紹了解讀CommandLineRunner或者ApplicationRunner接口的使用，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-02-02
這篇文章主要介紹了java 調(diào)用Python文件包括傳參的實現(xiàn)方式，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-04-04
Java使用反射和動態(tài)代理實現(xiàn)一個View注解綁定庫
這篇文章主要介紹了Java使用反射和動態(tài)代理實現(xiàn)一個View注解綁定庫,代碼簡潔，使用簡單，擴展性強，結(jié)合實例代碼給大家介紹的非常詳細，需要的朋友可以參考下2022-05-05
這篇文章主要介紹了淺談一下Java中集合的迭代方式,可以幫助我們學習，理解函數(shù)式編程,需要的朋友可以參考下2023-04-04
這篇文章主要介紹了如何使用SpringSecurity保護程序安全，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-09-09
這篇文章主要介紹了Spring Boot 集成MyBatis 教程詳解,非常不錯，具有參考借鑒價值，需要的朋友可以參考下2017-04-04
SpringBoot中的ApplicationRunner與CommandLineRunner問題
這篇文章主要介紹了SpringBoot中的ApplicationRunner與CommandLineRunner問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-09-09
正則表達式的強大眾所周知，它令程序員的頭痛程度也數(shù)一數(shù)二的。下面這篇文章主要給大家介紹了關于Java API學習教程之正則表達式的相關資料，文中通過示例代碼介紹的非常詳細，對大家具有一定的參考學習價值，需要的朋友們下面來一起看看吧。2017-07-07