哈希表（Hash Table），有時也稱為散列表，是一種數據結構，它提供了一種快速存取數據的方法。哈希表利用一個被稱為哈希函數的機制將鍵映射到表中的一個位置來直接訪問記錄，以此加快查找的速度。哈希表通常支持非常快的插入、刪除和查找操作，平均情況下這些操作的時間復雜度為O(1)。
基本概念
鍵（Key）：
用于唯一標識哈希表中每個元素的值。
值（Value）：
與鍵關聯的數據或信息。
哈希函數（Hash Function）：
用于計算給定鍵的哈希碼，從而確定該鍵值對在哈希表中的存儲位置。
沖突（Collision）：
當兩個不同的鍵通過哈希函數得到相同的哈希碼時，這種情況稱為沖突。解決沖突是設計哈希表時必須考慮的問題。
發生沖突時的解決策略
鏈地址法（Chaining）：
使用鏈表存儲具有相同哈希值的所有元素。因此，每個桶實際上是一個鏈表，包含所有被哈希到同一個索引的元素。
開放地址法（Open Addressing）：
當發生沖突時，尋找下一個空位來存儲這個鍵值對。常見的技術包括線性探測、二次探測和雙重哈希等。
哈希表的操作
插入：
根據鍵計算出哈希值，并將其對應的值存入哈希表中。如果存在沖突，則按照所選的沖突解決策略處理。
查找：
根據鍵計算出哈希值，然后從相應的槽中找到對應的值。若采用鏈地址法，還需遍歷鏈表；若采用開放地址法則可能需要沿著探查序列搜索。
刪除：
首先查找要刪除的鍵，然后移除它。在開放地址法中，刪除后可能還需要重新組織哈希表以保持其正確性。
示例代碼：
//哈希表#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int DATATYPE;
typedef struct
{DATATYPE* head;int tlen;
} HSTABLE;HSTABLE* CreateHSTable(int n)
{HSTABLE* hs = malloc(sizeof(HSTABLE));if(NULL == hs){fprintf(stderr,"CreateHSTable malloc");return NULL;}hs->head = malloc(sizeof(DATATYPE)*n);if(NULL == hs->head){fprintf(stderr,"CreateHSTable malloc");return NULL;}hs->tlen = n;for(int i=0; i<n;i++) //給數組設置初值{hs->head[i] = -1;}return hs;}int HSFun(HSTABLE* hs,DATATYPE* dat)
{return *dat %hs->tlen;
}int HS_Insert(HSTABLE* hs, DATATYPE* dat)
{int idx = HSFun(hs,dat);while(hs->head[idx]!=-1) //判斷當前位置是否是空閑{printf("沖突 idx:%d num:%d\n",idx, *dat);idx= (idx+1) %hs->tlen;}hs->head[idx] = *dat;return 0;
}int HS_Search(HSTABLE* hs, DATATYPE* dat)
{int idx = HSFun(hs,dat);int old_idx = idx;while(hs->head[idx] != *dat){idx= (idx+1) %hs->tlen;if(old_idx == idx){return -1;}}return idx;return 0;
}int DestroyHS(HSTABLE* hs)
{free(hs->head);free(hs);return 0;
}DATATYPE *GetItemHSTable(HSTABLE* hs,int idx) //5 0-4
{if(idx<0 || idx > hs->tlen-1){return NULL;}return &hs->head[idx];
}int main(int argc, char** argv)
{int array[12]={12,67,56,16,25,37,22,29,15,47,48,34};HSTABLE* hs = CreateHSTable(12);for(int i = 0 ;i<12 ;i++){HS_Insert(hs, &array[i]);}int want_num = 35;int ret = HS_Search(hs, &want_num);if(-1 == ret){printf("cant find %d\n",want_num);}else {printf("find it , idx:%d num:%d\n",ret,*GetItemHSTable(hs, ret));}// system("pause");return 0;
}
優缺點
優點：
平均時間復雜度為O(1)，非常適合用于快速查找。
空間利用率高，適合大規模數據集。
缺點：
在最壞的情況下（如所有元素都被哈希到同一個桶），查找時間復雜度可能會退化至O(n)。
需要額外的空間來處理沖突。
不同類型的哈希函數對于不同類型的數據表現不同，選擇合適的哈希函數至關重要。
應用場景
哈希表廣泛應用于各種領域，比如數據庫系統中的快速查找、編譯器設計中的符號表管理、緩存實現以及算法設計中的集合、圖表示等。由于其實現簡單且效率高，在實際編程中也是常用的數據結構之一。例如，在Python中，字典（dictionary）就是基于哈希表實現的；在Java中，HashMap也是一個典型的哈希表實現。
)
