哈希表是什么？哈希表數(shù)據(jù)結(jié)構(gòu)詳細資料分析

我所寫的這些數(shù)據(jù)結(jié)構(gòu)，都是比較經(jīng)典的，也是面試中經(jīng)常會出現(xiàn)的，這篇文章我就不閑扯了，全是干貨，如果你能讀完，希望對你有所幫助~

哈希表也稱為散列表，是根據(jù)關(guān)鍵字值（key value）而直接進行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把關(guān)鍵字值映射到一個位置來訪問記錄，以加快查找的速度。這個映射函數(shù)稱為哈希函數(shù)（也稱為散列函數(shù)），映射過程稱為哈?；?，存放記錄的數(shù)組叫做散列表。比如我們可以用下面的方法將關(guān)鍵字映射成數(shù)組的下標：

arrayIndex=hugeNumber%arraySize

那么問題來了，這種方式對不同的關(guān)鍵字，可能得到同一個散列地址，即同一個數(shù)組下標，這種現(xiàn)象稱為沖突，那么我們該如何去處理沖突呢？一種方法是開放地址法，即通過系統(tǒng)的方法找到數(shù)組的另一個空位，把數(shù)據(jù)填入，而不再用哈希函數(shù)得到的數(shù)組下標，因為該位置已經(jīng)有數(shù)據(jù)了；另一種方法是創(chuàng)建一個存放鏈表的數(shù)組，數(shù)組內(nèi)不直接存儲數(shù)據(jù)，這樣當發(fā)生沖突時，新的數(shù)據(jù)項直接接到這個數(shù)組下標所指的鏈表中，這種方法叫做鏈地址法。下面針對這兩種方法進行討論。

1.開放地址法

1.1 線性探測法

所謂線性探測，即線性地查找空白單元。我舉個例子，如果21是要插入數(shù)據(jù)的位置，但是它已經(jīng)被占用了，那么就是用22，然后23，以此類推。數(shù)組下標一直遞增，直到找到空白位。下面是基于線性探測法的哈希表實現(xiàn)代碼：

publicclassHashTable {

privateDataItem[] hashArray; //DateItem類是數(shù)據(jù)項，封裝數(shù)據(jù)信息

privateint arraySize;

privateint itemNum; //數(shù)組中目前存儲了多少項

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++;

}

/*

* 數(shù)組有固定的大小，而且不能擴展，所以擴展哈希表只能另外創(chuàng)建一個更大的數(shù)組，然后把舊數(shù)組中的數(shù)據(jù)插到新的數(shù)組中。但是哈希表是根據(jù)數(shù)組大小計算給定數(shù)據(jù)的位置的，所以這些數(shù)據(jù)項不能再放在新數(shù)組中和老數(shù)組相同的位置上，因此不能直接拷貝，需要按順序遍歷老數(shù)組，并使用insert方法向新數(shù)組中插入每個數(shù)據(jù)項。這叫重新哈?；?。這是一個耗時的過程，但如果數(shù)組要進行擴展，這個過程是必須的。

*/

publicvoid extendHashTable() { //擴展哈希表

int num = arraySize;

itemNum = 0; //重新記數(shù)，因為下面要把原來的數(shù)據(jù)轉(zhuǎn)移到新的擴張的數(shù)組中

arraySize *= 2; //數(shù)組大小翻倍

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;

}

}

線性探測有個弊端，即數(shù)據(jù)可能會發(fā)生聚集。一旦聚集形成，它會變得越來越大，那些哈希化后落在聚集范圍內(nèi)的數(shù)據(jù)項，都要一步步的移動，并且插在聚集的最后，因此使聚集變得更大。聚集越大，它增長的也越快。這就導致了哈希表的某個部分包含大量的聚集，而另一部分很稀疏。

