目錄

一、引言

二、代碼結構與核心概念解析

1. 數據結構定義

2. 初始化函數?initList

3. 哈希函數?hash

4. 插入函數?put（核心邏輯）

開放尋址法詳解：

三、主函數驗證與運行結果

1. 測試邏輯

2. 運行結果分析

四、完整代碼

五、優化方向與注意事項

1. 現有代碼局限性

2. 優化建議

3. 注意事項

六、總結

七、擴展思考

---

一、引言

哈希表（Hash Table）是一種高效的數據結構，通過哈希函數實現數據的快速查找與插入。本文將通過一段 C 語言代碼實例，帶大家理解哈希表的基本原理，并分析開放尋址法解決哈希沖突的實現邏輯。

二、哈希表基礎概念

1. 定義與核心思想

哈希表（Hash Table，也稱為散列表）是一種根據鍵（Key）直接訪問內存存儲位置的數據結構。它通過哈希函數（Hash Function）將鍵映射到存儲桶（Bucket）或槽位（Slot），從而實現高效的數據插入、查找和刪除操作。

核心思想：將數據的鍵通過哈希函數轉換為數組索引，使數據可以直接定位，無需遍歷整個數據集。

2. 基本結構

一個簡單的哈希表通常由以下部分組成：

• 數組：作為存儲數據的物理空間，每個位置稱為一個 “槽位” 或 “桶”
• 哈希函數：將鍵轉換為數組索引的映射函數
• 沖突處理機制：解決不同鍵映射到相同索引的問題

3. 關鍵操作時間復雜度

• 插入：平均 O (1)，最壞 O (n)（沖突嚴重時）
• 查找：平均 O (1)，最壞 O (n)
• 刪除：平均 O (1)，最壞 O (n)

這種高效性使得哈希表廣泛應用于數據庫索引、緩存系統（如 Redis）、編程語言內置數據結構（如 Python 的字典、Java 的 HashMap）等場景。

三、代碼結構

1. 數據結構定義

typedef struct HashList
{int num;        // 記錄元素個數char *data;     // 哈希表數組
} HashList;

• num：用于統計哈希表中實際存儲的元素數量
• data：字符型數組，作為哈希表的存儲載體，大小由宏定義NUM（值為 10）決定

2. 初始化函數?initList

