基本概念
- 散列表：散列表存储了各个关键字
key及其地址。 - 散列函数：
p=H(key)，关键字key到其地址的映射。 - 散列地址：将
key作为参数，丢到散列函数H()中，算出来的结果，就是散列地址。 -
冲突：不同的
key，通过散列函数算出来的散列地址一样，这种现象称为冲突。即key1≠key2，但H(key1)=H(key2)。
散列查找的思路
- 给定待查找的关键字
key，根据散列函数计算出散列地址p=H(key)。 - 若地址
p中的元素为空，则key不存在，查找失败。 - 若地址
p中的元素为key，则没有冲突，查找成功，返回地址p。 - 否则（即地址
p中有元素，但该元素不为key），说明出现了冲突，利用处理冲突的方法，计算出下一个散列地址p，跳到步骤2。
代码实现
#include <stdio.h>
#include <stdlib.h>
#define SUCCESS 1
#define UNSUCCESS 0
#define OVERFLOW -1
#define OK 1
#define ERROR -1
typedef int Status;
typedef int KeyType;
typedef struct
{
KeyType key;
} RcdType;
typedef struct
{
RcdType *rcd;
int size;
int count;
int *tag;
} HashTable;
int hashsize[] = {11, 31, 61, 127, 251, 503};
int index = 0;
Status InitHashTable(HashTable &H, int size)
{
int i;
H.rcd = (RcdType *)malloc(sizeof(RcdType) * size);
H.tag = (int *)malloc(sizeof(int) * size);
if (NULL == H.rcd || NULL == H.tag)
return OVERFLOW;
for (i = 0; i < size; i++)
H.tag[i] = 0;
H.size = size;
H.count = 0;
return OK;
}
int Hash(KeyType key, int m)
{
return (3 * key) % m;
}
void collision(int &p, int m)
{ //线性探测
p = (p + 1) % m;
}
Status SearchHash(HashTable H, KeyType key, int &p, int &c)
{
p = Hash(key, H.size);
int h = p;
c = 0;
while ((1 == H.tag[p] && H.rcd[p].key != key) || -1 == H.tag[p])
{
collision(p, H.size);
c++;
}
if (1 == H.tag[p] && key == H.rcd[p].key)
return SUCCESS;
else
return UNSUCCESS;
}
void printHash(HashTable H) //打印哈希表
{
int i;
printf("key : ");
for (i = 0; i < H.size; i++)
printf("%3d ", H.rcd[i].key);
printf("\n");
printf("tag : ");
for (i = 0; i < H.size; i++)
printf("%3d ", H.tag[i]);
printf("\n\n");
}
Status InsertHash(HashTable &H, KeyType key); //对函数的声明
//重构
Status recreateHash(HashTable &H)
{
RcdType *orcd;
int *otag, osize, i;
orcd = H.rcd;
otag = H.tag;
osize = H.size;
InitHashTable(H, hashsize[index++]);
//把所有元素，按照新哈希函数放到新表中
for (i = 0; i < osize; i++)
{
if (1 == otag[i])
{
InsertHash(H, orcd[i].key);
}
}
}
Status InsertHash(HashTable &H, KeyType key)
{
int p, c;
if (UNSUCCESS == SearchHash(H, key, p, c))
{ //没有相同key
if (c * 1.0 / H.size < 0.5)
{ //冲突次数未达到上线
//插入代码
H.rcd[p].key = key;
H.tag[p] = 1;
H.count++;
return SUCCESS;
}
else
recreateHash(H); //重构哈希表
}
return UNSUCCESS;
}
Status DeleteHash(HashTable &H, KeyType key)
{
int p, c;
if (SUCCESS == SearchHash(H, key, p, c))
{
//删除代码
H.tag[p] = -1;
H.count--;
return SUCCESS;
}
else
return UNSUCCESS;
}
void main()
{
printf("-----哈希表-----\n");
HashTable H;
int i;
int size = 11;
KeyType array[8] = {22, 41, 53, 46, 30, 13, 12, 67};
KeyType key;
RcdType e;
//初始化哈希表
printf("初始化哈希表\n");
if (SUCCESS == InitHashTable(H, hashsize[index++]))
printf("初始化成功\n");
//插入哈希表
printf("插入哈希表\n");
for (i = 0; i <= 7; i++)
{
key = array[i];
InsertHash(H, key);
printHash(H);
}
//删除哈希表
printf("删除哈希表\n");
int p, c;
if (SUCCESS == DeleteHash(H, 12))
{
printf("删除成功，此时哈希表为：\n");
printHash(H);
}
//查询哈希表
printf("查询哈希表\n");
if (SUCCESS == SearchHash(H, 67, p, c))
printf("查询成功\n");
//再次插入，测试哈希表的重构
printf("再次插入，测试哈希表的重构：\n");
KeyType array1[8] = {27, 47, 57, 47, 37, 17, 93, 67};
for (i = 0; i <= 7; i++)
{
key = array1[i];
InsertHash(H, key);
printHash(H);
}
}
参考资料：
1.https://blog.csdn.net/CHENYUFENG1991/article/details/50678878
