一. 簡介

前面文章簡單了解了哈希表 這種數據結構，文章如下：

什么是哈希表-CSDN博客

本文來學習一下哈希表，具體學習一下C語言實現對哈希表的簡單實現。

二.?C語言實現對哈希表的操作

1. 哈希表

哈希表（Hash Table，又稱散列表）是一種高效的數據結構，用于實現鍵值對（Key-Value）的存儲和快速查找。其核心思想是通過哈希函數將鍵（Key）映射到數組的特定位置（稱為“桶”或“槽”），從而在平均情況下實現接近常數時間復雜度（O(1)）的插入、刪除和查找操作。

2. C語言實現哈希表操作

(1) 定義哈希表節點結構體與哈希表結構體

#define  HASH_TABLE_LENGTH  20   //鏈表容量
#define  LOAD_FACTOR        0.85 //負載因子//哈希表節點結構
typedef struct hash_node {char *key; //鍵int value; //值struct hash_node* next; //下一個節點指針（用于解決沖突）
} hash_node;//哈希表結構
typedef struct hash_table {hash_node** buckets; //桶數組size_t size; //當前元素數量size_t capacity; //哈希表長度
} hash_table;

hash_node結構體表示每個鍵值對，hash_table表示每個桶，每個桶中存放一個鏈表。

(2) 創建哈希表，擴容哈希表容量

//創建哈希表
hash_table* create_hash_table(void) {hash_table* hash_tables = (hash_table*)malloc(sizeof(hash_table));if(!hash_tables) {printf("hash_table malloc failed!\n");return NULL;}hash_tables->size = 0;hash_tables->capacity = HASH_TABLE_LENGTH;hash_tables->buckets = (hash_node**)calloc(hash_tables->capacity, sizeof(hash_node*));if(!hash_tables->buckets) {printf("hash_tables->buckets calloc failed!\n");return NULL;}return hash_tables;
}//哈希函數的實現(djb2哈希算法)
unsigned long hash_func(const char* str) {unsigned long hash = 5381;int c;while((c = *str++)) {hash = ((hash << 5)+hash)+c;}return hash;
}//調節哈希表長度(擴容)
int resize_hash_table(hash_table* hash_tables, size_t new_capacity) {//分配新桶數組hash_node** new_buckets = (hash_node**)calloc(new_capacity, sizeof(hash_node*));if(!new_buckets) {printf("new_buckets calloc failed!\n");return -1;}int i = 0;//遍歷原有桶數組，并重新哈希for(i = 0; i < hash_tables->capacity; i++) {hash_node* node = hash_tables->buckets[i];while(node != NULL) {hash_node* tmp_node = node->next;unsigned long new_index = hash_func(node->key)/ new_capacity;//采用頭插入法，插入到新桶中node->next = new_buckets[new_index];new_buckets[new_index] = node;//遍歷下一個元素node = tmp_node;}}hash_tables->buckets = new_buckets;hash_tables->capacity = new_capacity;free(hash_tables->buckets);return 0;
}

創建哈希表比較簡單，這里不做說明。

調整哈希表容量接口這里進行一下說明：

首先，分配新哈希表的容量。

其次，遍歷原來哈希表中所有元素（鍵值對），將舊的哈希表中元素插入到哈希表新桶中。由于哈希表的容量發生了改變，原有的鍵值對需要重新計算哈希值并插入到新的哈希表中。

node->next = new_buckets[new_index]; 
new_buckets[new_index] = node;

這兩行代碼的作用是將當前處理的哈希表節點 node 插入到新哈希表的對應桶（bucket）中，采用的是頭插法。

node->next = new_buckets[new_index];

• 含義：將當前節點 node 的 next 指針指向新哈希表中對應桶的頭節點。
• 作用：這一步是為了把當前節點插入到新桶的頭部。若新桶原本為空，new_buckets[new_index] 會是 NULL，那么 node->next 就會被設為 NULL；若新桶已經有節點存在，new_buckets[new_index] 就會指向桶中的頭節點，此時 node->next 就會指向這個頭節點。

new_buckets[new_index] = node;

• 含義：把新哈希表中對應桶的頭節點更新為當前節點 node。
• 作用：經過這一步，當前節點 node 就成為了新桶的頭節點。原本新桶中的節點（如果有的話）就變成了 node 的后繼節點。

(3) 向哈希表中插入新的鍵值對