數據結構 散列表

哈希表(Hash Table):

通過哈希函數將鍵（key）映射到存儲位置，從而實現快速的插入、刪除和查找操作。

哈希表是現代編程中最重要的數據結構之一，幾乎所有編程語言都提供了內置實現。

計數

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define TABLE_SIZE 100  // 哈希表大小// 哈希表節點結構
typedef struct Node {int key;          // 存儲的元素值int count;        // 出現次數struct Node* next; // 鏈表指針（處理沖突）
} Node;// 創建新節點
Node* createNode(int key) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->key = key;newNode->count = 1;newNode->next = NULL;return newNode;
}// 簡單哈希函數
unsigned int hash(int key) {return key % TABLE_SIZE;
}// 插入元素到哈希表
void insert(Node* hashTable[], int key) {unsigned int index = hash(key);// 檢查是否已存在Node* current = hashTable[index];while (current != NULL) {if (current->key == key) {current->count++; // 已存在，計數增加return;}current = current->next;}// 不存在，創建新節點Node* newNode = createNode(key);newNode->next = hashTable[index];hashTable[index] = newNode;
}// 打印哈希表內容
void printHashTable(Node* hashTable[]) {for (int i = 0; i < TABLE_SIZE; i++) {Node* current = hashTable[i];while (current != NULL) {printf("元素 %d 出現次數: %d\n", current->key, current->count);current = current->next;}}
}// 釋放哈希表內存
void freeHashTable(Node* hashTable[]) {for (int i = 0; i < TABLE_SIZE; i++) {Node* current = hashTable[i];while (current != NULL) {Node* temp = current;current = current->next;free(temp);}}
}int main() {Node* hashTable[TABLE_SIZE] = {NULL}; // 初始化哈希表int nums[] = {1, 2, 3, 2, 1, 3, 3, 4, 5, 4, 4, 4};int size = sizeof(nums) / sizeof(nums[0]);// 統計每個元素的出現次數for (int i = 0; i < size; i++) {insert(hashTable, nums[i]);}// 打印統計結果printHashTable(hashTable);// 釋放內存freeHashTable(hashTable);return 0;
}

哈希函數:將任意大小的數據映射到固定大小的值（哈希值）

#include <stdio.h>
#include <string.h>// 簡單哈希函數 - 適用于字符串
unsigned int simple_hash(const char* str) {unsigned int hash = 0;while (*str) {hash = (hash * 31) + *str; // 31是個常用質數str++;}return hash;
}// 測試
int main() {const char* str1 = "hello";const char* str2 = "world";printf("'%s' 的哈希值: %u\n", str1, simple_hash(str1));printf("'%s' 的哈希值: %u\n", str2, simple_hash(str2));return 0;
}

桶（Bucket）：存儲數據的容器，通常是一個數組

沖突（Collision）：不同鍵映射到相同哈希值的情況

滾動哈希:一種高效處理字符串/數組子串哈希的技術，常用于字符串匹配、重復子串檢測等場景

#include <stdio.h>
#include <string.h>#define BASE 256  // 基數，通常選擇質數
#define MOD 101   // 模數，通常選擇大質數// 計算初始哈希值
unsigned long initial_hash(const char* str, int len) {unsigned long hash = 0;for (int i = 0; i < len; i++) {hash = (hash * BASE + str[i]) % MOD;}return hash;
}// 滾動哈希計算下一個哈希值
unsigned long roll_hash(unsigned long prev_hash, char left_char, char right_char, int len, unsigned long power) {prev_hash = (prev_hash + MOD - (left_char * power) % MOD) % MOD;return (prev_hash * BASE + right_char) % MOD;
}// 查找模式串在文本中的位置
void rabin_karp(const char* text, const char* pattern) {int n = strlen(text);int m = strlen(pattern);if (m == 0 || n < m) return;// 計算BASE^(m-1) % MODunsigned long power = 1;for (int i = 0; i < m - 1; i++) {power = (power * BASE) % MOD;}unsigned long pattern_hash = initial_hash(pattern, m);unsigned long text_hash = initial_hash(text, m);for (int i = 0; i <= n - m; i++) {if (text_hash == pattern_hash) {// 哈希匹配，驗證實際字符串是否匹配if (strncmp(text + i, pattern, m) == 0) {printf("在位置 %d 找到匹配\n", i);}}// 滾動到下一個位置if (i < n - m) {text_hash = roll_hash(text_hash, text[i], text[i + m], m, power);}}
}int main() {const char* text = "ABABDABACDABABCABAB";const char* pattern = "ABABCABAB";rabin_karp(text, pattern);return 0;
}

哈希工作原理

插入數據時 計算哈希值? 確定儲存位置

查找數據時 計算哈希值? 直接訪問對應位置

處理沖突時

????????????????鏈接地址法 每個桶使用鏈表 儲存多個元素

? ? ? ? ? ? ? ? 開放尋址法 尋找下一個可用位置

應用場景

• 數據庫索引

• 緩存實現（如Redis）

• 語言中的字典/映射結構（如Python的dict，Java的HashMap）

• 唯一性檢查

優缺點

優點：

• 平均情況下操作非常快

• 實現簡單直接

缺點：

• 哈希函數設計影響性能

• 沖突處理增加復雜度

• 不支持有序遍歷（除非使用特殊實現）