給出哈希之閉散列的定義：

#define HashMaxSize 1000typedef enum Stat {Empty,Valid,Invalid //當前元素被刪除了 }Stat;typedef int KeyType; typedef int ValType;typedef size_t(*HashFunc)(KeyType key);typedef struct HashElem {KeyType key;ValType value;Stat stat; // 引入一個 stat 標記來作為是否有效的標記 }HashElem;typedef struct HashTable {HashElem data[HashMaxSize];size_t size;HashFunc hash_func; }HashTable;

將函數的聲明放在head.h的頭文件里面：

// 現在使用閉散列的方式實現hash表（通用的hash表） // // 下面的問題是我們要解決的問題之一 // 統計一個數組中每一個元素出現的個數 // 這個時候就可以用 value 來表示次數了 // 給定一個數組 {1，1，1，2，2，3} // 遍歷數組 // 1）先將hash表中查找（得到了當前元素的次數） // 2）如果元素在hash表中存在，將這個次數（value）+ 1 // 3) 如果元素在hash表中不存在，插入一個新的元素，初始value為1 #pragma once#include <stddef.h> #include <windows.h> #include <stdio.h>#define HashMaxSize 1000typedef enum Stat {Empty,Valid,Invalid //當前元素被刪除了 }Stat;typedef int KeyType; typedef int ValType;typedef size_t(*HashFunc)(KeyType key);typedef struct HashElem {KeyType key;ValType value;Stat stat; // 引入一個 stat 標記來作為是否有效的標記 }HashElem;typedef struct HashTable {HashElem data[HashMaxSize];size_t size;HashFunc hash_func; }HashTable;/// 哈希函數 size_t HashFuncDefault(KeyType key);// 初始化 void HashInit(HashTable* ht, HashFunc hash_func);// 插入 int HashInsert(HashTable* ht, KeyType key, ValType value);// 輸入key，查找對應key的value int HashFind(HashTable* ht, KeyType key, ValType* value);// 刪除 void HashRemove(HashTable* ht, KeyType key);// 判空 int HashEmpty(HashTable* ht);// 大小 size_t HashSize(HashTable* ht);// 銷毀 void HashDestroy(HashTable* ht);// 打印 void HashPrintInt(HashTable* ht, const char* msg);

函數的定義（具體實現）：

#include "Hash.h"// 默認的取哈希值的方式 // 比較簡單，但是沖突的可能性也比較大 size_t HashFuncDefault(KeyType key) {return key % HashMaxSize; }void HashInit(HashTable* ht, HashFunc hash_func) {if (ht == NULL){// 非法輸入return;}ht->hash_func = hash_func;ht->size = 0;size_t i = 0;for (; i < HashMaxSize; ++i){ht->data[i].stat = Empty;}return; }void HashPrintInt(HashTable* ht, const char* msg) {printf("[%s]\n", msg);size_t i = 0;for (; i < HashMaxSize; ++i){if (ht->data[i].stat != Empty){printf("[%lu] key = %d, value = %d stat = %d\n", i, ht->data[i].key, ht->data[i].value, ht->data[i].stat);}} }int HashInsert(HashTable* ht, KeyType key, ValType value) {if (ht == NULL){// 非法輸入return 0;}if (ht->size >= HashMaxSize * 0.8) // 設定負載因子為 0.8{// 這里認為hash表已經滿了，不能繼續插入return 0;}// 先找到 key 對應的下標size_t offset = ht->hash_func(key);while (1){if (ht->data[offset].stat == Valid){if (ht->data[offset].key == key){// 發現在hash表中已經存在了相同的元素// 策略1：認為插入失敗// 策略2：更新對應的value// ht->data[offset].value = value;return 0;}// 出現了hash沖突，使用線性探測的方式查找下一個元素++offset;if (offset >= HashMaxSize) // 判斷越界和處理{offset -= HashMaxSize;}}else{// 由于我們的負載因子是 80%，一定能找到一個空位ht->data[offset].key = key;ht->data[offset].value = value;ht->data[offset].stat = Valid;++ht->size;return 1;}}return 0; }int HashFind(HashTable* ht, KeyType key, ValType* value) {if (ht == NULL || value == NULL){// 非法輸入return 0;}// 1. 通過hash函數計算數組下標size_t offset = ht->hash_func(key);// 2. 從這個數組下標開始，線性的向后查找while (1){// a) 如果找到了某個元素的 key 是想要的值，并且狀態為 Valid，就認為找到了，就將 value 賦值給輸出參數if (ht->data[offset].key == key && ht->data[offset].stat == Valid){// 找到了想要找的元素*value = ht->data[offset].value;return 1;}// b) 如果發現當前位置的狀態是 Empty，就認為沒有找到else if (ht->data[offset].stat == Empty){return 0;}// c）繼續嘗試查找下一個位置else{offset++;if (offset >= HashMaxSize) // 判斷越界和處理{offset -= HashMaxSize;}}}return 0; }void HashRemove(HashTable* ht, KeyType key) {if (ht == NULL){return;}// 1. 根據 key 找到對應的數組下標size_t offset = ht->hash_func(key);// 2. 從找到的下標開始依次遍歷while (1){// 6種情況：// 1. key 相同：// a) 狀態為 Valid// b) 狀態為 Empty// c) 狀態為 Invalid// 2. key 不相同：// a) 狀態為 Valid// b) 狀態為 Empty// c) 狀態為 Invalid// a) 如果當前元素的 key 為要刪除的 key，并且狀態為 Valid，就將狀態置為 Invalid，并且要 -- sizeif (ht->data[offset].key == key && ht->data[offset].stat == Valid){// 找到了想要找的元素ht->data[offset].stat = Invalid;--ht->size;return;}// b) 如果當前元素的狀態為 Empty，要刪除的 key 沒有找到，不需要進行任何刪除了else if (ht->data[offset].stat == Empty){return;}// c) 剩下的情況，就依次的取下一個元素就行了else{offset++;if (offset >= HashMaxSize) // 判斷越界和處理{offset -= HashMaxSize;}}}return; }int HashEmpty(HashTable* ht) {if (ht == NULL){return 1;}return ht->size == 0 ? 1 : 0; }size_t HashSize(HashTable* ht) {if (ht == NULL){return 0;}return ht->size; }void HashDestroy(HashTable* ht) // 清理掉所有狀態 {size_t i = 0;for (; i < HashMaxSize; ++i){ht->data[i].stat = Empty;}ht->size = 0;ht->hash_func = NULL;return; }

