溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容主要講解“Java散列表怎么實現”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“Java散列表怎么實現”吧!
數組的特點是尋址容易，插入和刪除困難；而鏈表的特點是尋址困難，插入和刪除容易。而對于tree結構，它們的查找都是先從根節點進行查找，從節點取出數據或索引與查找值進行比較，雖然查找和增刪的綜合效率較好，但是最終還是需要進行多次查找。為此引入了散列表來嘗試進一步提升查找效率和增刪的綜合效率。
之前所掌握的查找算法，最簡單的順序表結構查找包括簡單的順序查找、二分查找、插值查找、斐波那契查找，以及后來的樹結構查找包括二叉排序樹、平衡二叉樹、多路查找樹、紅黑樹等。它們有一個功能特點就是，要查找的元素始終要與已經存在的元素進行多次比較，才能最終的出要該的元素是否存在或者不存在的結果。
我們知道，這些比較用于逐漸的定位某一個確切的位置，上面的大部分查找算法要求數據必須是有序存儲的，算法就是通過比較兩個數據的大小來縮小查找的范圍，最終找到一個大小相等的數據，或說明該元素存在，或者最終也沒有找到一個大小相等的數據，說明不存在。
為什么一定要“比較”？能否直接通過關鍵字key得到要查找的記錄內存存儲位置呢？當然有，這就是散列表。
事先在數據(這里可以是key-value鍵值對形式的數據，也可以是單個key形式的數據)的存儲位置和它的關鍵字之間建立一個確定的對應函數關系f，使得每個關鍵字k對應一個存儲位置f（key）。即：存儲位置=f(key)，該映射被稱為散列函數，利用散列函數來存儲數據的數據結構被稱為散列表。通過f(key)計算出存儲位置的過程被稱為散列，所得的存儲位置稱散列地址。
散列表通常基于數組來實現。存放數據的時候，散列函數f(key)根據key計算出數據應該存儲的位置-數組下標，從而將不同的數據分散在不同的存儲位置，這也是“散列”的由來；查找的時候，通過散列函數f(key)對應的key可以直接確定查找值所在位置-數組下標，而不需要一個個比較。這樣就“預先知道”key所在的位置，直接找到數據，提升效率。散列表存放元素的數組位置也被稱為“槽（slot）”。
散列表與線性表、樹、圖等結構不同的是，后幾種結構數據元素之間都存在某種邏輯關系，而使用散列技術的散列表的數據元素之間不存在什么邏輯關系，元素的位置只與關鍵字key和散列函數f(key)有關聯。
對于查找來說，散列技術簡化了比較過程，效率就會大大提高，但萬事有利就有弊，由于數據元素之間并沒有確切的關系，散列技術不具備很多常規數據結構的能力。相對于其他查找結構，它只支持部分操作（查找、增刪……），另一部分操作不能實現（排序、索引操作、范圍查找、順序輸出、查找最大/小值……）。因此，散列表主要是面向查找的存儲結構。
散列表的英文名稱為 hash table，因此散列表又被稱為哈希表，散列函數又被稱為哈希函數，函數的實現步驟被稱為散列算法/哈希算法。
我們還能看出來，散列算法實際上是將任意長度的key變換成固定范圍長度的值。這種轉換是一種壓縮映射，簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。也就是，散列值的范圍大小通常遠小于輸入的key的范圍。
例如，輸入的key為5,28,19,15,20,33,12,17,10，共9個，此時肯定不能將哈希表（內部數組）的長度初始化為33，那樣的話就太浪費空間了。理想的結果是，將這9個key通過某個散列函數f(key)將它們放入長度為10的哈希表（數組）中，并且然而由于散列算法是一種壓縮映射算法，散列表的長度單元是有限的，關鍵字key是無限的，對于某個散列算法，如果key樣本如果大，那么兩個不同的key映射到相同的單元，即f(key)的值相等的情況幾乎是一種必然，這種現象也被稱為散列沖突/哈希沖突。
例如對上面的key個數采用的散列函數是f(key)=key mod 9，f(5)=5，所以數據5應該放在散列表的第5個槽里；f(28)=1，所以數據28應該放在散列表的第1個槽里；f(19)=1，也就是說，數據19也應該放在散列表表的第1個槽里——于是就造成了碰撞。
盡管我們可以通過精心設計的散列函數讓沖突盡可能的少，但是不能完全避免。因此散列表必須具備處理散列沖突的能力。
從上面的散列表的概述可以看出來，要實現散列表，最關鍵的就是散列函數f(key)的選擇和處理散列沖突的能力，我們先來看散列函數的選擇。
良好的散列函數應該滿足下面兩個原則：
計算簡單：如果散列算法需要很復雜的計算，會耗費很多時間，這對于需要頻繁地查找來說，就會大大降低查找的效率了。因此散列函數的計算時間不應該超過其他查找技術與關鍵字比較的時間。
散列地址分布均勻：我們剛才也提到沖突帶來的問題，雖然不能完全避免沖突，但是可能設計好的散列函數盡量讓散列地址均勻地分布在存儲空間中，這樣可以保證存儲空間的有效利用，并減少沖突的發生和為處理沖突而耗費的時間。 下面介紹幾種常用的散列函數構造方法！
直接定址法
取關鍵字或關鍵字的某個線性函數值為散列地址（這種散列函數也叫自身函數）。f(key)=a×key+b（a、b為常數）。
比如對0-100歲人口數統計，直接采用年齡作為關鍵字。
比如統計1980年忠厚每年出生的人口數目，我們可以對出生年份關鍵字減去1980來作為地址。
這樣的散列函數優點就是簡單、均勻，也不會產生沖突，但問題是這需要事先知道關鍵字的分布情況，適合查找表較小且連續的情況。由于這樣的限制，在現實應用中，此方法雖然簡單，但卻并不常用。
數字分析法
假設關鍵字是以r為基的數，并且哈希表中可能出現的關鍵字都是事先知道的，則可取關鍵字的若干數位組成哈希地址。
比如對于手機號碼的key，用手機號碼后四位參與計算。
數字分析法通常適合處理關鍵字位數比較大的情況，如果事先知道關鍵字的分布且關鍵字的若干位分布較均勻，就可以考慮用這個方法。
折疊法
將關鍵字從左到右分割成位數相等的幾部分（注意最后一部分位數不夠時可以短些），然后將這幾部分疊加求和，并按散列表表長，取后幾位作為散列地址。 比如我們的關鍵字是9876543210，散列表表長為三位，我們將它分為四組，987|654|321|0，然后將它們疊加求和987+654+321+0=1962，再求后3位得到散列地址為962。
有時可能這還不能夠保證分布均勻，不妨從一端向另一端來回折疊后對齊相加。比如我們將987和321反轉，再與654和0相加，變成789+654+123+0=1566，此時散列地址為566。
折疊法事先不需要知道關鍵字的分布，適合關鍵字位數較多的情況。
平方取中法
取關鍵字平方后的中間幾位為哈希地址。通過平方擴大差別，另外中間幾位與乘數的每一位相關，由此產生的散列地址較為均勻。
假設關鍵字是1234，那么它的平方就是1522756，再抽取中間的3位就是227，用做散列地址。再比如關鍵字是4321，那么它的平方就是18671041，抽取中間的3位就可以是671，也可以是710，用做散列地址。
平方取中法比較適合于不知道關鍵字的分布，而位數又不是很大的情況。
除留余數法
此方法為最常用的構造散列函數方法。對于散列表長為m的散列函數公式為：f(key)=key mod p(p≤m)
mod是取模（求余數）的意思。事實上，這方法不僅可以對關鍵字直接取模，也可在折疊、平方取中后再取模。很顯然，本方法的關鍵就在于選擇合適的p，p如果選得不好，就可能會容易產生沖突。HashMap就采用了這種方法（利用位運算代替取模運算，提高程序的計算效率）。需要注意的是，只有在特定情況下，位運算才可以轉換成取模運算（當 b = 2^n 時，a % b = a & (b - 1) ）。
因此根據前輩們的經驗，若散列表表長為m，通常p為小于或等于表長（最好接近m）的最小質數或不包含小于20質因子的合數。
隨機數法
選擇一個隨機數，取關鍵字的隨機函數值為它的散列地址。也就是：f(key)=random(key)
這里random是隨機函數。當關鍵字的長度不等時，采用這個方法構造散列函數是比較合適的。
總之，現實中，應該視不同的情況采用不同的散列函數。我們只能給出一些考慮的因素來提供參考：
1.計算散列地址所需的時間。
2.關鍵字的長度。
3.散列表的大小。
4.關鍵字的分布情況。
5.記錄查找的頻率。
綜合這些因素，才能決策選擇哪種散列函數更合適。
設計得再好的散列函數也不可能完全避免沖突。對無論以何種散列函數構建的散列表，還必須考慮如何處理散列沖突。常見方法有以下幾種：
使用輔助數據結構：分離鏈接法/鏈地址法/拉鏈法
不使用輔助數據結構：開放定址法（線性探測、平方探測、雙散列）
再散列
在存儲數據的過程中，如果發生沖突，可以利用單鏈表在已有數據的后面插入新數據，訪問的數組下標元素作為鏈表的頭部。這種解決沖突的方法被稱為“分離鏈接法”，又被稱為分離鏈接法、拉鏈法。可以想象，除了鏈表之外，其他輔助結構都能解決沖突現象：二叉樹或者另一張散列表，如果采用鏈表來輔助解決散列沖突，并且散列函數設計的很好，那么鏈表應該是比較短的，此時其他復雜的輔助結構便不值得嘗試了。
如下圖，使用鏈地址法的散列表：
JDK1.8之前的HashMap就是使用的鏈表來處理散列沖突，為了降低鏈表過長造成的遍歷性能損耗，在JDK1.8中采用鏈表+紅黑樹的方法來處理散列沖突，當鏈表長度大于8個時，轉換為紅黑樹，紅黑樹的查找效率明顯高于單鏈表的。而小于等于8個時，采用鏈表則完全可以接受，避免紅黑樹的復雜結構。
開放定址法的基本思路就是出現沖突時，通過另外的算法尋找其他空余的位置，因此不需要額外的輔助數據結構，只要散列表足夠大，空的散列地址總能找到，并將記錄存入。
開放定址法法又可以分為線性探測法、平方探測法、雙散列法。
3.2.1 線性探測法(Linear Probing)
線性探測公式為：（H（key）+di）％ m；其中H（key）為哈希函數，m 為表長-1，di為一個增量序列（di=0,1,2,3...,m-1）。
線性探測法的主要思想是：當發生碰撞時（一個鍵被散列到一個已經有鍵值對的數組位置），我們會檢查數組的下一個位置，這個過程被稱作線性探測。線性探測可能會產生三種結果：
命中：該位置的鍵與要查找的鍵相同；
未命中：該位置為空；
該位置的鍵和被查找的鍵不同。
當我們查找某個鍵時，首先通過散列函數得到一個數組索引后，之后我們就開始檢查相應位置的鍵是否與給定鍵相同，若不同則繼續查找（若到數組末尾也沒找到就折回數組開頭），直到找到該鍵或遇到一個空位置。由線性探測的過程我們可以知道，若數組已滿的時候我們再向其中插入新鍵，會陷入無限循環之中。
3.2.2 平方探測法
如果散列函數選的不是那么的好，可能導致沖突不斷出現。如果先存入key1，能夠找到某個空余位置存入，存入key2時與key1沖突，此時被存入到key1的下一個位置，后來key3又與它們發生散列沖突……這樣就出現了關鍵字聚集在某一區域的情況，即出現了數據聚集的現象。
一種解決方法是，增大di的增量：（H（key）+di²）％ m（di=0,1,2,3...,m/2）
增加平方運算的目的是為了不讓關鍵字都聚集在某一塊區域。我們稱這種方法為平方探測法。
如果m—表長-1不為素數，那么備選單元的數量將會減少，造成散列沖突的可能性就會大大增加。
3.2.3 雙散列法
準備兩個散列函數。雙散列一般公式為：F(i)= i * hash3(x)，意思是用第二個散列函數算出x的散列值，然后在距離hash3(x)，2hash3(x)的地方探測。
前面的鏈地址法和開放定址法都是為了讓散列表中的元素分布的更加合理，但是散列表空間總有用完的時候，甚至當它們的散列表填充元素過多時，都會增大發生散列沖突的概率。這里的再散列法就是計算出什么時候讓散列表進行擴展以及在散列表擴展的時候，如何讓原來的元素在新的空間中合理的分布。
一般方法是：當散列表的元素足夠的多時，建立另外一個大約兩倍大的表，再用一個新的散列函數，掃描整個原始表然后按照新的映射插入到新的表里，這就是再散列。其開銷非常大，因為涉及到所有元素的移動。
再散列的觸發條件通常有：只要表有一半滿了就做、只有當插入失敗時才做（這種比較極端）、當表到達某個擴容因子時再做。第三種是較好的方法，HashMap就是用的這種方法。
散列表的擴容因子： 所謂的擴容因子α=填入表中的記錄個數/散列表長度，α標志著散列表的裝滿的程度。一般來說，當元素數量達到設定的擴容因子的數量時，就表示可以進行再散列擴容了，也叫裝填因子。因此一個合理的擴容因子非常重要。α越大，產生沖突的可能性就越大；α越小，產生沖突的可能性就越小，但是造成了空間浪費。JDK1.8的HasmMap裝填因子默認為0.75。
JDK已經提供了現成的散列表實現，比如著名的HashMap。JDK1.8的HashMap是采用數組+鏈表+紅黑樹來實現的。散列函數采用基于hashcode()的去除留余法，并且采用分離鏈接法和再散列法的散列沖突解決辦法。
這里提供另一種采用線性探測的散列表的Java簡單實現，從下面的實現上可以看出來，實際上線性探測的散列表效率并不高，并且產生了數據聚集，但是JDK中也有使用線性探測實現的散列表類，比如ThreadLocal中的ThreadLocalMap，因為線性探測的實現比較簡單。
/**
* 基于線性探測法的散列表簡單實現
*
* @param <K> key類型
* @param <V> value類型
*/
public class LinearProbingHashMap<K, V> {
/**
* 存儲節點數據的數組
*/
transient Entry<K, V>[] table;
/**
* 存儲的節點對象
*
* @param <K>
* @param <V>
*/
private static class Entry<K, V> implements Map.Entry<K, V> {
/**
* 保存hash值,避免重復計算
*/
final int hash;
/**
* key值
*/
final K key;
/**
* value值
*/
V value;
/**
* 構造器
*
* @param hash
* @param key
* @param value
*/
private Entry(int hash, K key, V value) {
this.hash = hash;
this.key = key;
this.value = value;
}
@Override
public final K getKey() {
return key;
}
@Override
public final V getValue() {
return value;
}
/*@Override
public final String toString() {
return hash + "=" + key + "=" + value;
}*/
@Override
public final String toString() {
return key + "=" + value;
}
@Override
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
@Override
public int hashCode() {
return hash;
}
}
/**
* 散列表的容量,初始為16
*/
private int capacity = 16;
/**
* 散列表節點數量
*/
private int size;
/**
* 空構造器,并不會初始化內部數組
*/
public LinearProbingHashMap() {
}
/**
* 插入
*
* @param key k
* @param value v
*/
public V put(K key, V value) {
//初始化
if (table == null) {
table = new Entry[capacity];
}
//擴容,這里判斷元素數量大于等于0.75*capacity
if (size >= capacity * 0.75) {
resize(2 * capacity);
}
int hash = hash(key);
//計算應該插入的數組元素下標
int position = hash & (capacity - 1);
//插入邏輯,總會成功
while (true) {
if (table[position] == null) {
table[position] = new Entry<>(hash, key, value);
size++;
break;
//判斷是否是重復的key,這里使用hash值和==判斷
} else if (hash == table[position].hashCode() && table[position].getKey() == key) {
return table[position].setValue(value);
}
position = nextIndex(position, capacity);
}
return null;
}
/**
* 查找
*
* @param key 要查找的key
* @return 查找到的value
*/
public V get(K key) {
if (table == null) {
return null;
}
//計算出key對應的數組位置
int position = hash(key) & (capacity - 1);
//如果該位置不為null,則開始查找連續的元素
if (table[position] != null) {
do {
if (table[position].getKey() == key) {
return table[position].getValue();
}
position = nextIndex(position, capacity);
} while (table[position] != null);
}
return null;
}
/**
* 刪除元素
*
* @param key 查找的元素
* @return 被刪除的元素value;null不代表不是被刪除的value
*/
public V delete(K key) {
if (table == null) {
return null;
}
//計算出key對應的數組位置
int position = hash(key) & (capacity - 1);
V value;
//如果該位置不為null,則開始查找連續的元素
if (table[position] != null) {
do {
if (table[position].getKey() == key) {
//刪除元素
value = table[position].getValue();
table[position] = null;
size--;
//將后面的連續的元素全部重新插入
position = nextIndex(position, capacity);
Entry<K, V> positionEntry;
while ((positionEntry = table[position]) != null) {
table[position] = null;
size--;
put(positionEntry.getKey(), positionEntry.getValue());
position = nextIndex(position, capacity);
}
return value;
}
position = nextIndex(position, capacity);
} while (table[position] != null);
}
return null;
}
public int size() {
return size;
}
/**
* 獲取hash值,不是直接取hash值,而是借鑒了HashMap的擾動算法,這樣可以讓元素分布更加均勻
*
* @param key k
* @return hash值
*/
private int hash(K key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* 擴容
*
* @param newCapacity 新容量
*/
private void resize(int newCapacity) {
if (newCapacity <= 0) {
throw new StackOverflowError("容量超出最大容量");
}
this.capacity = newCapacity;
Entry<K, V>[] oldTab = table;
table = new Entry[capacity];
for (Entry<K, V> e : oldTab) {
if (e != null) {
int position = e.hashCode() & (capacity - 1);
while (table[position] != null) {
position = nextIndex(position, capacity);
}
table[position] = e;
}
}
}
/**
* 下一個位置
*
* @param i 當前位置
* @param len 數組長度
* @return 下一個位置, 此處包含循環的邏輯循環
*/
private static int nextIndex(int i, int len) {
return ((i + 1 < len) ? i + 1 : 0);
}
@Override
public String toString() {
return "LinearProbingHashST{" +
"table=" + Arrays.toString(table) +
'}';
}
}public class LinearProbingHashMapTest {
public static void main(String[] args) {
System.out.println("==========>插入一批元素");
LinearProbingHashMap<Object, Object> objectObjectLinearProbingHashMap = new LinearProbingHashMap<>();
objectObjectLinearProbingHashMap.put(49, 16);
objectObjectLinearProbingHashMap.put("Aa", 1);
objectObjectLinearProbingHashMap.put(34, 78);
objectObjectLinearProbingHashMap.put(17, 85);
//Aa與BB的hash值是一樣的
objectObjectLinearProbingHashMap.put("BB", 2);
objectObjectLinearProbingHashMap.put(36, 36);
objectObjectLinearProbingHashMap.put(21, 37);
objectObjectLinearProbingHashMap.put(9, 87);
objectObjectLinearProbingHashMap.put("兓", 62);
objectObjectLinearProbingHashMap.put(46, 43);
objectObjectLinearProbingHashMap.put("呵呵", 3);
objectObjectLinearProbingHashMap.put("嘻嘻", 4);
System.out.println(objectObjectLinearProbingHashMap);
System.out.println("size:" + objectObjectLinearProbingHashMap.size());
System.out.println(objectObjectLinearProbingHashMap);
System.out.println("==========>刪除 BB");
Object delete = objectObjectLinearProbingHashMap.delete("BB");
System.out.println(delete);
System.out.println("size:" + objectObjectLinearProbingHashMap.size());
System.out.println(objectObjectLinearProbingHashMap);
System.out.println("==========>插入(46,44) 重復添加46,將會替換value");
Object put = objectObjectLinearProbingHashMap.put(46, 44);
System.out.println(put);
System.out.println("size:" + objectObjectLinearProbingHashMap.size());
System.out.println(objectObjectLinearProbingHashMap);
System.out.println("==========>插入null 將會嘗試添加到第一個元素");
Object putNull = objectObjectLinearProbingHashMap.put(null, "nullnull");
System.out.println(putNull);
System.out.println("size:" + objectObjectLinearProbingHashMap.size());
System.out.println(objectObjectLinearProbingHashMap);
System.out.println("==========>獲取null 對應的value");
Object o = objectObjectLinearProbingHashMap.get(null);
System.out.println(o);
System.out.println("==========>擴容");
objectObjectLinearProbingHashMap.put("BB", 5);
System.out.println("size:" + objectObjectLinearProbingHashMap.size());
System.out.println(objectObjectLinearProbingHashMap);
System.out.println("==========>獲取BB 對應的value");
Object bb = objectObjectLinearProbingHashMap.get("BB");
System.out.println(bb);
System.out.println("==========>刪除 34");
Object delete34 = objectObjectLinearProbingHashMap.delete(34);
System.out.println(delete34);
System.out.println("size:" + objectObjectLinearProbingHashMap.size());
System.out.println(objectObjectLinearProbingHashMap);
}
}到此，相信大家對“Java散列表怎么實現”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
