建设个网站长沙做网站哪里好
一、概念
哈希表（Hash Table）是一种数据结构，用于实现关联数组（Associative Array），即可以通过键（Key）来查找对应的值（Value）。哈希表使用哈希函数将键转换为数组下标，从而实现快速查找、插入和删除操作。
哈希表的主要优点是查询速度非常快，时间复杂度接近O(1)。但是，哈希表的缺点是在数据量较大时，可能会出现哈希冲突（Hash Collision），即不同的键经过哈希函数计算后得到相同的哈希值。解决哈希冲突的方法有多种，如开放寻址法（Open Addressing）、链地址法（Chaining）等。
常见的哈希表实现有：Java中的HashMap、Python中的字典（dict）等。
散列技术既是一种存储方法，又是一种查找方法。最适合求解的问题是查找与给定值相等的记录。
冲突就是参数不同，结果相同。
二、哈希函数
哈希函数常见的构造方法
1、直接定址法
2、数字分析法
3、平方取中法
4、折叠法
5、除留余数法（最常用）
6、随机数法
7、构造哈希函数需考虑的因素
三、处理冲突常用方法
1、开放地址法
2、再散列函数法
3、链地址法
4、公共溢出区法
四、哈希表结构
五、代码示例（除留余数法）
这里用线性探测法处理冲突
#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef int DATATYPE;
typedef struct
{DATATYPE *head;int tlen;
}HS;HS* CreateHsTable(int len)； //创建哈希表
void DestroyHsTable(HS* hs)； //销毁哈希表
int HSFun(HS* hs,DATATYEP*data)； //哈希函数
int HSInsert(HS* hs, DATATYEP* data)； //数据插入哈希表
int HSSearch(HS* hs,DATATYEP*data) //哈希查找HS* CreateHsTable(int len)
{HS* hs = (HS*)malloc(sizeof(HS));if(NULL == hs){perror("CreateHsTable");return NULL;}hs->head = (DATATYEP*)malloc(sizeof(DATATYEP)*len);if(NULL == hs){perror("hs->head malloc");return NULL;}hs->tlen = len;int i = 0 ;for(i=0;i<len;i++){hs->head [i] = -1;} return hs;
}void DestroyHsTable(HS* hs)
{free(hs->head);free(hs);
}int HSFun(HS* hs,DATATYEP*data)
{return *data % hs->tlen ;
}int HSInsert(HS* hs, DATATYEP* data)
{int ind= HSFun(hs,data) ;while(hs->head [ind]!=-1){ind = (ind+1)%hs->tlen;
// printf("ind:%d num:%d\n",ind,*data); }memcpy(&hs->head [ind],data,sizeof(DATATYEP));printf("ind:%d num:%d\n",ind,hs->head[ind]); return 0;
}int HSSearch(HS* hs,DATATYEP*data)
{int ind = HSFun(hs,data);int oldind = ind;while(hs->head[ind]!=*data){ind=(ind+1)%hs->tlen ;if(ind == oldind){return -1;}}return ind;
}int main(int argc, char *argv[])
{int array[12]={11,22,33,44,55,66,77,88,99,100,110,120};HS* hs = CreateHsTable(12);int i =0;for(i = 0 ;i<12;i++) //将每一个元素插入哈希表{HSInsert(hs,&array[i]); }int n = 66; int ret = HsSearch(hs,&n); //查找给定数据if(-1 == ret){printf("can't find\n"); //找不到数据} else{printf("find it, ind:%d\n",ret); //找到返回数字的下标}return 0;
}