帶你瞭解Java數據結構和算法之哈希表
1、哈希函數的引入
大傢都用過字典，字典的優點是我們可以通過前面的目錄快速定位到所要查找的單詞。如果我們想把一本英文字典的每個單詞，從 a 到 zyzzyva(這是牛津字典的最後一個單詞)，都寫入計算機內存，以便快速讀寫，那麼哈希表是個不錯的選擇。
這裡我們將范圍縮小點，比如想在內存中存儲5000個英文單詞。我們可能想到每個單詞會占用一個數組單元，那麼數組的大小是5000，同時可以用數組下標存取單詞，這樣設想很完美，但是數組下標和單詞怎麼建立聯系呢？
首先我們要建立單詞和數字（數組下標）的關系：
我們知道 ASCII 是一種編碼，其中 a 表示97，b表示98，以此類推，一直到122表示z，而每個單詞都是由這26個字母組成，我們可以不用 ASCII 編碼那麼大的數字，自己設計一套類似 ASCII的編碼，比如a表示1，b表示2，依次類推，z表示26，那麼表示方法我們就知道瞭。
接下來如何把單個字母的數字組合成代表整個單詞的數字呢？
①、把數字相加
首先第一種簡單的方法就是把單詞的每個字母表示的數字相加，得到的和便是數組的下標。
比如單詞 cats 轉換成數字：
cats = 3 + 1 + 20 + 19 = 43
那麼單詞 cats 存儲在數組中的下標為43，所有的英文單詞都可以用這個辦法轉換成數組下標。但是這個辦法真的可行嗎？
假設我們約定一個單詞最多有 10 個字母，那麼字典的最後一個單詞為 zzzzzzzzzz ，其轉換為數字：
zzzzzzzzzz = 26*10 = 260
那麼我們可以得到單詞編碼的范圍是從1-260。很顯然，這個范圍是不夠存儲5000個單詞的，那麼肯定有一個位置存儲瞭多個單詞，每個數組的數據項平均要存儲192個單詞（5000除以260）。
對於上面的問題，我們如何解決呢？
第一種方法：考慮每個數組項包含一個子數組或者一個子鏈表，這個辦法存數據項確實很快，但是如果我們想要從192個單詞中查找到其中一個，那麼還是很慢。
第二種方法：為啥要讓那麼多單詞占據同一個數據項呢？也就是說我們沒有把單詞分的足夠開，數組能表示的元素太少，我們需要擴展數組的下標，使其每個位置都隻存放一個單詞。
對於上面的第二種方法，問題產生瞭，我們如何擴展數組的下標呢？
②、冪的連乘
我們將單詞表示的數拆成數列，用適當的 27 的冪乘以這些位數（因為有26個可能的字符，以及空格，一共27個），然後把乘積相加，這樣就得出瞭每個單詞獨一無二的數字。
比如把單詞cats 轉換為數字：
cats = 3*273 + 1*272 + 20*271 + 19*270 = 59049 + 729 + 540 + 19 = 60337
這個過程會為每個單詞創建一個獨一無二的數，但是註意的是我們這裡隻是計算瞭 4 個字母組成的單詞，如果單詞很長，比如最長的10個字母的單詞 zzzzzzzzzz，僅僅是279 結果就超出瞭7000000000000，這個結果是很巨大的，在實際內存中，根本不可能為一個數組分配這麼大的空間。
所以這個方案的問題就是雖然為每個單詞都分配瞭獨一無二的下標，但是隻有一小部分存放瞭單詞，很大一部分都是空著的。那麼現在就需要一種方法，把數位冪的連乘系統中得到的巨大的整數范圍壓縮到可接受的數組范圍中。
對於英語字典，假設隻有5000個單詞，這裡我們選定容量為10000 的數組空間來存放（後面會介紹為啥需要多出一倍的空間）。那麼我們就需要將從 0 到超過 7000000000000 的范圍，壓縮到從0到10000的范圍。
第一種方法：取餘，得到一個數被另一個整數除後的餘數。首先我們假設要把從0-199的數字（用largeNumber表示），壓縮為從0-9的數字（用smallNumber表示），後者有10個數，所以變量smallRange 的值為10，這個轉換的表達式為：
smallNumber = largeNumber % smallRange
當一個數被 10 整除時，餘數一定在0-9之間，這樣，我們就把從0-199的數壓縮為從0-9的數，壓縮率為 20 :1。
我們也可以用類似的方法把表示單詞唯一的數壓縮成數組的下標：
arrayIndex = largerNumber % smallRange
這也就是哈希函數。它把一個大范圍的數字哈希（轉化）成一個小范圍的數字，這個小范圍的數對應著數組的下標。使用哈希函數向數組插入數據後，這個數組就是哈希表。
2、沖突
把巨大的數字范圍壓縮到較小的數字范圍，那麼肯定會有幾個不同的單詞哈希化到同一個數組下標，即產生瞭沖突。
沖突可能會導致哈希化方案無法實施，前面我們說指定的數組范圍大小是實際存儲數據的兩倍，因此可能有一半的空間是空著的，所以，當沖突產生時，一個方法是通過系統的方法找到數組的一個空位，並把這個單詞填入，而不再用哈希函數得到數組的下標，這種方法稱為開放地址法。比如加入單詞 cats 哈希化的結果為5421，但是它的位置已經被單詞parsnip占用瞭，那麼我們會考慮將單詞 cats 存放在parsnip後面的一個位置 5422 上。
另一種方法，前面我們也提到過，就是數組的每個數據項都創建一個子鏈表或子數組，那麼數組內不直接存放單詞，當產生沖突時，新的數據項直接存放到這個數組下標表示的鏈表中，這種方法稱為鏈地址法。
3、開放地址法
開發地址法中，若數據項不能直接存放在由哈希函數所計算出來的數組下標時，就要尋找其他的位置。分別有三種方法：線性探測、二次探測以及再哈希法。
①、線性探測
在線性探測中，它會線性的查找空白單元。比如如果 5421 是要插入數據的位置，但是它已經被占用瞭，那麼就使用5422，如果5422也被占用瞭，那麼使用5423，以此類推，數組下標依次遞增，直到找到空白的位置。這就叫做線性探測，因為它沿著數組下標一步一步順序的查找空白單元。
完整代碼：
需要註意的是，當哈希表變得太滿時，我們需要擴展數組，但是需要註意的是，數據項不能放到新數組中和老數組相同的位置，而是要根據數組大小重新計算插入位置。這是一個比較耗時的過程，所以一般我們要確定數據的范圍，給定好數組的大小，而不再擴容。
另外，當哈希表變得比較滿時，我們每插入一個新的數據，都要頻繁的探測插入位置，因為可能很多位置都被前面插入的數據所占用瞭，這稱為聚集。數組填的越滿，聚集越可能發生。
這就像人群，當某個人在商場暈倒時，人群就會慢慢聚集。最初的人群聚過來是因為看到瞭那個倒下的人，而後面聚過來的人是因為它們想知道這些人聚在一起看什麼。人群聚集的越大，吸引的人就會越多。
②、裝填因子
已填入哈希表的數據項和表長的比率叫做裝填因子，比如有10000個單元的哈希表填入瞭6667 個數據後，其裝填因子為 2/3。當裝填因子不太大時，聚集分佈的比較連貫，而裝填因子比較大時，則聚集發生的很大瞭。
我們知道線性探測是一步一步的往後面探測，當裝填因子比較大時，會頻繁的產生聚集，那麼如果我們探測比較大的單元，而不是一步一步的探測呢，這就是下面要講的二次探測。
③、二次探測
二測探測是防止聚集產生的一種方式，思想是探測相距較遠的單元，而不是和原始位置相鄰的單元。
線性探測中，如果哈希函數計算的原始下標是x, 線性探測就是x+1, x+2, x+3, 以此類推；而在二次探測中，探測的過程是x+1, x+4, x+9, x+16，以此類推，到原始位置的距離是步數的平方。二次探測雖然消除瞭原始的聚集問題，但是產生瞭另一種更細的聚集問題，叫二次聚集：比如講184，302，420和544依次插入表中，它們的映射都是7，那麼302需要以1為步長探測，420需要以4為步長探測， 544需要以9為步長探測。隻要有一項其關鍵字映射到7，就需要更長步長的探測，這個現象叫做二次聚集。二次聚集不是一個嚴重的問題，但是二次探測不會經常使用，因為還有好的解決方法，比如再哈希法。
④、再哈希法
為瞭消除原始聚集和二次聚集，我們使用另外一種方法：再哈希法。
我們知道二次聚集的原因是，二測探測的算法產生的探測序列步長總是固定的：1,4，9,16以此類推。那麼我們想到的是需要產生一種依賴關鍵字的探測序列，而不是每個關鍵字都一樣，那麼，不同的關鍵字即使映射到相同的數組下標，也可以使用不同的探測序列。
方法是把關鍵字用不同的哈希函數再做一遍哈希化，用這個結果作為步長。對於指定的關鍵字，步長在整個探測中是不變的，不過不同的關鍵字使用不同的步長。
第二個哈希函數必須具備如下特點：
一、和第一個哈希函數不同
二、不能輸出0（否則，將沒有步長，每次探測都是原地踏步，算法將陷入死循環）。
專傢們已經發現下面形式的哈希函數工作的非常好：stepSize = constant – key % constant; 其中constant是質數，且小於數組容量。
再哈希法要求表的容量是一個質數，假如表長度為15(0-14)，非質數，有一個特定關鍵字映射到0，步長為5，則探測序列是0,5,10,0,5,10,以此類推一直循環下去。算法隻嘗試這三個單元，所以不可能找到某些空白單元，最終算法導致崩潰。如果數組容量為13, 質數，探測序列最終會訪問所有單元。即0,5,10,2,7,12,4,9,1,6,11,3,一直下去，隻要表中有一個空位，就可以探測到它。
完整再哈希法代碼：
package com.ys.hash;
public class HashDouble {
private DataItem[] hashArray; //DataItem類，表示每個數據項信息
private int arraySize;//數組的初始大小
private int itemNum;//數組實際存儲瞭多少項數據
private DataItem nonItem;//用於刪除數據項
public HashDouble(){
this.arraySize = 13;
hashArray = new DataItem[arraySize];
nonItem = new DataItem(-1);//刪除的數據項下標為-1
}
//判斷數組是否存儲滿瞭
public boolean isFull(){
return (itemNum == arraySize);
}
//判斷數組是否為空
public boolean isEmpty(){
return (itemNum == 0);
}
//打印數組內容
public void display(){
System.out.println("Table:");
for(int j = 0 ; j < arraySize ; j++){
if(hashArray[j] != null){
System.out.print(hashArray[j].getKey() + " ");
}else{
System.out.print("** ");
}
}
}
//通過哈希函數轉換得到數組下標
public int hashFunction1(int key){
return key%arraySize;
}
public int hashFunction2(int key){
return 5 - key%5;
}
//插入數據項
public void insert(DataItem item){
if(isFull()){
//擴展哈希表
System.out.println("哈希表已滿，重新哈希化...");
extendHashTable();
}
int key = item.getKey();
int hashVal = hashFunction1(key);
int stepSize = hashFunction2(key);//用第二個哈希函數計算探測步數
while(hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1){
hashVal += stepSize;
hashVal %= arraySize;//以指定的步數向後探測
}
hashArray[hashVal] = item;
itemNum++;
}
/**
* 數組有固定的大小，而且不能擴展，所以擴展哈希表隻能另外創建一個更大的數組，然後把舊數組中的數據插到新的數組中。
* 但是哈希表是根據數組大小計算給定數據的位置的，所以這些數據項不能再放在新數組中和老數組相同的位置上。
* 因此不能直接拷貝，需要按順序遍歷老數組，並使用insert方法向新數組中插入每個數據項。
* 這個過程叫做重新哈希化。這是一個耗時的過程，但如果數組要進行擴展，這個過程是必須的。
*/
public void extendHashTable(){
int num = arraySize;
itemNum = 0;//重新計數，因為下面要把原來的數據轉移到新的擴張的數組中
arraySize *= 2;//數組大小翻倍
DataItem[] oldHashArray = hashArray;
hashArray = new DataItem[arraySize];
for(int i = 0 ; i < num ; i++){
insert(oldHashArray[i]);
}
}
//刪除數據項
public DataItem delete(int key){
if(isEmpty()){
System.out.println("Hash Table is Empty!");
return null;
}
int hashVal = hashFunction1(key);
int stepSize = hashFunction2(key);
while(hashArray[hashVal] != null){
if(hashArray[hashVal].getKey() == key){
DataItem temp = hashArray[hashVal];
hashArray[hashVal] = nonItem;//nonItem表示空Item,其key為-1
itemNum--;
return temp;
}
hashVal += stepSize;
hashVal %= arraySize;
}
return null;
}
//查找數據項
public DataItem find(int key){
int hashVal = hashFunction1(key);
int stepSize = hashFunction2(key);
while(hashArray[hashVal] != null){
if(hashArray[hashVal].getKey() == key){
return hashArray[hashVal];
}
hashVal += stepSize;
hashVal %= arraySize;
}
return null;
}
public static class DataItem{
private int iData;
public DataItem(int iData){
this.iData = iData;
}
public int getKey(){
return iData;
}
}
}
4、鏈地址法
在開放地址法中，通過再哈希法尋找一個空位解決沖突問題，另一個方法是在哈希表每個單元中設置鏈表（即鏈地址法），某個數據項的關鍵字值還是像通常一樣映射到哈希表的單元，而數據項本身插入到這個單元的鏈表中。其他同樣映射到這個位置的數據項隻需要加到鏈表中，不需要在原始的數組中尋找空位。
有序鏈表：
package com.ys.hash;
public class SortLink {
private LinkNode first;
public SortLink(){
first = null;
}
public boolean isEmpty(){
return (first == null);
}
public void insert(LinkNode node){
int key = node.getKey();
LinkNode previous = null;
LinkNode current = first;
while(current != null && current.getKey() < key){
previous = current;
current = current.next;
}
if(previous == null){
first = node;
}else{
previous.next = node;
}
node.next = curent;
}
public void delete(int key){
LinkNode previous = null;
LinkNode current = first;
if(isEmpty()){
System.out.println("Linked is Empty!!!");
return;
}
while(current != null && current.getKey() != key){
previous = current;
current = current.next;
}
if(previous == null){
first = first.next;
}else{
previous.next = current.next;
}
}
public LinkNode find(int key){
LinkNode current = first;
while(current != null && current.getKey() <= key){
if(current.getKey() == key){
return current;
}
current = current.next;
}
return null;
}
public void displayLink(){
System.out.println("Link(First->Last)");
LinkNode current = first;
while(current != null){
current.displayLink();
current = current.next;
}
System.out.println("");
}
class LinkNode{
private int iData;
public LinkNode next;
public LinkNode(int iData){
this.iData = iData;
}
public int getKey(){
return iData;
}
public void displayLink(){
System.out.println(iData + " ");
}
}
}
鏈地址法：
package com.ys.hash;
import com.ys.hash.SortLink.LinkNode;
public class HashChain {
private SortLink[] hashArray;//數組中存放鏈表
private int arraySize;
public HashChain(int size){
arraySize = size;
hashArray = new SortLink[arraySize];
//new 出每個空鏈表初始化數組
for(int i = 0 ; i < arraySize ; i++){
hashArray[i] = new SortLink();
}
}
public void displayTable(){
for(int i = 0 ; i < arraySize ; i++){
System.out.print(i + "：");
hashArray[i].displayLink();
}
}
public int hashFunction(int key){
return key%arraySize;
}
public void insert(LinkNode node){
int key = node.getKey();
int hashVal = hashFunction(key);
hashArray[hashVal].insert(node);//直接往鏈表中添加即可
}
public LinkNode delete(int key){
int hashVal = hashFunction(key);
LinkNode temp = find(key);
hashArray[hashVal].delete(key);//從鏈表中找到要刪除的數據項，直接刪除
return temp;
}
public LinkNode find(int key){
int hashVal = hashFunction(key);
LinkNode node = hashArray[hashVal].find(key);
return node;
}
}
鏈地址法中，裝填因子（數據項數和哈希表容量的比值）與開放地址法不同，在鏈地址法中，需要有N個單元的數組中轉入N個或更多的數據項，因此裝填因子一般為1，或比1大（有可能某些位置包含的鏈表中包含兩個或兩個以上的數據項）。
找到初始單元需要O(1)的時間級別，而搜索鏈表的時間與M成正比，M為鏈表包含的平均項數，即O(M)的時間級別。
5、桶
另外一種方法類似於鏈地址法，它是在每個數據項中使用子數組，而不是鏈表。這樣的數組稱為桶。
這個方法顯然不如鏈表有效，因為桶的容量不好選擇，如果容量太小，可能會溢出，如果太大，又造成性能浪費，而鏈表是動態分配的，不存在此問題。所以一般不使用桶。
6、總結
哈希表基於數組，類似於key-value的存儲形式，關鍵字值通過哈希函數映射為數組的下標，如果一個關鍵字哈希化到已占用的數組單元，這種情況稱為沖突。用來解決沖突的有兩種方法：開放地址法和鏈地址法。在開發地址法中，把沖突的數據項放在數組的其它位置；在鏈地址法中，每個單元都包含一個鏈表，把所有映射到同一數組下標的數據項都插入到這個鏈表中。
本篇文章就到這裡瞭，希望能夠給你帶來幫助，也希望您能夠多多關註WalkonNet的更多內容!