数据结构----哈希
哈希（Hash）是一种数据结构，它通过哈希函数将键(Key)映射到表中一个位置来访问记录，以加快查找的速度。
一、基本概念
哈希函数（Hash Function）：也称散列函数，一种算法，它接收任意长度的输入数据，并产生一个固定长度的输出字符串（哈希值），即 将键转换成哈希表索引的函数
键值对（key-value pairs）: 在哈希表中，数据通常以键值对的形式存储，键通过哈希函数映射到哈希表的一个位置，该位置存储对应的值
哈希表（Hash Table）：也称散列表，一种使用哈希函数来存储和检索数据的数据结构，用于存储键值对
冲突（Collision）: 当两个键的哈希值相同，即发生哈希冲突
二、哈希函数的构造方法
一个好的哈希函数：关键字通过哈希函数得到一个"随机的地址"，从而使一组关键字的哈希地址均匀的分布在地址区间中，从而减少冲突
1. 直接定址法
f(x)=x 关键字值 直接作为哈希函数/散列函数
优点：避免哈希冲突
缺点：空间利用率低 该方法极少使用
2. 数字分析法
一般用于手机号码这种有规律的 选取关键字进行分析
优点：适合处理数据位数较多的关键字
缺点：必须了解关键字的分布特征(如手机号)
3. 平方取中法
将关键字平方后，抽取其中一部分用作哈希地址，例如关键字是1224，则平方之后是1498176，取中间三位981作为哈希地址
优点：适合不知道关键字的分布规律，但是位数不多的情况
缺点：只能处理关键字位数不多的情况
4. 折叠法
折叠法就是将关键字分割成位数相同的几个部分，然后将这几个部分进行四则运算（如求和），并且还可以根据哈希表长度再抽取其中的一部分作为哈希地址。
例如：关键字是9876543210，哈希表的长度为3，则将其从左向右3，3分开，|987|654|321|0|，然后叠加求和987+654+321+0=1962，则再取末尾3位，则哈希地址为962。
优点：适合不知道关键字分布规律且关键字位数比较大的情况
5. 除留余数法
最常用的构造哈希函数的方法， index=val % len
6.随机值法
选取一个随机数，将随机函数值作为它的哈希地址。
三、哈希冲突的解决方法及代码
1. 链地址法
· 每一个槽位是一个链表，当插入元素时，如果发生冲突，将其添加到对应槽位的链表中
· 插入一个新的元素时，一般是头插，类似于单链表的头插法
· 查找时，先找到对应的槽位，然后再链表中查找
代码：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
#define INITSIZE 10
#define LOAD_FACTOR 0.75
#define REHASH_SIZE_MULTIPLIER 2
typedef struct Node {
int data;
struct Node* next;
} Node;
typedef struct listhash {
Node* table[INITSIZE];
} listhash;
void init(listhash* hash) {
assert(hash);
//数组每个元素赋值为空 NULL--头指针指向空
memset(hash->table, 0, sizeof(hash->table));
}
int Hash(int key) {
return key % INITSIZE;
}
void insert_hash(listhash* hash, int key) {
//参数检测：哈希不为空
assert(hash);
//1.定位哈希下标
int index = Hash(key);
//2.申请结点
Node* newNode = (Node*)malloc(sizeof(Node));
assert(newNode);
//3.设置新节点存储的键值
newNode->data = key;
//4.新节点指向原链表的头节点
newNode->next = hash->table[index];
//5.将新节点插入到哈希表的对应索引位置，成为新的头节点
hash->table[index] = newNode;
}
void Delete(listhash* hash, int key) {
assert(hash); // 确保传入的哈希表指针不为空
int index = Hash(key); // 计算键值的哈希值
Node* prev = NULL; // 用于跟踪当前节点的前一个节点
Node* curr = hash->table[index]; // 当前遍历的节点
while (curr != NULL) {
if (curr->data == key) { // 找到要删除的节点
if (prev == NULL) { // 如果是头节点
hash->table[index] = curr->next; // 更新头节点
} else {
prev->next = curr->next; // 更新前一个节点的next指针
}
free(curr); // 释放要删除的节点
return; // 删除完成后返回
}
prev = curr; // 更新前一个节点
curr = curr->next; // 继续遍历链表
}
}
void show(listhash* hash) {
assert(hash);
for (int i = 0; i < INITSIZE; i++) {
Node* temp = hash->table[i];
printf("table[%d]:", i);
while (temp != NULL) {
printf("%5d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
printf("-----------------------\n");
}
// 扩容哈希表
void rehash(listhash* oldHash) {
assert(oldHash); // 确保传入的哈希表指针不为空
listhash newHash; // 创建新的哈希表
init(&newHash); // 初始化新哈希表
int newSize = INITSIZE * REHASH_SIZE_MULTIPLIER; // 新哈希表的大小
for (int i = 0; i < INITSIZE; i++) { // 遍历旧哈希表的每个索引
Node* temp = oldHash->table[i]; // 当前索引对应的链表头节点
while (temp != NULL) { // 遍历链表
insert_hash(&newHash, temp->data); // 将元素重新插入到新哈希表
temp = temp->next; // 移动到下一个节点
}
}
*oldHash = newHash; // 将旧哈希表指针指向新哈希表
}
int main() {
listhash list;
init(&list);
// 插入一些元素
insert_hash(&list, 10);
insert_hash(&list, 30);
insert_hash(&list, 40);
insert_hash(&list, 12);
insert_hash(&list, 24);
insert_hash(&list, 25);
insert_hash(&list, 40);
insert_hash(&list, 20);
show(&list);
Delete(&list, 12);
Delete(&list, 40);
show(&list);
// 模拟扩容
rehash(&list);
show(&list);
return 0;
}
2. 开放地址法
（1）线性探测法
· 每一个槽位是一个单独的元素，当插入元素时，如果发生冲突，线性探测下一个空闲位置，直到全部插入为止
· 查找时，先找到对应的初始槽位，然后线性探测直接找到元素或空槽位
· 若插入数据已满，需要扩容：重新申请新大小，将原来的数组内容 依次遍历，重新哈希到数组中 (新申请之后排列不一定和原来数组顺序一样)
例如关键字集合为{5，6，8，10，14，19}，表长为6，则采用哈希函数 f(x)=x%6，前4个数没有发生冲突，可以直接存入，如下图所示：
当计算14%6 时发现 f(14)=14%6=2 ， 此时会与8发生冲突，于是线性探测下一个位置，则 f(14)=(f(14)+1)%6=3，此时无冲突，将14放入下标为 3 的位置 如下图所示：
代码如下：
#include <string.h>
#include <cassert>
#include <corecrt_malloc.h>
#include <stdio.h>
#define INITSIZE 10
typedef int ElemType;
//ReturnState 返回值状态
enum Status { False, True, Err, OutMem };
/*
不设置为整形的数组(整形用0做初始化 再放0不知道是初始化的还是放的)
设置为键值对(类似银行卡 每张卡有自己的属性 一个元素是一个结构体)
即键值对/结构体类型一维数组
*/
typedef struct KeyVal
{
ElemType key; //键：关键字 3 6 8 9
bool isused;//值：真假 T F
}KeyVal;
typedef struct Hash
{
size_t size; //关键字有效个数 4
size_t capacity; //数组容量 4
KeyVal hashtable[0];//柔性数组
}Hash, * Phash;
//初始化哈希结构--核心：每一个格子里isuse的属性 不关心值域--内存初始化memset
Status init_hash(Phash ph)
{
assert(ph != NULL); //debug调试版本下有效 醒目
if (ph == NULL) return Err;
ph->size = 0; //有效个数归0
ph->capacity = INITSIZE;
return True;
}
static int hash(Phash ph, ElemType key)
{
return key % ph->capacity; //返回数组长度
}
static void insert0(Phash ph, ElemType key)
{
//获取散列函数 -- 除留余数法
int index = hash(ph, key);//调用哈希函数传参 接受下标值
//判断该位置是否冲突
if (ph->hashtable[index].isused)
{
//该位置被占用 --- 线性探测法解决碰撞
//从当前位置开始找一圈找空闲位置存储该数值
int i = (index + 1) % ph->capacity;//从取余的位置开始走一圈
//不存在数组已满，必定至少会有一个空闲
//等于真 继续轮转
while (ph->hashtable[i].isused)
{
i = (i + 1) % ph->capacity;
}
index = i;//用i做更新
}
//index下标位置存放数据：更新 值+标记
ph->hashtable[index].key = key;
ph->hashtable[index].isused = true;
ph->size++;
}
//关键字插入 ------二级指针
Status insert_hash(Phash* pph, ElemType key)
{
assert(pph != NULL);
if (pph == NULL) return Err;
Phash ph = *pph; //为了不改动以下ph(本来应该改为pph)
int index;
//1.
// 判满 size==capacity需要扩容 重新哈希 申请新的大小 将原来的数据重新哈希的新数组中
if (ph->size == ph->capacity)
{
Hash* tmp = (Hash*)malloc(sizeof(Hash) + ph->capacity * 2 * sizeof(KeyVal)); //申请原来的2倍大小
tmp->size = 0;
//遍历原来的数组 将原来的数组内容重新哈希到数组中
for (int i = 0; i < ph->size; i++)
{
//index = hash(tmp,ph->hashtable[i].key);//将原来数值重新哈希新数组
insert0(tmp, ph->hashtable[i].key);
tmp->size++;
}
tmp->capacity = ph->capacity * 2;
//释放原来空间
free(ph);
*pph = tmp;
}
else //不需要扩容 直接插入
{
insert0(ph, key);
}
return True;
}
//关键字删除 把标记改成false
Status del_hash(Phash ph, ElemType key)
{
// 计算关键字的哈希值，得到数组索引
int index = hash(ph, key);
// 遍历哈希表，直到找到未使用的槽位或找到匹配的关键字
while (ph->hashtable[index].isused && ph->hashtable[index].key != key)
{
// 如果当前槽位被使用，但关键字不匹配，移动到下一个槽位
index = (index + 1) % ph->capacity;
}
// 如果找到了匹配的关键字
if (ph->hashtable[index].isused && ph->hashtable[index].key == key)
{
// 将该槽位标记为未使用
ph->hashtable[index].isused = false;
// 减少哈希表中有效关键字的数量
ph->size--;
// 返回True表示删除成功
return True;
}
// 如果没有找到匹配的关键字，返回False表示删除失败
return False;
}
//关键字查找
int search_hash(Phash ph, ElemType key) //通过hash函数定位下标 若该下标不是key 找一圈
{
// 计算关键字的哈希值，得到数组索引
int index = hash(ph, key);
// 遍历哈希表，直到找到未使用的槽位或找到匹配的关键字
while (ph->hashtable[index].isused)
{
// 如果当前槽位被使用，检查关键字是否匹配
if (ph->hashtable[index].key == key)
{
// 如果找到匹配的关键字，返回该槽位的索引
return index;
}
// 如果当前槽位的关键字不匹配，移动到下一个槽位
index = (index + 1) % ph->capacity;
}
// 如果遍历完成后没有找到匹配的关键字，返回-1
return -1; // 未找到返回-1
}
//显示哈希表信息
void Show(Phash ph)
{
printf("---------------show-----------------\n");
for (int i = 0; i < ph->capacity; i++)
{
if (ph->hashtable[i].isused == false)
{
printf("null ");
}
else
printf("%d ",ph->hashtable[i].key);
}
}
int main()
{
//柔性数组创建 8(size+capacity) + 数组大小
Hash* ph = (Hash*)malloc(sizeof(Hash)+INITSIZE*sizeof(KeyVal)); //结构体整体进行malloc
memset(ph->hashtable, 0, INITSIZE * sizeof(KeyVal));//对申请的内存进行初始化
init_hash(ph);
insert_hash(&ph, 2); // null null 2 3
insert_hash(&ph, 3);
insert_hash(&ph, 12); // null null 2 3 12
insert_hash(&ph, 0); //0 null 2 3 12
Show(ph);
free(ph);
ph = NULL; //不一定非要加这步 预防错误
return 0;
}
（2）二次探测法（再哈希法）
二次探测法是一种开放寻址法，当发生冲突时，它按照二次序列（12,22,32,…12,22,32,…）探测新的存储位置。具体步骤如下：
①当插入一个元素时，首先计算它的哈希值，得到一个初始位置。
②如果这个位置已经被占用，则按照二次序列（1, 4, 9, 16, ...）探测下一个位置。
③这个过程会一直持续，直到找到一个空位或者遍历完整个哈希表。
④如果遍历完整个哈希表都没有找到空位，则说明哈希表已满，需要进行扩容。
二次探测法的优点是解决了一次探测法中的聚集问题，即多个元素聚集在连续的位置，但它仍然可能面临更严重的聚集问题。
（3）双重哈希
双重哈希也是开放寻址法的一种，它使用两个哈希函数来确定元素的存储位置。具体步骤如下：
①当插入一个元素时，首先计算它的哈希值，得到一个初始位置。
②如果这个位置已经被占用，则使用第二个哈希函数计算一个步长，然后探测下一个位置：(hash1(key)+i⋅hash2(key))mod table_size(hash1(key)+i⋅hash2(key))modtable_size，其中 ii 是探测的次数。
③这个过程会一直持续，直到找到一个空位或者遍历完整个哈希表。
④双重哈希的优点是探测序列是随机的，减少了聚集的可能性。
双重哈希要求第二个哈希函数能够生成一个与第一个哈希函数不同的步长，以确保能够探测到整个哈希表。
四、哈希表的应用
-
数据库索引： 数据库通常使用哈希表来创建索引，这样可以快速地通过键值（如用户名或电子邮件地址）检索记录。
-
计数器： 在处理需要计数的数据时，哈希表可以用来存储和更新计数器，例如，统计网页上的点击量或单词在文本中的出现次数。
-
数据去重： 哈希表可以用来快速检查数据是否已经存在，从而实现数据去重。
-
密码学： 在密码学中，哈希表用于实现加密散列函数，用于数据完整性验证和数字签名。
-
游戏开发： 在游戏开发中，哈希表可以用来存储游戏对象的状态和属性。
-
实时数据处理： 在需要实时处理大量数据的系统中，如金融市场分析，哈希表可以用来快速更新和检索数据。
DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。
更多推荐
29
0- 0
已为社区贡献2条内容
所有评论(0)