[数据结构]#7 哈希表

哈希表（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也是一个典型的哈希表实现。