当前位置： 首页 > news >正文

数据结构：闭散列 (Closed Hashing)-开放定址法 (Open Addressing)

news 2025/9/3 12:19:16

目录

根本思想的转变

如何标记房间状态？

结构设计与代码框架

线性探测 (Linear Probing)

逐步完善代码：insert 和 search

二次探测 (Quadratic Probing)

逐步完善代码：insert 和 search

双重哈希 (Double Hashing)

逐步完善代码：insert 和 search

完整代码示例

我们深入探讨另一种解决哈希冲突的哲学：闭散列 (Closed Hashing)，它更广为人知的名字是 开放定址法 (Open Addressing)。

这个名字听起来有点矛盾，“Closed Hashing” 又叫 “Open Addressing”？

  • 闭散列 (Closed Hashing)：这个名字强调的是“数据必须留在哈希表数组内部，是封闭的”，不能像拉链法那样“外出”到外部的链表结构中。

  • 开放定址法 (Open Addressing)：这个名字强调的是“地址是开放的”。如果我的目标地址被占了，我可以去寻找其他开放的、可用的地址。

这两个名字说的是同一件事的两个方面。

根本思想的转变

我们先回顾一下拉链法(Separate Chaining)的本质：

当 hashTable[i] 这个“房间”发生冲突时，我们在房间门口挂一个链条，把所有冲突的人都挂在这个链条上。这是一种“纵向扩展”的思路。

而开放定址法的哲学完全不同。它的核心原则是：

所有元素都必须存放在哈希表这个数组内，绝不外挂任何额外的数据结构。

那么，当 hashTable[i] 这个房间有人时，新来的人怎么办？ 唯一的选择是：

去数组里的其他房间找一个空位住下。

这个“寻找下一个空位”的过程，就叫做 探测 (Probing)。根据寻找策略的不同，就衍生出了几种不同的探测方法。

开放定址法的本质，是将冲突解决方式从“在冲突位置进行纵向扩展（链表）”，转变为“在哈希表内部进行横向移动，寻找下一个可用空间”。

如何标记房间状态？

在拉链法中，一个位置 hashTable[i] 要么是 NULL（空），要么是一个指向链表的指针。但在开放定址法中，数组里存放的是真实的数据项。这就带来一个新问题：

📍想象一个场景：

  • 张三哈希到位置 5，住下。

  • 李四也哈希到位置 5，发生冲突。他向后探测，住到了空闲的位置 6。

  • 现在，我们把张三（位置 5 的元素）删除了。如果只是简单地把位置 5 标记为“空”，会发生什么？

  • 此时我们去查找李四。计算哈希值得到 5，发现位置 5 是“空”的。程序会认为“既然初始位置是空的，那李四肯定不存在”，于是返回查找失败。但这显然是错的！

为了解决这个问题，每个槽位(slot)必须有三种状态：

  • EMPTY：此位置为空，从未被占用过。查找时遇到它，表示查找失败。

  • OCCUPIED：此位置已被占用。

  • DELETED：此位置曾经被占用，但现在已删除。我们叫它“墓碑(tombstone)”。查找时遇到它，不能停，必须继续探测；但插入时遇到它，可以把它当作空位来使用。

结构设计与代码框架

第一步：定义数据项和状态

我们需要一个结构体来表示哈希表中的每个槽位，这个结构体必须包含数据和状态。

#include <iostream>
#include <string.h>// 使用枚举类型来清晰地表示三种状态
enum State { EMPTY, OCCUPIED, DELETED };// 哈希表中的数据项
struct DataItem {int id;char name[50];State state; // 每个槽位都有自己的状态
};

第二步：定义哈希表并初始化

哈希表就是一个 DataItem 的数组。初始化时，我们需要把所有槽位的状态都设置为 EMPTY。