為了解決這個問題，我們可以使用二次探測：二次探測是防止聚集產(chǎn)生的一種方式，思想是探測相隔較遠的單元，而不是和原始位置相鄰的單元。線性探測中，如果哈希函數(shù)計算的原始下標是x, 線性探測就是x+1, x+2, x+3, 以此類推；而在二次探測中，探測的過程是x+1, x+4, x+9, x+16，以此類推，到原始位置的距離是步數(shù)的平方。二次探測雖然消除了原始的聚集問題，但是產(chǎn)生了另一種更細的聚集問題，叫二次聚集：比如講184，302，420和544依次插入表中，它們的映射都是7，那么302需要以1為步長探測，420需要以4為步長探測， 544需要以9為步長探測。只要有一項其關(guān)鍵字映射到7，就需要更長步長的探測，這個現(xiàn)象叫做二次聚集。

二次聚集不是一個嚴重的問題，但是二次探測不會經(jīng)常使用，因為還有好的解決方法，比如再哈希法。

1.2 再哈希法

為了消除原始聚集和二次聚集，現(xiàn)在需要的一種方法是產(chǎn)生一種依賴關(guān)鍵字的探測序列，而不是每個關(guān)鍵字都一樣。即：不同的關(guān)鍵字即使映射到相同的數(shù)組下標，也可以使用不同的探測序列。再哈希法就是把關(guān)鍵字用不同的哈希函數(shù)再做一遍哈希化，用這個結(jié)果作為步長，對于指定的關(guān)鍵字，步長在整個探測中是不變的，不同關(guān)鍵字使用不同的步長、經(jīng)驗說明，第二個哈希函數(shù)必須具備如下特點：

和第一個哈希函數(shù)不同；

不能輸出0（否則沒有步長，每次探索都是原地踏步，算法將進入死循環(huán)）。

專家們已經(jīng)發(fā)現(xiàn)下面形式的哈希函數(shù)工作的非常好：

stepSize=constant-key%constant

其中 constant 是質(zhì)數(shù)，且小于數(shù)組容量。

再哈希法要求表的容量是一個質(zhì)數(shù)，假如表長度為15(0-14)，非質(zhì)數(shù)，有一個特定關(guān)鍵字映射到0，步長為5，則探測序列是 0,5,10,0,5,10,以此類推一直循環(huán)下去。算法只嘗試這三個單元，所以不可能找到某些空白單元，最終算法導致崩潰。如果數(shù)組容量為13, 質(zhì)數(shù)，探測序列最終會訪問所有單元。即 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計算探測步數(shù)

while(hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1) {

hashVal += stepSize;

hashVal %= arraySize; //以指定的步數(shù)向后探測

}

hashArray[hashVal] = item;

itemNum++;

}

publicvoid extendHashTable() {

int num = arraySize;

itemNum = 0; //重新記數(shù)，因為下面要把原來的數(shù)據(jù)轉(zhuǎn)移到新的擴張的數(shù)組中

arraySize *= 2; //數(shù)組大小翻倍

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. 鏈地址法

在開放地址法中，通過再哈希法尋找一個空位解決沖突問題，另一個方法是在哈希表每個單元中設(shè)置鏈表（即鏈地址法），某個數(shù)據(jù)項的關(guān)鍵字值還是像通常一樣映射到哈希表的單元，而數(shù)據(jù)項本身插入到這個單元的鏈表中。其他同樣映射到這個位置的數(shù)據(jù)項只需要加到鏈表中，不需要在原始的數(shù)組中尋找空位。下面看看鏈地址法的代碼：

publicclassHashChain {

privateSortedList[] hashArray; //數(shù)組中存放鏈表

privateint arraySize;

publicHashChain(int size) {

arraySize = size;

hashArray = newSortedList[arraySize];

//new出每個空鏈表初始化數(shù)組

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);//從鏈表中找到要刪除的數(shù)據(jù)項，直接刪除

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 + " ");

}

}

在沒有沖突的情況下，哈希表中執(zhí)行插入和刪除操作可以達到O(1)的時間級，這是相當快的，如果發(fā)生沖突了，存取時間就依賴后來的長度，查找或刪除時也得挨個判斷，但是最差也就O(N)級別。