HASH表的创建（C语言）

---

一、简介:

哈希表又称散列表。哈希表存储的基本思想是：以数据表中的每个记录的关键字 key为自变量，通过一种函数H(key)计算出函数值。把这个值解释为一块连续存储空间（即数组空间）的单元地址（即下标），将该记录存储到这个单元中。在此称该函数H为哈函数或散列函数。按这种方法建立的表称为哈希表或散列表。

二、哈希冲突：

不同key值产生相同的地址，H(key1)=H(key2)

处理冲突的方法：

(1)开放寻址法：, i=1,2,…, k(k<=m-1)，其中H(key)为散列函数，m为散列表长，为增量序列，可有下列三种取法：
1.=1,2,3,…, m-1，称线性探测再散列；
2…,(k<=m/2)称二次探测再散列；
3.=伪随机数序列，称伪随机探测再散列。
最终存储结果 55 1 23 14 68 11 37 19 86
(2)再散列法：,i=1,2,…,k。均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间

(3)链地址法（拉链法）：将所有关键字为同义词的记录存储在同一线性链表中，产生hash冲突后在存储数据后面加一个指针，指向后面冲突的数据：

三、代码

#include<stdio.h>
#include<stdlib.h>
#define NUM 5
typedef struct HashList
{int num;			//表内当前的数据个数char *data;			//保存数据的数组
}HashList;//hash表的初始化
HashList *initList()
{HashList *list = (HashList *)malloc(sizeof(char)*NUM);list->num = 0;list->data = (char*)malloc(sizeof(char)*NUM);for(int i = 0;i < NUM;i++){list->data[i] = 0;		//将表内元素初始化为0}return list;
}//获取位置的下标
int hash(int data)
{return data % NUM;
}//放入哈希表
void put(HashList *list,char data)
{int index = hash(data);		//获取下标if(list->data[index] != 0){int count = 1;			//计数，便于解决冲突while(list->data[index] != 0){index = hash(hash(data) + count);	//解决冲突，如果下标位置有数据，则下标+1，直至下标位置上没有数据count++;}}list->data[index] = data;
}int main()
{HashList *list = initList();char str[10];scanf("%s",str);int i;for(i = 0;str[i] != '\0';i++){put(list,str[i]);}int j = 0;while(j<i){printf("%c\n",list->data[j++]);}
}