hashMap對各位小伙們來說，沒有不知道的了，使用過的人想必或多或少的都了解一點hashMap的底層實現原理，總結來說就是，數組+鏈表，至于源碼的實現，大家可參看源碼，今天想說的是hashMap是怎么解決hash沖突的呢？
首先看一張圖，
從這張圖也大概可以看出來，hashMap維護的是一個數組，數組里面的每個單元又是一個個鏈表，那么為什么會產生hash沖突呢？這也就是接下來要探討的問題。
既是數組，必然會有長度，當我們在往數組中插入數據的時候，不管是什么類型的數據，對于數組來說，就是占據了某個下標對應的空間，那么當加入的數據越來越多的時候，是否會出現多個數據占據同一個位置呢？答案是肯定的，這就是hash沖突產生的原始因素；
首先，我們先弄清楚幾個概念，對于hashMap或者其他類似的map來說，我們往里面添加數據的時候，并不是直接往數組里面加，而是通過計算這個插入數據的hash值，即通過一個hash的算法，然后把這個值加進去，以后再去查找數據的時候，hashMap同樣會根據你的key，倒推出這個hash值然后取出數據，即這個hash值可以理解為插入值對應的數組下表；
但通過實驗我們可以發現，hash函數計算不同的key的時候，可能得到相同的hash值，這樣一來，如果再用這個hash值作為數組的標識這個值的下標，就無法定位這個值了，這個時候沖突就發生了；
下面我們用代碼來模擬一下這個使用開發地址法解決hash沖突的問題，首先定義一個對象，這里為Info,為了更接近真實場景，我們這里的屬性都為字符串，
什么是開放地址法呢？
當沖突發生的時候，通過查找數組的一個空位，將數據插入進去，而不再用hash函數計算獲取數的下標，這個方法就叫做開發地址法；
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;
/**
* 默認的構造方法
*/
public HashTable() {
arr = new Info[100];
}
/**
* 指定數組初始化大小
*/
public HashTable(int maxSize) {
arr = new Info[maxSize];
}
/**
* 插入數據
*/
public void insert(Info info) {
//獲得關鍵字
String key = info.getKey();
//關鍵字所自定的哈希數
int hashVal = hashCode(key);
//如果這個索引已經被占用，而且里面是一個未被刪除的數據
while(arr[hashVal] != null && arr[hashVal].getName() != null) {
//進行遞加，避免漏找
++hashVal;
//循環
hashVal %= arr.length;
}
arr[hashVal] = info;
}
/**
* 查找數據
*/
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;
}
/**
* 刪除數據
*/
public Info delete(String key) {
int hashVal = hashCode(key);
//循環查找，數組中下標為hashVal的值，沒有找到返回null
while(arr[hashVal] != null) {
if(arr[hashVal].getKey().equals(key)) {
Info tmp = arr[hashVal];
tmp.setName(null);
return tmp;
}
++hashVal; //由于數組的值是連續的，為了避免漏找，需要依次往下找
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();
}
}
可以看到，我們是通過對要插入的數值先進行hash編碼，再對數值的長度進行取模i，這樣得到的位置總能夠落在數值的長度內，
里面有個地方可能不太好理解，就是在插入數據的時候，我們使用while循環進行插入，既然是開發地址，也就是說數組的每一個閑置的空間我們都能使用，前提是這個位置沒有被其他的值占用，由于數組是連續的，所以我們需要循環的去尋找一個這樣的位置，所以才有 ++hashVal這段代碼，直到找到了一個空位，然后我們把數據插入進去，
運行測試main方法，我們看到，數據成功插入，但通過hash函數計算得到的“a”和"ct"卻是一樣的，再一次印證了我們前面所說的問題，
以上便是所說的采用開發地址法解決hash沖突的解決方法，但這樣就萬無一失了嗎？
我們考慮一下，數據的長度是有限的，但我們可能會往數組里面添加很多數據進去，數組總有被填滿的時候，那樣開發地址法也不管用了，當然，實際業務中，如果可以預料數據的大小，我們可以采用這樣的方式解決部分問題，但問題是這樣確實不是萬無一失的解決辦法，
更合適的方式是什么呢？其實就是hashMap中使用較多的鏈地址法，也就是一開始我們圖中展示的，基本結構仍然是一個數組，但是數組的每個單元維護的不再是一個個數據，而是一個個鏈表，也就是類似于linkedList這樣的結構,當新插入的多個數據通過計算hash函數得到的是相同的數組下標時候，我們只需要把值往這個索引位置維護的鏈表中插入即可，什么是鏈地址法呢？
**
在hash表每個單元中設置鏈表，某個要插入的數據項的關鍵字還是像通常那樣映射到hash表的某個單元中，而數據項的本身則被插入到該單元維護的鏈表中；
**
下面用代碼來實現一下這個過程，同上面所有不同的是，鏈表中的結構我們通過是維護者一個個節點，即Node ，對鏈表結構不熟悉的同學可以先自行百度一下，不是很難，
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 {
// 數據域
public Info info;
// 指針域,指向對下一個節點引用
public Node next;
public Node(Info info) {
this.info = info;
}
}
3、定義一個鏈表，
/**
* 模擬linkedList
*
* @author asus
*
*/
public class LinkList {
// 頭結點
private Node first;
public LinkList() {
first = null;
}
// 插入一個節點
public void insertFirst(Info info) {
Node node = new Node(info);
node.next = first;
first = node;
}
// 刪除一個節點，在頭結點后進行刪除
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;
/**
* 默認的構造方法
*/
public HashTable() {
arr = new LinkList[100];
}
/**
* 指定數組初始化大小
*/
public HashTable(int maxSize) {
arr = new LinkList[maxSize];
}
/**
* 插入數據
*/
public void insert(Info info) {
String key = info.getKey();
// 獲取關鍵字的自定義hash函數
int hashVal = hashCode(key);
if (arr[hashVal] == null) { //如果數組某個單元的位置為空，則需要重新構造一個linkList
arr[hashVal] = new LinkList();
}
arr[hashVal].insertFirst(info);
}
/**
* 查找數據
*/
public Info find(String key) {
int hashVal = hashCode(key);
return arr[hashVal].find(key).info;
}
/**
* 刪除數據
*/
public Info delete(String key){
int hashVal = hashCode(key);
return arr[hashVal].delete(key).info;
}
/**
* 自定義計算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();
}
}
和上面開發地址法插入數據和查找數據不同，此種方式進行數據查找的時候，其實是進行兩次查到的，第一次定位數組中的位置，第二次去到鏈表中，調用鏈表的查找方法進行查找，這一點值得注意，插入和刪除的思想也是類似，
下面我們來測試一下，可以看到，依然達到了效果，說明我們模擬的鏈地址法也生效了，
以上就是通過開發地址法和鏈地址法解決hash沖突的兩種方式，希望對大家理解hashMap的底層原理有所幫助…感謝觀看！也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
