散列 - 數據結構（分離鏈接法、開放定址法） · 數據結構與算法分析-C語言描述

? ? ? 散列是一種用于以常數平均時間執行插入、刪除和查找的技術。理想的散列數據結構只不過是一個包含有關鍵字的具有固定大小的數組。典型情況下，一個關鍵字就是一個帶有相關值（工資信息等）的字符串。 ? ? ??散列函數主要的問題就是解決沖突的消除問題。如果當一個元素被插入時另一個元素已經存在（散列值存在），那么就會產生沖突。解決這種沖突的方法有幾種，一般用最簡單的兩種：分離鏈接法、開放地址法 ? ? ? 1.分離鏈接法 ![](https://box.kancloud.cn/2016-08-17_57b4292056093.jpg) //分離鏈接散列表的頭文件聲明 ~~~ #ifndef HASH_H_INCLUDED #define HASH_H_INCLUDED #include <stdio.h> #include <stdlib.h> typedef unsigned int Index; typedef int DataType; struct ListNode; typedef struct ListNode *Position; typedef Position List; struct HashTbl; typedef struct HashTbl *HashTable; HashTable Hash_InitTable(int TableSize); void Hash_Insert(DataType key, HashTable H); void Hash_Delete(DataType key, HashTable H); void Hash_Show(HashTable H); int Hash_Free(HashTable H); #endif // HASH_H_INCLUDED ~~~ //分離鏈接散列表的功能函數聲明 ~~~ #include "hash.h" struct ListNode { DataType Data; Position Next; }; struct HashTbl { int TableSize; List *TheLists; }; void Print_Err(char *str); int NextPrime(int n); Index Hash(const int key, int tablesize) { unsigned int hashval = 0; int x; x = key; if(x < 0) { printf("the key is low 0\n"); exit(-1); } while(x != 0) { hashval = (hashval << 3) + x%10; x /= 10; } return hashval % tablesize; } HashTable Hash_InitTable(int Size) { HashTable H; int i; H = (HashTable)malloc(sizeof(struct HashTbl)); if(H == NULL) Print_Err("no space for malloc H"); H->TableSize = NextPrime(Size); H->TheLists = (List *)malloc(sizeof(List) * H->TableSize); if(H->TheLists == NULL) Print_Err("no space for malloc H->TabLists"); for(i = 0; i < H->TableSize; i++) { H->TheLists[i] = (List)malloc(sizeof(struct ListNode)); if(H->TheLists[i] == NULL) Print_Err("no space for malloc H->TabLists[i]"); else H->TheLists[i]->Next = NULL; } return H; } Position Hash_Find(DataType key, HashTable H) { Position P; List L; L = H->TheLists[Hash(key, H->TableSize)]; P = L->Next; while(P != NULL && P->Data != key) P = P->Next; return P; } void Hash_Insert(DataType key, HashTable H) { Position pos, new_cell; List L; pos = Hash_Find(key, H); if(pos == NULL) { new_cell = malloc(sizeof(struct ListNode)); if(new_cell == NULL) Print_Err("no space in Hash_Insert"); else { L = H->TheLists[Hash(key, H->TableSize)]; new_cell->Next = L->Next; new_cell->Data = key; L->Next = new_cell; } } } void Hash_Delete(DataType key, HashTable H) { Position pos, front_cell, cur_cell; List L; pos = Hash_Find(key, H); if(pos != NULL) { L = H->TheLists[Hash(key, H->TableSize)]; front_cell = L; while(front_cell->Next != NULL && front_cell->Next->Data != key) { front_cell = front_cell->Next; } cur_cell = front_cell->Next; front_cell->Next = cur_cell->Next; free(cur_cell); } } int Hash_Free(HashTable H) { int i; for(i = 0; i < H->TableSize; i++) free(H->TheLists[i]); free(H->TheLists); free(H); return 1; } void Hash_Show(HashTable H) { int i; Position p; printf("H->TableSize:%d\n", H->TableSize); for(i = 0; i < H->TableSize; i++) { printf("H->TheLists[%d]: ", i); p = H->TheLists[i]; p = p->Next; while(p != NULL) { printf("%d ", p->Data); p = p->Next; } printf("\n"); } } /* * hash.c中要用到的子函數 */ void Print_Err(char *str) { printf("%s\n", str); exit(-1); } int IsPrime(unsigned int n) { unsigned int i; if(n < 2) return -1; for(i = 2; i < n; i++) { if(n % i == 0) return 0; } return 1; } int NextPrime(int n) { int i; for(i = n; ; i++) { if(IsPrime(i) == 1) return i; } exit(-1); } ~~~ //main.c函數測試 ~~~ #include <stdio.h> #include <stdlib.h> #include "hash.h" int main() { HashTable H = NULL; H = Hash_InitTable(6); Hash_Insert(1, H); Hash_Insert(2, H); Hash_Insert(3, H); Hash_Insert(24, H); Hash_Insert(5, H); Hash_Insert(6, H); Hash_Show(H); Hash_Delete(24, H); Hash_Show(H); if(Hash_Free(H) == 1) printf("free the HashTable is ok\n"); return 0; } ~~~ ? ? ? 1.開放定址法因為開放定址法都要置入表內，所以開放定址法所需要的表要比分離鏈接散列用表大。開放定址法分為線性探測法、平方探測法、雙散列 ![](https://box.kancloud.cn/2016-08-17_57b429207b797.jpg) ? ? ??平方探測是消除線性探測中一次聚集問題的沖突解決辦法，平方探測就是沖突函數為二次函數的探測方法。流行的選擇是F(i)=i^2，上圖顯示了使用該沖突函數所得到的開放定址散列表。 ? ? ? 如果使用平方探測法，且表的大小是素數，那么當表至少有一半是空的時候，總能夠插入一個新的元素。哪怕表有比一半多一個的位置被填滿時，那么插入都有可能失敗（雖然這是難以見到的） //開放定址法頭文件聲明-（平方探測法） ~~~ #ifndef HASH_H_INCLUDED #define HASH_H_INCLUDED #include <stdio.h> #include <stdlib.h> typedef unsigned int Index; typedef Index Position; struct HashTbl; typedef int DataType; typedef struct HashTbl *HashTable; HashTable Hash_Init(int Size); void Hash_Insert(DataType key, HashTable H); void Hash_Delete(DataType key, HashTable H); void Hash_Show(HashTable H); int Hash_Free(HashTable H); #endif // HASH_H_INCLUDED ~~~ //開放定址法功能函數聲明-（平方探測法） ~~~ #include "hash.h" enum KindOfEntry {Legitimate, Empty, Deleted}; struct HashEntry { DataType Data; enum KindOfEntry Info; }; typedef struct HashEntry Cell; struct HashTbl { int TableSize; Cell *TheCells; }; void Print_Err(char *str); int NextPrime(int n); HashTable Hash_Init(int Size) { HashTable H; int i; H = (HashTable)malloc(sizeof(struct HashTbl)); if(H == NULL) Print_Err("no space for H in Hash_Init()"); H->TableSize = NextPrime(Size); H->TheCells = (Cell *)malloc(sizeof(Cell) * H->TableSize); if(H->TheCells == NULL) Print_Err("no space for H->TheCells in Hash_Init()"); for(i = 0; i < H->TableSize; i++) H->TheCells[i].Info = Empty; return H; } Index Hash(const int key, int tablesize) { unsigned int hashval = 0; int x; x = key; if(x < 0) { printf("the key is low 0\n"); exit(-1); } while(x != 0) { hashval = (hashval << 3) + x%10; x /= 10; } return hashval % tablesize; } Position Hash_Find(DataType key, HashTable H) { Position cur_pos; int cnt; cnt = 0; cur_pos = Hash(key, H->TableSize); while(H->TheCells[cur_pos].Info != Empty && H->TheCells[cur_pos].Data != key) { cur_pos += (2 * ++cnt - 1); if(cnt >= H->TableSize) cnt -= H->TableSize; } return cur_pos; } void Hash_Insert(DataType key, HashTable H) { Position pos; pos = Hash_Find(key, H); if(H->TheCells[pos].Info != Legitimate) { H->TheCells[pos].Info = Legitimate; H->TheCells[pos].Data = key; } } void Hash_Delete(DataType key, HashTable H) { Position pos; pos = Hash_Find(key, H); if(H->TheCells[pos].Info == Legitimate) { H->TheCells[pos].Info = Empty; //H->TheCells[pos].Data = key; } } void Hash_Show(HashTable H) { int i; printf("H->TableSize: %d\n", H->TableSize); for(i = 0; i < H->TableSize; i++) { if(H->TheCells[i].Info == Legitimate) { printf("H->TheCells[%d]: %d\n", i, H->TheCells[i].Data); } else { printf("H->TheCells[%d]:\n", i); } } printf("\n"); } int Hash_Free(HashTable H) { if(H != NULL) { free(H->TheCells); free(H); } return 1; } /* * hash.c中要用到的子函數 */ void Print_Err(char *str) { printf("%s\n", str); exit(-1); } int IsPrime(unsigned int n) { unsigned int i; if(n < 2) return -1; for(i = 2; i < n; i++) { if(n % i == 0) return 0; } return 1; } int NextPrime(int n) { int i; for(i = n; ; i++) { if(IsPrime(i) == 1) return i; } exit(-1); } ~~~ //main.c測試主函數-（平方探測法） ~~~ #include <stdio.h> #include <stdlib.h> #include "hash.h" int main() { HashTable H; H = Hash_Init(6); Hash_Insert(1, H); Hash_Insert(2, H); Hash_Insert(3, H); Hash_Insert(13, H); Hash_Insert(14, H); Hash_Show(H); Hash_Delete(3, H); Hash_Show(H); Hash_Insert(3, H); Hash_Show(H); if(Hash_Free(H)) printf("free the hash is ok\n"); return 0; } ~~~ 3.其他的散列還有再散列和可擴展列。 ![](https://box.kancloud.cn/2016-08-17_57b42920a2da9.jpg)