const int TABLE_SIZE = 11; // 同样，最好是素数// 哈希表本体
DataItem hashTable[TABLE_SIZE];// 哈希函数
int hash_function(int key) {return key % TABLE_SIZE;
}// 初始化哈希表
void init_hash_table() {for (int i = 0; i < TABLE_SIZE; ++i) {hashTable[i].state = EMPTY;hashTable[i].id = -1; // 初始化 id 为一个无效值}
}

好了，我们的舞台已经搭好。接下来，不同的探测方法，就是在这个舞台上表演的不同“走位”策略。

线性探测 (Linear Probing)

这是最直观、最简单的探测思想。

推导过程： 如果 hash(key) 计算出的位置 p 被占用了，怎么办？

最简单的想法：看看下一个位置 p+1 行不行？

如果 p+1 还被占用，就看 p+2... 以此类推，直到找到一个空位。如果到了数组末尾，就绕回到数组开头继续找。

👉这个探测序列就是：p, p + 1, p + 2, p + 3, ...

用公式表达就是： probe_index = (hash(key) + i) % TABLE_SIZE，其中 i 是探测次数（从 0 开始）。

逐步完善代码：insert 和 search

插入 (Insert)：

// 插入（线性探测）
void insert_linear(int id, const char* name) {int index = hash_function(id);int i = 0;// 循环探测while (i < TABLE_SIZE) {int probe_index = (index + i) % TABLE_SIZE;// 找到了一个可以插入的位置（空的或已删除的）if (hashTable[probe_index].state != OCCUPIED) {hashTable[probe_index].id = id;strcpy(hashTable[probe_index].name, name);hashTable[probe_index].state = OCCUPIED;std::cout << "ID " << id << " 插入到位置 " << probe_index << std::endl;return;}// 如果此位置已被占用，继续下一次探测i++;}// 如果循环走完还没找到位置，说明表满了std::cout << "哈希表已满，无法插入！" << std::endl;
}

查找 (Search)：

// 查找（线性探测）
DataItem* search_linear(int id) {int index = hash_function(id);int i = 0;while (i < TABLE_SIZE) {int probe_index = (index + i) % TABLE_SIZE;// 如果遇到 EMPTY，说明要找的元素肯定不存在if (hashTable[probe_index].state == EMPTY) {return NULL;}// 如果遇到 OCCUPIED，需要比对 idif (hashTable[probe_index].state == OCCUPIED && hashTable[probe_index].id == id) {// 找到了！return &hashTable[probe_index];}// 如果是 DELETED 或者 id 不匹配，都继续探测i++;}// 探测了一整圈都没找到return NULL;
}

线性探测的致命弱点：一次聚集 (Primary Clustering)

当多个哈希值相近的元素被插入时，它们会形成连续的“区块”。后来的元素，一旦哈希到这个区块中的任何一个位置，就必须一直探测到区块的末尾才能插入。

这导致这个区块越来越长，查找和插入的效率急剧下降，这就是“聚集”问题。

二次探测 (Quadratic Probing)

 线性探测的问题在于，每次探测的步长都是固定的 +1。如何避免元素“抱团”？

一个自然的想法是：让探测的步子迈得大一点，而且越来越大。

二次探测就是这样一个策略。它的探测序列是：p, p+1^2, p+2^2, p+3^2, ... 即 p, p+1, p+4, p+9, ...

📌用公式表达就是： probe_index = (hash(key) + i*i) % TABLE_SIZE

这个方法可以有效地打散线性探测造成的“一次聚集”。

逐步完善代码：insert 和 search

代码结构和线性探测几乎完全一样，我们只需要修改计算 probe_index 的那一行。

// 插入（二次探测）
void insert_quadratic(int id, const char* name) {int index = hash_function(id);int i = 0;while (i < TABLE_SIZE) {// 唯一的区别在这里：探测步长是 i*iint probe_index = (index + i * i) % TABLE_SIZE;if (hashTable[probe_index].state != OCCUPIED) {hashTable[probe_index].id = id;strcpy(hashTable[probe_index].name, name);hashTable[probe_index].state = OCCUPIED;std::cout << "ID " << id << " 插入到位置 " << probe_index << " (经过 " << i << " 次探测)" << std::endl;return;}i++;}std::cout << "哈希表已满，无法插入！" << std::endl;
}// 查找（二次探测）
DataItem* search_quadratic(int id) {int index = hash_function(id);int i = 0;while (i < TABLE_SIZE) {// 唯一的区别在这里int probe_index = (index + i * i) % TABLE_SIZE;if (hashTable[probe_index].state == EMPTY) {return NULL;}if (hashTable[probe_index].state == OCCUPIED && hashTable[probe_index].id == id) {return &hashTable[probe_index];}i++;}return NULL;
}

二次探测的弱点：二次聚集 (Secondary Clustering)

虽然它解决了“一次聚集”，但它引入了新问题。

如果两个不同的 Key (k1, k2) 经过主哈希函数后得到相同的地址（hash(k1) == hash(k2)），那么它们后续的整个探测序列 (p+1, p+4, p+9, ...) 将会是一模一样的。

它们仍然在争夺同一批槽位，只是争夺的模式不同了。

双重哈希 (Double Hashing)

推导过程： 二次聚集的根源是：探测序列的“模式”是固定的（+i*i），与 Key 本身无关。

那么，终极解决方案就是：让每个 Key 的探测步长，由它自己来决定！

探测序列就变成了：p, p + 1·step, p + 2·step, p + 3·step, ...

✅用公式表达就是： probe_index = (hash1(key) + i * hash2(key)) % TABLE_SIZE

我们需要第二个哈希函数 hash2() 来专门计算这个“步长”。

📍hash2() 的设计要求：

  1. 绝不能返回 0。否则步长为 0，探测将卡在原地。

  2. 返回值应与 TABLE_SIZE 互质。这样才能保证探测序列能走遍整个哈希表。

一个常见的、简单的设计是： hash2(key) = R - (key % R)，其中 R 是一个小于 TABLE_SIZE 的素数。

逐步完善代码：insert 和 search

我们先定义第二个哈希函数。

// 选择一个小于 TABLE_SIZE 的素数
const int R = 7; int hash2(int key) {return R - (key % R);
}

然后，我们再次修改 insert 和 search 中的 probe_index 计算方法。

// 插入（双重哈希）
void insert_double(int id, const char* name) {int index1 = hash_function(id); // 主哈希int step = hash2(id);          // 第二个哈希函数计算步长int i = 0;while (i < TABLE_SIZE) {// 探测步长由 hash2 决定int probe_index = (index1 + i * step) % TABLE_SIZE;if (hashTable[probe_index].state != OCCUPIED) {hashTable[probe_index].id = id;strcpy(hashTable[probe_index].name, name);hashTable[probe_index].state = OCCUPIED;std::cout << "ID " << id << " 插入到位置 " << probe_index << " (步长 " << step << ")" << std::endl;return;}i++;}std::cout << "哈希表已满，无法插入！" << std::endl;
}// 查找（双重哈希）
DataItem* search_double(int id) {int index1 = hash_function(id);int step = hash2(id);int i = 0;while (i < TABLE_SIZE) {int probe_index = (index1 + i * step) % TABLE_SIZE;if (hashTable[probe_index].state == EMPTY) {return NULL;}if (hashTable[probe_index].state == OCCUPIED && hashTable[probe_index].id == id) {return &hashTable[probe_index];}i++;}return NULL;
}

双重哈希是开放定址法中性能最好、分布最均匀的方法，因为它极大地减少了各种聚集问题。

完整代码示例

下面是使用双重哈希的完整、可运行的代码，因为它是在开放定址法中综合性能最好的。

#include <iostream>
#include <string.h>// 1. 定义状态和数据项
enum State { EMPTY, OCCUPIED, DELETED };struct DataItem {int id;char name[50];State state;
};// 2. 定义哈希表和相关常量
const int TABLE_SIZE = 11;
const int R = 7; // 用于第二个哈希函数的素数DataItem hashTable[TABLE_SIZE];// 3. 实现哈希函数
// 主哈希函数
int hash1(int key) {return key % TABLE_SIZE;
}// 第二个哈希函数，用于计算步长
int hash2(int key) {return R - (key % R);
}// 4. 实现核心操作
// 初始化
void init_hash_table() {for (int i = 0; i < TABLE_SIZE; ++i) {hashTable[i].state = EMPTY;hashTable[i].id = -1;}
}// 插入（双重哈希）
void insert(int id, const char* name) {int index1 = hash1(id);int step = hash2(id);int i = 0;while (i < TABLE_SIZE) {int probe_index = (index1 + i * step) % TABLE_SIZE;if (hashTable[probe_index].state != OCCUPIED) {hashTable[probe_index].id = id;strcpy(hashTable[probe_index].name, name);hashTable[probe_index].state = OCCUPIED;std::cout << "插入成功: ID " << id << " (" << name << ") at index " << probe_index << std::endl;return;}i++;}std::cout << "错误: 哈希表已满，无法插入 " << id << std::endl;
}// 查找（双重哈希）
DataItem* search(int id) {int index1 = hash1(id);int step = hash2(id);int i = 0;while (i < TABLE_SIZE) {int probe_index = (index1 + i * step) % TABLE_SIZE;if (hashTable[probe_index].state == EMPTY) {return NULL; // 遇到空，说明不存在}if (hashTable[probe_index].state == OCCUPIED && hashTable[probe_index].id == id) {return &hashTable[probe_index]; // 找到了}// 遇到 DELETED 或者 id 不匹配，继续探测i++;}return NULL; // 找了一圈，不存在
}// 删除操作
void remove(int id) {DataItem* item = search(id);if (item != NULL) {item->state = DELETED;std::cout << "删除成功: ID " << id << std::endl;} else {std::cout << "删除失败: 未找到 ID " << id << std::endl;}
}// 打印哈希表状态，用于调试
void print_table() {std::cout << "------ 哈希表状态 ------" << std::endl;for (int i = 0; i < TABLE_SIZE; ++i) {std::cout << "Index " << i << ": ";if (hashTable[i].state == EMPTY) {std::cout << "--- EMPTY ---" << std::endl;} else if (hashTable[i].state == DELETED) {std::cout << "--- DELETED ---" << std::endl;} else {std::cout << "ID=" << hashTable[i].id << ", Name=" << hashTable[i].name << std::endl;}}std::cout << "-------------------------" << std::endl;
}// 5. 主函数测试
int main() {init_hash_table();// 插入数据，故意制造冲突// 5, 16, 27 都会哈希到 5insert(5, "Alice");insert(16, "Bob");   // 冲突insert(27, "Charlie"); // 再次冲突insert(8, "David");insert(19, "Eve");   // 19 % 11 = 8, 与 David 冲突print_table();// 查找测试int ids_to_find[] = {16, 8, 99};for (int id : ids_to_find) {DataItem* result = search(id);if (result) {std::cout << "查找成功: ID=" << result->id << ", Name=" << result->name << std::endl;} else {std::cout << "查找失败: 未找到 ID=" << id << std::endl;}}// 删除和之后再查找的测试remove(16); // 删除 Bobprint_table();std::cout << "删除 Bob(16) 后再次查找 Charlie(27)..." << std::endl;DataItem* charlie = search(27);if (charlie) {std::cout << "查找成功: ID=" << charlie->id << ", Name=" << charlie->name << std::endl;} else {std::cout << "查找失败: 未找到 ID=27" << std::endl;}return 0;
}

http://www.xdnf.cn/news/1435123.html

相关文章：

  • react用useImages读取图片,方便backgroundImage
  • hikvision海康威视sdk调用失败，code为29解决办法
  • 集采与反腐双重压力下，医药销售的破局之道：从资源依赖到价值重构
  • 从结构化到多模态：RAG文档解析工具选型全指南
  • Portainer：Docker可视化管理神器部署与使用攻略
  • 不只是一台玩具车：开源燃料电池机器人HydroBot全揭秘
  • 怎么用redis lua脚本实现各分布式锁？Redisson各分布式锁怎么实现的？
  • Unity通过Object学习原型模式
  • ES6和CommonJS模块区别
  • GNU Make | C/C++项目自动构建入门
  • DevOps运维与开发一体化及Kubernetes运维核心详解
  • Aurobay EDI 需求分析：OFTP2 与 EDIFACT 驱动的汽车供应链数字化
  • DataAgent技术解析：数据智能的未来之路
  • LangGraph 上下文工程权威指南：构建智能、感知、有记忆的 AI 代理
  • Ubuntu平台查看.gz格式压缩文件内容以及利用grep命令过滤搜索内容
  • 《浪浪山小妖怪》知识竞赛来袭！测测你是几级影迷？
  • RL【1】：Basic Concepts
  • 情况三：已经 add ，并且也 commit 了
  • 机器人控制器开发(整体架构2 Lerobot介绍)
  • 佛山体彩第二届唱享之夜浪漫收官， 七夕音乐派对全场大合唱！
  • 使用 Gulp + Webpack 打造一个完整的 TypeScript 库构建流程
  • 社区医疗健康管理系统的设计与实现-（源码+LW+可部署）
  • Linux92 shell:倒计时，用户分类
  • [re_2] rpc|http|nginx|protobuf|
  • HBuilder X 4.76 开发微信小程序集成 uview-plus
  • 【Linux我做主】进程退出和终止详解
  • C++编程语言：标准库：第37章——正则表达式(Bjarne Stroustrup)
  • 拷打字节面试官之-吃透c语言-哈希算法 如何在3面拷打字节cto 3万行算法源码带你吃透算法面试所有考题
  • 【完整源码+数据集+部署教程】鸡粪病害检测系统源码和数据集：改进yolo11-bifpn-SDI
  • 前端开发中经常提到的iframe、DOM是什么?