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

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

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

arrayIndex=hugeNumber%arraySize

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

1.開放地址法

1.1 線性探測法

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

publicclassHashTable {

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

privateint arraySize;

privateint itemNum; //數(shù)組中目前存儲(chǔ)了多少項(xiàng)

privateDataItem nonItem; //用于刪除項(xiàng)的

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()) {

//擴(kuò)展哈希表

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

*/

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

int num = arraySize;

itemNum = 0; //重新記數(shù)，因?yàn)橄旅嬉言瓉淼臄?shù)據(jù)轉(zhuǎn)移到新的擴(kuò)張的數(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;

}

}

線性探測有個(gè)弊端，即數(shù)據(jù)可能會(huì)發(fā)生聚集。一旦聚集形成，它會(huì)變得越來越大，那些哈?；舐湓诰奂秶鷥?nèi)的數(shù)據(jù)項(xiàng)，都要一步步的移動(dòng)，并且插在聚集的最后，因此使聚集變得更大。聚集越大，它增長的也越快。這就導(dǎo)致了哈希表的某個(gè)部分包含大量的聚集，而另一部分很稀疏。

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

二次聚集不是一個(gè)嚴(yán)重的問題，但是二次探測不會(huì)經(jīng)常使用，因?yàn)檫€有好的解決方法，比如再哈希法。

1.2 再哈希法

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

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

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

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

stepSize=constant-key%constant

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

再哈希法要求表的容量是一個(gè)質(zhì)數(shù)，假如表長度為15(0-14)，非質(zhì)數(shù)，有一個(gè)特定關(guān)鍵字映射到0，步長為5，則探測序列是 0,5,10,0,5,10,以此類推一直循環(huán)下去。算法只嘗試這三個(gè)單元，所以不可能找到某些空白單元，最終算法導(dǎo)致崩潰。如果數(shù)組容量為13, 質(zhì)數(shù)，探測序列最終會(huì)訪問所有單元。即 0,5,10,2,7,12,4,9,1,6,11,3,一直下去，只要表中有一個(gè)空位，就可以探測到它。下面看看再哈希法的代碼：

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計(jì)算探測步數(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ù)，因?yàn)橄旅嬉言瓉淼臄?shù)據(jù)轉(zhuǎn)移到新的擴(kuò)張的數(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. 鏈地址法

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

publicclassHashChain {

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

privateint arraySize;

publicHashChain(int size) {

arraySize = size;

hashArray = newSortedList[arraySize];

//new出每個(gè)空鏈表初始化數(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);//從鏈表中找到要?jiǎng)h除的數(shù)據(jù)項(xiàng)，直接刪除

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í)行插入和刪除操作可以達(dá)到O(1)的時(shí)間級(jí)，這是相當(dāng)快的，如果發(fā)生沖突了，存取時(shí)間就依賴后來的長度，查找或刪除時(shí)也得挨個(gè)判斷，但是最差也就O(N)級(jí)別。