哈希表是什么？哈希表數據結構詳細資料分析
我所寫的這些數據結構，都是比較經典的，也是面試中經常會出現的，這篇文章我就不閑扯了，全是干貨，如果你能讀完，希望對你有所幫助~
哈希表也稱為散列表，是根據關鍵字值（key value）而直接進行訪問的數據結構。也就是說，它通過把關鍵字值映射到一個位置來訪問記錄，以加快查找的速度。這個映射函數稱為哈希函數（也稱為散列函數），映射過程稱為哈希化，存放記錄的數組叫做散列表。比如我們可以用下面的方法將關鍵字映射成數組的下標：
arrayIndex=hugeNumber%arraySize
那么問題來了，這種方式對不同的關鍵字，可能得到同一個散列地址，即同一個數組下標，這種現象稱為沖突，那么我們該如何去處理沖突呢？一種方法是開放地址法，即通過系統的方法找到數組的另一個空位，把數據填入，而不再用哈希函數得到的數組下標，因為該位置已經有數據了；另一種方法是創建一個存放鏈表的數組，數組內不直接存儲數據，這樣當發生沖突時，新的數據項直接接到這個數組下標所指的鏈表中，這種方法叫做鏈地址法。下面針對這兩種方法進行討論。
1.開放地址法
1.1 線性探測法
所謂線性探測，即線性地查找空白單元。我舉個例子，如果21是要插入數據的位置，但是它已經被占用了，那么就是用22，然后23，以此類推。數組下標一直遞增，直到找到空白位。下面是基于線性探測法的哈希表實現代碼：
publicclassHashTable {
privateDataItem[] hashArray; //DateItem類是數據項，封裝數據信息
privateint arraySize;
privateint itemNum; //數組中目前存儲了多少項
privateDataItem nonItem; //用于刪除項的
publicHashTable() {
arraySize = 13;
hashArray = newDataItem[arraySize];
nonItem = newDataItem(-1); //deleted item key is -1
}
publicboolean isFull() {
return (itemNum == arraySize);
}
publicboolean isEmpty() {
return (itemNum == 0);
}
publicvoid displayTable() {
System.out.print("Table:");
for(int j = 0; j < arraySize; j++) {
if(hashArray[j] != null) {
System.out.print(hashArray[j].getKey() + " ");
}
else {
System.out.print("** ");
}
}
System.out.println("");
}
publicint hashFunction(int key) {
return key % arraySize; //hash function
}
publicvoid insert(DataItem item) {
if(isFull()) {
//擴展哈希表
System.out.println("哈希表已滿，重新哈希化..");
extendHashTable();
}
int key = item.getKey();
int hashVal = hashFunction(key);
while(hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1) {
++hashVal;
hashVal %= arraySize;
}
hashArray[hashVal] = item;
itemNum++;
}
/*
* 數組有固定的大小，而且不能擴展，所以擴展哈希表只能另外創建一個更大的數組，然后把舊數組中的數據插到新的數組中。但是哈希表是根據數組大小計算給定數據的位置的，所以這些數據項不能再放在新數組中和老數組相同的位置上，因此不能直接拷貝，需要按順序遍歷老數組，并使用insert方法向新數組中插入每個數據項。這叫重新哈希化。這是一個耗時的過程，但如果數組要進行擴展，這個過程是必須的。
*/
publicvoid extendHashTable() { //擴展哈希表
int num = arraySize;
itemNum = 0; //重新記數，因為下面要把原來的數據轉移到新的擴張的數組中
arraySize *= 2; //數組大小翻倍
DataItem[] oldHashArray = hashArray;
hashArray = newDataItem[arraySize];
for(int i = 0; i < num; i++) {
insert(oldHashArray[i]);
}
}
publicDataItemdelete(int key) {
if(isEmpty()) {
System.out.println("Hash table is empty!");
returnnull;
}
int hashVal = hashFunction(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;
hashVal %= arraySize;
}
returnnull;
}
publicDataItem find(int key) {
int hashVal = hashFunction(key);
while(hashArray[hashVal] != null) {
if(hashArray[hashVal].getKey() == key) {
return hashArray[hashVal];
}
++hashVal;
hashVal %= arraySize;
}
returnnull;
}
}
classDataItem {
privateint iData;
publicDataItem (int data) {
iData = data;
}
publicint getKey() {
return iData;
}
}
線性探測有個弊端，即數據可能會發生聚集。一旦聚集形成，它會變得越來越大，那些哈希化后落在聚集范圍內的數據項，都要一步步的移動，并且插在聚集的最后，因此使聚集變得更大。聚集越大，它增長的也越快。這就導致了哈希表的某個部分包含大量的聚集，而另一部分很稀疏。
為了解決這個問題，我們可以使用二次探測：二次探測是防止聚集產生的一種方式，思想是探測相隔較遠的單元，而不是和原始位置相鄰的單元。線性探測中，如果哈希函數計算的原始下標是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.2 再哈希法
為了消除原始聚集和二次聚集，現在需要的一種方法是產生一種依賴關鍵字的探測序列，而不是每個關鍵字都一樣。即：不同的關鍵字即使映射到相同的數組下標，也可以使用不同的探測序列。再哈希法就是把關鍵字用不同的哈希函數再做一遍哈希化，用這個結果作為步長，對于指定的關鍵字，步長在整個探測中是不變的，不同關鍵字使用不同的步長、經驗說明，第二個哈希函數必須具備如下特點：
和第一個哈希函數不同；
不能輸出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,一直下去，只要表中有一個空位，就可以探測到它。下面看看再哈希法的代碼：
publicclassHashDouble {
privateDataItem[] hashArray;
privateint arraySize;
privateint itemNum;
privateDataItem nonItem;
publicHashDouble() {
arraySize = 13;
hashArray = newDataItem[arraySize];
nonItem = newDataItem(-1);
}
publicvoid displayTable() {
System.out.print("Table:");
for(int i = 0; i < arraySize; i++) {
if(hashArray[i] != null) {
System.out.print(hashArray[i].getKey() + " ");
}
else {
System.out.print("** ");
}
}
System.out.println("");
}
publicint hashFunction1(int key) { //first hash function
return key % arraySize;
}
publicint hashFunction2(int key) { //second hash function
return5 - key % 5;
}
publicboolean isFull() {
return (itemNum == arraySize);
}
publicboolean isEmpty() {
return (itemNum == 0);
}
publicvoid insert(DataItem item) {
if(isFull()) {
System.out.println("哈希表已滿，重新哈希化..");
extendHashTable();
}
int key = item.getKey();
int hashVal = hashFunction1(key);
int stepSize = hashFunction2(key); //用hashFunction2計算探測步數
while(hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1) {
hashVal += stepSize;
hashVal %= arraySize; //以指定的步數向后探測
}
hashArray[hashVal] = item;
itemNum++;
}
publicvoid extendHashTable() {
int num = arraySize;
itemNum = 0; //重新記數，因為下面要把原來的數據轉移到新的擴張的數組中
arraySize *= 2; //數組大小翻倍
DataItem[] oldHashArray = hashArray;
hashArray = newDataItem[arraySize];
for(int i = 0; i < num; i++) {
insert(oldHashArray[i]);
}
}
publicDataItemdelete(int key) {
if(isEmpty()) {
System.out.println("Hash table is empty!");
returnnull;
}
int hashVal = hashFunction1(key);
int stepSize = hashFunction2(key);
while(hashArray[hashVal] != null) {
if(hashArray[hashVal].getKey() == key) {
DataItem temp = hashArray[hashVal];
hashArray[hashVal] = nonItem;
itemNum--;
return temp;
}
hashVal += stepSize;
hashVal %= arraySize;
}
returnnull;
}
publicDataItem 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;
}
returnnull;
}
}
2. 鏈地址法
在開放地址法中，通過再哈希法尋找一個空位解決沖突問題，另一個方法是在哈希表每個單元中設置鏈表（即鏈地址法），某個數據項的關鍵字值還是像通常一樣映射到哈希表的單元，而數據項本身插入到這個單元的鏈表中。其他同樣映射到這個位置的數據項只需要加到鏈表中，不需要在原始的數組中尋找空位。下面看看鏈地址法的代碼：
publicclassHashChain {
privateSortedList[] hashArray; //數組中存放鏈表
privateint arraySize;
publicHashChain(int size) {
arraySize = size;
hashArray = newSortedList[arraySize];
//new出每個空鏈表初始化數組
for(int i = 0; i < arraySize; i++) {
hashArray[i] = newSortedList();
}
}
publicvoid displayTable() {
for(int i = 0; i < arraySize; i++) {
System.out.print(i + ": ");
hashArray[i].displayList();
}
}
publicint hashFunction(int key) {
return key % arraySize;
}
publicvoid insert(LinkNode node) {
int key = node.getKey();
int hashVal = hashFunction(key);
hashArray[hashVal].insert(node); //直接往鏈表中添加即可
}
publicLinkNodedelete(int key) {
int hashVal = hashFunction(key);
LinkNode temp = find(key);
hashArray[hashVal].delete(key);//從鏈表中找到要刪除的數據項，直接刪除
return temp;
}
publicLinkNode find(int key) {
int hashVal = hashFunction(key);
LinkNode node = hashArray[hashVal].find(key);
return node;
}
}
下面是鏈表類的代碼，用的是有序鏈表：
publicclassSortedList {
privateLinkNode first;
publicSortedList() {
first = null;
}
publicboolean isEmpty() {
return (first == null);
}
publicvoid 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 {
node.next = current;
previous.next = node;
}
}
publicvoiddelete(int key) {
LinkNode previous = null;
LinkNode current = first;
if(isEmpty()) {
System.out.println("chain 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;
}
}
publicLinkNode find(int key) {
LinkNode current = first;
while(current != null && current.getKey() <= key) {
if(current.getKey() == key) {
return current;
}
current = current.next;
}
returnnull;
}
publicvoid displayList() {
System.out.print("List(First->Last):");
LinkNode current = first;
while(current != null) {
current.displayLink();
current = current.next;
}
System.out.println("");
}
}
classLinkNode {
privateint iData;
publicLinkNode next;
publicLinkNode(int data) {
iData = data;
}
publicint getKey() {
return iData;
}
publicvoid displayLink() {
System.out.print(iData + " ");
}
}
在沒有沖突的情況下，哈希表中執行插入和刪除操作可以達到O(1)的時間級，這是相當快的，如果發生沖突了，存取時間就依賴后來的長度，查找或刪除時也得挨個判斷，但是最差也就O(N)級別。
-
函數
+關注
關注
3文章
4338瀏覽量
62734 -
數據結構
+關注
關注
3文章
573瀏覽量
40152 -
哈希表
+關注
關注
0文章
9瀏覽量
4858
原文標題：讀完這篇，希望你能真正理解什么是哈希表
文章出處：【微信號：TheAlgorithm，微信公眾號：算法與數據結構】歡迎添加關注！文章轉載請注明出處。
發布評論請先 登錄
相關推薦
序列化哈希表到文件
基于分段哈希碼的倒排索引樹結構
為什么要學習數據結構？數據結構的應用詳細資料概述免費下載
哈希表是什么？為什么需要使用哈希表
基于C++哈希表解決沖突
基于Xilinx Virtex-II FPGA的硬件哈希算法的研究分析
一種基于智能放置策略的CucKoo哈希表
哈希表是什么，它是如何根據鍵來得到值的
Linux內核分析 端口哈希桶
工商網監
評論