本章目录

• 哈希表
• • 1. 哈希函数
  • • 1.1 源代码
    • 1.2 测试结果
  • 2. 哈希冲突
  • • 2.1 开放地址法
    • • 2.1.1 源代码
      • 2.1.2 测试结果
    • 2.2 拉链法
    • • 2.2.1 源代码
      • 2.2.2 测试结果

哈希表

哈希表中元素是由哈希函数确定的，将数据元素的关键字key作为自变量，通过一定的函数关系（称为哈希函数），计算出的值，即为该元素的存储地址。

1. 哈希函数

哈希函数：指将哈希表中元素的关键键值映射为元素存储位置的函数
常用哈希函数

1. 直接定址法：直接取关键值为哈希表地址
2. 数字分析法：取重复性低的几位数字作为哈希表地址
3. 平方取中法：取关键字平方后的中间几位为哈希表地址
4. 折叠法：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍进位）作为哈希地址
5. 除留余数法：取关键值的余数作为哈希表地址
6. 随机数法：选择一个随机函数，取关键字的随机函数值为它的哈希地址

在不同场景中使用的哈希函数各不相同，也可以按照自己的需求设计哈希函数

1.1 源代码

#include 
#include 
#define MaxSize 10
#define NullKey -32768typedef int DataType;
typedef struct hashTable
{DataType *data;int count;  
}hashTable;// 初始化哈希表
void InitHashTable(hashTable *H)
{// 分配空间H->data = (DataType *)malloc(MaxSize * sizeof(DataType));H->count = 0;// 初始化int i;for (i = 0; i < MaxSize; i++){H->data[i] = NullKey;}printf("已初始化哈希表!\n");
}// 定义哈希函数
int Hash(DataType key)
{//  除留余数法return key % MaxSize;
}// 插入关键字
void InsertHashKey(hashTable *H, DataType key)
{// 根据哈希函数得到下标地址int address = Hash(key);printf("\n插入关键字 %d, 哈希地址 = %d\n", key, address);// 在目标地址存储数据if (H->data[address] == NullKey){H->data[address] = key;H->count++;printf("插入下标地址[%d], 插入成功!\n\n", address);}else{printf("插入下标地址[%d], 发生冲突!\n\n", address);}
}void DisplayHashTable(hashTable H)
{int i;printf("哈希表：\n");for (i = 0; i < MaxSize; i++){printf("%d\t", i);}printf("\n");for (i = 0; i < MaxSize; i++){if (H.data[i] != NullKey){printf("%d\t", H.data[i]);}else{printf("-\t");}}printf("\n\n");
}int main()
{int i;DataType key;hashTable H;InitHashTable(&H);printf("构建哈希表:");for (i = 0; i < MaxSize; i++){// 参考用例: 50 81 192 33 64 75 86 97 88 109scanf("%d", &key);InsertHashKey(&H, key);}DisplayHashTable(H);while (1){int address;printf("查找关键字: ");scanf("%d", &key);address = Hash(key);// 查找结果if (H.data[address] == key){printf("查找成功, 目标地址 = %d\n", address);}else{printf("查找失败\n");}}return 0;
}

1.2 测试结果

2. 哈希冲突

哈希冲突：两个关键字经过哈希函数处理后的结果都映射在同一地址位置上
而对于哈希表而言，无论哈希函数设计得有多精妙，都可能会发生冲突现象

例如插入序列：0 11 21 31 41 51 61 71 82 97

2.1 开放地址法

开放地址法：发生冲突时，寻找下一个空的哈希地址
其中查找下一个空的哈希地址的常用方法包括【线性探测法】和【二次探测】

• 线性探测法：每次向后移动d个位置（0 < d < MaxSize - 1）
• 二次探测法：每次向后移动1²、2²、3²… d²个位置

2.1.1 源代码

#include 
#include 
#define MaxSize 10
#define NullKey -32768typedef int DataType;
typedef struct hashTable
{DataType *data;int count;  
}hashTable;// 初始化哈希表
void InitHashTable(hashTable *H)
{// 分配空间H->data = (DataType *)malloc(MaxSize * sizeof(DataType));H->count = 0;// 初始化int i;for (i = 0; i < MaxSize; i++){H->data[i] = NullKey;}printf("已初始化哈希表!\n");
}// 定义哈希函数
int Hash(DataType key)
{//  除留余数法return key % MaxSize;
}// 插入关键字
void InsertHashKey(hashTable *H, DataType key)
{// 根据哈希函数得到下标地址int address = Hash(key);printf("\n插入关键字 %d, 哈希地址 = %d\n", key, address);int d = 1;// 若发生冲突则寻找下一个位置while (H->data[address] != NullKey){printf("插入下标地址[%d], 发生冲突\n", address);// 1. 线性探测法address = (address + d) % MaxSize;// 2. 二次探测法// address = (address + d * d) % MaxSize; d++;}// 在最终地址存储数据H->data[address] = key;H->count++;printf("插入下标地址[%d], 插入成功\n\n", address);
}// 查找关键字
int SearchHashKey(hashTable H, DataType key) 
{int address = Hash(key);int p = address;// 查找关键字while (H.data[p] != key){// 线性探测p = (p + 1) % MaxSize;// 指针遍历到空数据，或者指针回到原位置，则代表查找失败if (H.data[p] == NullKey || p == address){return -1;}}return p;
}void DisplayHashTable(hashTable H)
{int i;printf("哈希表：\n");for (i = 0; i < MaxSize; i++){printf("%d\t", i);}printf("\n");for (i = 0; i < MaxSize; i++){if (H.data[i] != NullKey){printf("%d\t", H.data[i]);}else{printf("-\t");}}printf("\n\n");
}int main()
{int i;DataType key;hashTable H;InitHashTable(&H);printf("构建哈希表:");for (i = 0; i < MaxSize; i++){// 参考用例: 50 81 191 32 65 75 9 97 88 109scanf("%d", &key);InsertHashKey(&H, key);}DisplayHashTable(H);while (1){int address;printf("查找关键字: ");scanf("%d", &key);    // 查找关键字地址address = SearchHashKey(H, key);if (address != -1){printf("查找成功, 目标地址 = %d\n", address);}else{printf("查找失败\n");}}return 0;
}

2.1.2 测试结果

2.2 拉链法

拉链法：哈希表的每个地址下都是链表结构，当发生冲突时，可将冲突数据存入链表中

• 如下图：关键字【1】和【21】、【31】、【41】、【51】在除留取余法中均会发生冲突，则只需要将冲突数据插入冲突地址下的链表即可。

2.2.1 源代码

#include 
#include 
#define MaxSize 10
#define NullKey -32768typedef int DataType;
// 链表结点
typedef struct LNode
{DataType data;struct LNode *next;
}LNode, *LinkList;
// 哈希表
typedef struct hashTable
{LinkList list;int count;  
}hashTable;// 初始化哈希表
void InitHashTable(hashTable *H)
{// 分配多个链表头结点空间H->list = (LNode *)malloc(MaxSize * sizeof(LNode));H->count = 0;// 初始化链表头结点（头结点存储初始值，链表后序结点存储冲突值）int i;for (i = 0; i < MaxSize; i++){H->list[i].data = NullKey;H->list[i].next = NULL;}printf("已初始化哈希表!\n");
}// 定义哈希函数
int Hash(DataType key)
{//  除留余数法return key % MaxSize;
}// 插入关键字
void InsertHashKey(hashTable *H, DataType key)
{// 根据哈希函数得到下标地址int address = Hash(key);printf("\n插入关键字 %d, 哈希地址 = %d\n", key, address);if(H->list[address].data == NullKey){// 若未发生冲突，则直接赋值给头结点H->list[address].data = key;printf("插入下标地址[%d], 插入成功!\n\n", address);}else{// 若发生冲突，则在该头结点的链表下进行头插// 创建新结点LNode *s;s = (LNode *)malloc(sizeof(LNode));s->data = key;// 头插法插入s->next = H->list[address].next;H->list[address].next = s;printf("插入下标地址[%d], 发生冲突! 已插入该地址的链表下\n\n", address);}H->count++;
}// 查找关键字
LNode* SearchHashKey(hashTable H, DataType key) 
{int address = Hash(key);// 根据哈希地址获取对应链表的头结点LNode *p = &H.list[address];// 在链表中查找关键字while (p != NULL && p->data != key){// 线性探测p = p->next;}return p;
}void DisplayHashTable(hashTable H)
{int i;printf("哈希表：\n**********************************\n");for (i = 0; i < MaxSize; i++){printf("%d\t", i);}printf("\n");LNode *p;int j, k = 0, flag = 1;while (flag){flag = 0;for (i = 0; i < MaxSize; i++){j = 0;p = &H.list[i];while (j < k && p){p = p->next;j++;}if (p && p->data != NullKey){printf("%d\t", p->data);flag = 1;}else{printf(" \t");}}k++;printf("\n");}printf("*********************************\n");
}int main()
{int i;DataType key;hashTable H;InitHashTable(&H);printf("构建哈希表:");for (i = 0; i < MaxSize; i++){// 参考用例: 50 81 191 32 65 75 9 97 88 109scanf("%d", &key);InsertHashKey(&H, key);}DisplayHashTable(H);while (1){LNode *result;printf("查找关键字: ");scanf("%d", &key);    // 查找关键字地址result = SearchHashKey(H, key);if (result != NULL){printf("查找成功, 目标地址 = %x\n", result);}else{printf("查找失败\n");}}return 0;
}

2.2.2 测试结果

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！