測試代碼：

#include "Hash.h"void TestInit() {HashTable ht;HashInit(&ht, HashFuncDefault);printf("ht->size expect 0, actual %lu\n", ht.size);printf("ht->hash_func expect %p, actual %p\n", HashFuncDefault, ht.hash_func);size_t i = 0;for (; i < HashMaxSize; ++i){if (ht.data[i].stat != Empty){printf("pos [%lu] elem error!\n", i);}} }void TestInsert() {HashTable ht;HashInit(&ht, HashFuncDefault);HashInsert(&ht, 1, 100);HashInsert(&ht, 2, 200);HashInsert(&ht, 1001, 300);HashInsert(&ht, 1002, 400);HashPrintInt(&ht, "插入四個元素"); }void TestFind() {HashTable ht;HashInit(&ht, HashFuncDefault);HashInsert(&ht, 1, 100);HashInsert(&ht, 2, 200);HashInsert(&ht, 1001, 300);HashInsert(&ht, 1002, 400);int value = 0;int ret = HashFind(&ht, 1, &value);printf("ret expect 1, actual %d\n", ret);printf("vaule expect 100, actual %d\n", value);ret = HashFind(&ht, 1001, &value);printf("ret expect 1, actual %d\n", ret);printf("value expect 300, actual %d\n", value);ret = HashFind(&ht, 1005, &value);printf("ret expect 0, actual %d\n", ret); }void TestRemove() {HashTable ht;HashInit(&ht, HashFuncDefault);HashInsert(&ht, 1, 100);HashInsert(&ht, 2, 200);HashInsert(&ht, 1001, 300);HashInsert(&ht, 1002, 400);HashRemove(&ht, 1);HashPrintInt(&ht, "刪除 key 為 1 的元素：");int value = 0;int ret = HashFind(&ht, 1, &value);printf("ret expect 0, actual %d\n", ret);ret = HashFind(&ht, 1001, &value);printf("ret expect 1, actual %d\n", ret);printf("value expect 300, actual %d\n", value); }// 哈希桶（統計元素個數） void CountNum() {int array[] = { 1, 1, 1, 2, 2, 3 };HashTable ht;HashInit(&ht, HashFuncDefault);size_t i = 0;for (; i < sizeof(array) / sizeof(array[0]); ++i){int value = 0;int ret = HashFind(&ht, array[i], &value);if (ret == 0){// 沒有找到HashInsert(&ht, array[i], 1);}else{// 該元素已經存在HashRemove(&ht, array[i]);HashInsert(&ht, array[i], value + 1);}}HashPrintInt(&ht, "統計的最終結果為："); }c++ 中的hash，做了這樣的事情重載了 [] 運算符如果1已經存在，就取出對應的value如果1已經不存在，插入一個默認的值int value = ht[1]; ht[1] = value; //#include <unordered_map> //void CountNum_CPP() //{ // int array[] = { 1, 1, 1, 2, 2, 3 }; // std::unordered_map<int, int>ht; // size_t i = 0; // for (; i < sizeof(array) / sizeof(array[0]); ++i) // { // ++ht[i]; // } // // 遍歷哈希表，打印結果就可以了 // for (auto item : ht) // { // printf("%d,%d\n", item.fist, item.second); // } //}int main() {TestInit();TestInsert();TestFind();TestRemove();CountNum();//CountNum_CPP();system("pause");return 0; }

結果如下：

總結

以上是生活随笔為你收集整理的哈希之闭散列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。