HashList *initList()
{HashList *list = (HashList *)malloc(sizeof(HashList));list->num = 0;list->data = (char *)malloc(sizeof(char) * NUM);for (int i = 0; i < NUM; i++){list->data[i] = 0;  // 初始化為0（空槽）}return list;
}

• 功能：分配哈希表結構體內存，初始化數組為空槽（0表示空）
• 關鍵點：動態內存分配確保哈希表可獨立管理內存，初始化空槽為后續沖突處理奠定基礎

3. 哈希函數?hash

int hash(char data)
{return data % NUM;  // 取模運算生成哈希地址
}

• 設計思路：利用字符 ASCII 碼對哈希表大小NUM取模，將字符映射到[0, 9]的索引范圍內
• 特點：簡單直觀，但可能產生哈希沖突（不同字符映射到相同索引）

4. 插入函數?put（核心邏輯）

void put(HashList *list, char data)
{if (list->num >= NUM){printf("哈希表已滿，無法插入");return;}int index = hash(data);          // 初始哈希地址int count = 1;                   // 沖突次數計數器// 開放尋址法解決沖突（線性探測）while (list->data[index] != 0)  {index = hash(hash(data) + count);  // 新地址 = 原哈希值 + 增量再取模count++;if (count == NUM)  // 嘗試所有位置后仍無空位{printf("無法找到空位插入");return;}}// 插入數據list->data[index] = data;list->num++;
}

開放尋址法詳解：

• 沖突處理策略：線性探測（Linear Probing）
  • 當發現哈希地址index被占用時，按index+1, index+2,...的順序依次查找下一個空槽
  • 代碼中通過hash(hash(data) + count)實現等價于(index + count) % NUM的循環探測
• 終止條件：
  • 找到空槽（data[index] == 0）
  • 遍歷所有槽位仍無空位（count == NUM）

四、主函數驗證與運行結果

1. 測試邏輯

int main()
{HashList *list = initList();put(list, 'A');  // 'A'的ASCII碼為65，65%10=5 → 初始地址5put(list, 'F');  // 'F'的ASCII碼為70，70%10=0 → 初始地址0（假設空槽）// 打印非空槽位for (int i = 0; i < NUM; i++){if (list->data[i] != 0){printf("data[%d]=%c\n", i, list->data[i]);}}printf("哈希表中有%d個元素", list->num);return 0;
}

2. 運行結果分析

假設'A'和'F'插入時均未發生沖突：

data[5]=A
data[0]=F
哈希表中有2個元素

• 若插入順序導致沖突（如先插入'K'（ASCII 75，75%10=5）再插入'A'），則'A'會探測到5+1=6號槽位（假設為空）并插入

五、完整代碼

#include <stdio.h>
#include <stdlib.h>
#define NUM 10typedef struct HashList
{int num;char *data;
} HashList;HashList *initList()
{HashList *list = (HashList *)malloc(sizeof(HashList));list->num = 0;list->data = (char *)malloc(sizeof(char) * NUM);for (int i = 0; i < NUM; i++){list->data[i] = 0;}return list;
}int hash(char data)
{return data % NUM;
}void put(HashList *list, char data)
{if (list->num >= NUM){printf("哈希表已滿，無法插入");}int index = hash(data);int count = 1;while (list->data[index] != 0){index = hash(hash(data) + count);count++;}if (count == NUM){printf("無法找到空位插入");}else{list->data[index] = data;list->num++;}
}int main()
{HashList *list = initList();put(list, 'A');put(list, 'F');for (int i = 0; i < NUM; i++){if (list->data[i] != 0){printf("data[%d]=%c\n", i, list->data[i]);}}printf("哈希表中有%d個元素", list->num);return 0;
}

六、優化方向與注意事項

1. 現有代碼局限性

• 固定大小：哈希表大小由NUM硬編碼，無法動態擴容
• 單一類型：僅支持字符型數據存儲，可通過泛型改造支持多類型
• 線性探測缺陷：可能產生 “聚類”（Cluster）現象，導致后續插入效率下降

2. 優化建議

優化點	方案
動態擴容	當元素個數超過負載因子（如 0.75）時，重新分配更大數組并重新哈希所有元素
改進沖突處理	改用二次探測（index + i2）或雙重哈希（多個哈希函數）
支持泛型	使用void*指針結合類型標簽，或通過 C11 _Generic 關鍵字實現

3. 注意事項

• 內存管理：使用完哈希表后需調用free釋放data和結構體內存，避免內存泄漏
• 負載因子控制：合理設置負載因子（元素數 / 表大小），平衡空間與時間效率
• 哈希函數設計：對于字符串等復雜數據，需設計更均勻的哈希函數（如 DJB2、FNV 算法）

七、總結

本文通過一個簡單的 C 語言實例，演示了哈希表的基本實現流程：

1. 哈希函數將數據映射到表中位置
2. 開放尋址法（線性探測）處理哈希沖突
3. 動態內存管理實現表的初始化與數據存儲

哈希表的核心優勢在于 ** 平均 O (1)** 的插入和查找時間復雜度，但其性能高度依賴哈希函數設計和沖突處理策略。實際開發中需根據數據特性選擇合適的哈希表實現方案。

八、擴展思考

1. 如何實現哈希表的查找（get）功能？
2. 嘗試用鏈表法（鏈地址法）改寫沖突處理邏輯
3. 分析線性探測與二次探測的性能差異

歡迎在評論區分享你的思路與實踐！