模拟实现unordered_map

1.定义

unordered_map 是 C++ 标准库中的哈希表容器，特点是无序存储、平均 O (1) 时间复杂度的插入 / 查找 / 删除操作。其核心原理是通过哈希函数将关键字映射到哈希桶（bucket），再通过链表或红黑树处理哈希冲突。

2.实现原理

1. 哈希表（Hash Table）
  • 作用：存储键值对的底层数据结构，由哈希桶数组组成。
  • 结构：vector<Node*> 或 vector<list<Node>>，每个元素（桶）对应一个链表（处理哈希冲突）。
2. 哈希函数（Hash Function）
  • 作用：将关键字（Key）映射为哈希桶的索引（整数）。
  • 要求：
    • 输出范围需在哈希桶数组大小范围内（通过取模 % bucket_count 实现）。
    • 尽可能减少哈希冲突（不同 Key 映射到同一索引）。

 例子：

template <typename Key>
size_t HashFunc(const Key& key) {// 对整数直接取哈希return static_cast<size_t>(key);
}// 对字符串的哈希
template <>
size_t HashFunc(const std::string& key) {size_t hash = 0;for (char c : key) {hash = hash * 31 + c; // 31 是质数，减少冲突}return hash;
}

3. 哈希冲突（Hash Collision）
  • 问题：不同的 Key 通过哈希函数得到相同的桶索引。
  • 解决方式：
    • 链地址法（最常用）：每个桶对应一个链表，冲突的键值对依次插入链表。
    • 开放定址法：冲突时寻找下一个空桶（较少用于 unordered_map）。
4. 负载因子（Load Factor）
  • 定义：负载因子 = 元素个数 / 桶数量。
  • 作用：衡量哈希表的拥挤程度，超过阈值（通常为 1.0）时需要扩容。
  • 扩容机制：
    • 创建新的、更大的桶数组（通常为原大小的 2 倍，且为质数）。
    • 将所有元素重新哈希（rehash）到新桶中，避免哈希冲突加剧。
5. 键值对（Key-Value Pair）
  • 结构：存储关键字（Key）和值（Value）的节点，例如：
template <typename Key, typename Value>
struct Node {Key key;Value value;Node* next; // 指向链表中下一个节点（处理冲突）Node(const Key& k, const Value& v) : key(k), value(v), next(nullptr) {}
};

3.主要实现

1. 构造函数与析构函数

template <typename Key, typename Value>
class my_UnorderedMap {
private:std::vector<Node<Key, Value>*> buckets; // 哈希桶数组size_t size; // 当前元素个数size_t bucket_count; // 桶数量const float load_factor_threshold = 1.0f; // 负载因子阈值public:// 构造函数：初始化桶数量（默认 10 个桶）my_UnorderedMap(size_t init_buckets = 10) : bucket_count(init_buckets), size(0) {buckets.resize(bucket_count, nullptr);}// 析构函数：释放所有节点和桶~my_UnorderedMap() {for (auto bucket : buckets) {Node<Key, Value>* cur = bucket;while (cur) {Node<Key, Value>* next = cur->next;delete cur;cur = next;}}}
};

2.插入操作

bool my_insert(const Key& key, const Value& value) {// 检查是否需要扩容if (size * 1.0 / bucket_count >= load_factor_threshold) {rehash(bucket_count * 2); // 扩容为原大小的 2 倍}// 计算哈希索引size_t index = HashFunc(key) % bucket_count;// 检查 Key 是否已存在（不允许重复 Key）Node<Key, Value>* cur = buckets[index];while (cur) {if (cur->key == key) {return false; // Key 已存在，插入失败}cur = cur->next;}// 插入新节点（头插法）Node<Key, Value>* new_node = new Node<Key, Value>(key, value);new_node->next = buckets[index]; // 新节点指向原链表头buckets[index] = new_node; // 桶头指向新节点size++;return true;
}

 3.查找

Value* my_find(const Key& key) {size_t index = HashFunc(key) % bucket_count;Node<Key, Value>* cur = buckets[index];while (cur) {if (cur->key == key) {return &(cur->value); // 找到 Key，返回值的指针}cur = cur->next;}return nullptr; // 未找到
}

 4.删除

bool my_erase(const Key& key) {size_t index = HashFunc(key) % bucket_count;Node<Key, Value>* cur = buckets[index];Node<Key, Value>* prev = nullptr;while (cur) {if (cur->key == key) {// 移除节点if (prev == nullptr) {// 头节点删除buckets[index] = cur->next;} else {prev->next = cur->next;}delete cur;size--;return true;}prev = cur;cur = cur->next;}return false; // 未找到 Key
}

 5.扩容

void my_rehash(size_t new_bucket_count) {if (new_bucket_count <= bucket_count) return; // 新桶数量必须更大// 创建新桶数组std::vector<Node<Key, Value>*> new_buckets(new_bucket_count, nullptr);// 将旧桶中的元素重新哈希到新桶for (size_t i = 0; i < bucket_count; i++) {Node<Key, Value>* cur = buckets[i];while (cur) {Node<Key, Value>* next = cur->next; // 保存下一个节点// 计算新索引size_t new_index = HashFunc(cur->key) % new_bucket_count;// 插入新桶（头插法）cur->next = new_buckets[new_index];new_buckets[new_index] = cur;cur = next;}}// 替换旧桶数组buckets.swap(new_buckets);bucket_count = new_bucket_count;
}

6.移动复制和拷贝赋值

// 拷贝赋值运算符my_UnorderedMap& operator=(const UnorderedMap& other) {if (this != &other) {clear();bucket_count = other.bucket_count;load_factor_threshold = other.load_factor_threshold;hash_fn = other.hash_fn;equal_fn = other.equal_fn;buckets.resize(bucket_count, nullptr);for (size_t i = 0; i < other.bucket_count; ++i) {Node* current = other.buckets[i];while (current != nullptr) {insert(current->key, current->value);current = current->next;}}}return *this;}// 移动赋值运算符my_UnorderedMap& operator=(UnorderedMap&& other) noexcept {if (this != &other) {clear();buckets = std::move(other.buckets);element_count = other.element_count;bucket_count = other.bucket_count;load_factor_threshold = other.load_factor_threshold;hash_fn = std::move(other.hash_fn);equal_fn = std::move(other.equal_fn);other.element_count = 0;other.bucket_count = 0;}return *this;}

---完整代码；

#include <vector>
#include <cstddef>
#include <functional>
#include <stdexcept>template <typename Key, typename Value, typename Hash = std::hash<Key>, typename Equal = std::equal_to<Key>>
class my_UnorderedMap {
private:// 键值对节点结构struct Node {Key key;Value value;Node* next;Node(const Key& k, const Value& v) : key(k), value(v), next(nullptr) {}};std::vector<Node*> buckets;  // 哈希桶数组size_t element_count;        // 当前元素数量size_t bucket_count;         // 桶的数量float load_factor_threshold; // 负载因子阈值// 哈希函数包装器Hash hash_fn;// 相等比较器Equal equal_fn;// 检查是否为质数bool is_prime(size_t num) const {if (num <= 1) return false;if (num == 2) return true;if (num % 2 == 0) return false;for (size_t i = 3; i * i <= num; i += 2) {if (num % i == 0) return false;}return true;}// 获取下一个质数size_t next_prime(size_t num) const {if (num <= 2) return 2;size_t candidate = num;if (candidate % 2 == 0) ++candidate;while (!is_prime(candidate)) {candidate += 2;}return candidate;}// 重新哈希所有元素到新的桶数组void my_rehash(size_t new_bucket_count) {if (new_bucket_count <= bucket_count) return;std::vector<Node*> new_buckets(new_bucket_count, nullptr);// 将旧桶中的所有节点迁移到新桶for (size_t i = 0; i < bucket_count; ++i) {Node* current = buckets[i];while (current != nullptr) {Node* next = current->next;size_t new_index = hash_fn(current->key) % new_bucket_count;current->next = new_buckets[new_index];new_buckets[new_index] = current;current = next;}}// 交换新旧桶数组buckets.swap(new_buckets);bucket_count = new_bucket_count;}public:// 构造函数explicit my_UnorderedMap(size_t initial_buckets = 10, const Hash& hash = Hash(), const Equal& equal = Equal()): element_count(0), bucket_count(next_prime(initial_buckets)),load_factor_threshold(1.0f),hash_fn(hash),equal_fn(equal) {buckets.resize(bucket_count, nullptr);}// 析构函数~my_UnorderedMap() {clear();}// 拷贝构造函数my_UnorderedMap(const UnorderedMap& other): element_count(0), bucket_count(other.bucket_count),load_factor_threshold(other.load_factor_threshold),hash_fn(other.hash_fn),equal_fn(other.equal_fn) {buckets.resize(bucket_count, nullptr);for (size_t i = 0; i < other.bucket_count; ++i) {Node* current = other.buckets[i];while (current != nullptr) {insert(current->key, current->value);current = current->next;}}}// 移动构造函数my_UnorderedMap(UnorderedMap&& other) noexcept: buckets(std::move(other.buckets)),element_count(other.element_count),bucket_count(other.bucket_count),load_factor_threshold(other.load_factor_threshold),hash_fn(std::move(other.hash_fn)),equal_fn(std::move(other.equal_fn)) {other.element_count = 0;other.bucket_count = 0;}// 拷贝赋值运算符my_UnorderedMap& operator=(const UnorderedMap& other) {if (this != &other) {clear();bucket_count = other.bucket_count;load_factor_threshold = other.load_factor_threshold;hash_fn = other.hash_fn;equal_fn = other.equal_fn;buckets.resize(bucket_count, nullptr);for (size_t i = 0; i < other.bucket_count; ++i) {Node* current = other.buckets[i];while (current != nullptr) {insert(current->key, current->value);current = current->next;}}}return *this;}// 移动赋值运算符my_UnorderedMap& operator=(UnorderedMap&& other) noexcept {if (this != &other) {clear();buckets = std::move(other.buckets);element_count = other.element_count;bucket_count = other.bucket_count;load_factor_threshold = other.load_factor_threshold;hash_fn = std::move(other.hash_fn);equal_fn = std::move(other.equal_fn);other.element_count = 0;other.bucket_count = 0;}return *this;}// 插入元素bool my_insert(const Key& key, const Value& value) {// 检查负载因子，必要时扩容if (static_cast<float>(element_count) / bucket_count >= load_factor_threshold) {rehash(next_prime(bucket_count * 2));}size_t index = hash_fn(key) % bucket_count;Node* current = buckets[index];// 检查键是否已存在while (current != nullptr) {if (equal_fn(current->key, key)) {return false; // 键已存在，插入失败}current = current->next;}// 创建新节点并插入链表头部Node* new_node = new Node(key, value);new_node->next = buckets[index];buckets[index] = new_node;++element_count;return true;}// 查找元素Value* my_find(const Key& key) {size_t index = hash_fn(key) % bucket_count;Node* current = buckets[index];while (current != nullptr) {if (equal_fn(current->key, key)) {return &(current->value);}current = current->next;}return nullptr; // 未找到}// 查找元素（const 版本）const Value* my_find(const Key& key) const {size_t index = hash_fn(key) % bucket_count;Node* current = buckets[index];while (current != nullptr) {if (equal_fn(current->key, key)) {return &(current->value);}current = current->next;}return nullptr; // 未找到}// 重载[]运算符Value& operator[](const Key& key) {Value* value_ptr = find(key);if (value_ptr == nullptr) {// 键不存在，插入默认值insert(key, Value());value_ptr = find(key);}return *value_ptr;}// 删除元素bool my_erase(const Key& key) {size_t index = hash_fn(key) % bucket_count;Node* current = buckets[index];Node* previous = nullptr;while (current != nullptr) {if (equal_fn(current->key, key)) {if (previous == nullptr) {// 删除头节点buckets[index] = current->next;} else {previous->next = current->next;}delete current;--element_count;return true;}previous = current;current = current->next;}return false; // 未找到键}// 获取元素数量size_t size() const {return element_count;}// 检查是否为空bool my_empty() const {return element_count == 0;}// 清空容器void clear() {for (size_t i = 0; i < bucket_count; ++i) {Node* current = buckets[i];while (current != nullptr) {Node* next = current->next;delete current;current = next;}buckets[i] = nullptr;}element_count = 0;}// 获取负载因子float load_factor() const {return static_cast<float>(element_count) / bucket_count;}// 获取负载因子阈值float max_load_factor() const {return load_factor_threshold;}// 设置负载因子阈值void max_load_factor(float new_threshold) {if (new_threshold > 0) {load_factor_threshold = new_threshold;}}// 调整桶的数量void reserve(size_t count) {size_t new_bucket_count = next_prime(count);if (new_bucket_count > bucket_count) {rehash(new_bucket_count);}}// 迭代器类class Iterator {private:Node* current;const std::vector<Node*>* buckets;size_t bucket_index;size_t bucket_count;// 移动到下一个非空桶void move_to_next_bucket() {while (current == nullptr && bucket_index < bucket_count) {++bucket_index;if (bucket_index < bucket_count) {current = (*buckets)[bucket_index];}}}public:Iterator(Node* node, const std::vector<Node*>* b, size_t index, size_t count): current(node), buckets(b), bucket_index(index), bucket_count(count) {if (current == nullptr) {move_to_next_bucket();}}Iterator& operator++() {if (current != nullptr) {current = current->next;if (current == nullptr) {++bucket_index;move_to_next_bucket();}}return *this;}bool operator==(const Iterator& other) const {return current == other.current;}bool operator!=(const Iterator& other) const {return !(*this == other);}std::pair<const Key&, Value&> operator*() const {return {current->key, current->value};}std::pair<const Key&, Value&>* operator->() const {// 这里简化实现，实际需要返回一个代理对象throw std::runtime_error("Arrow operator not fully implemented");}};// 迭代器接口Iterator begin() const {if (empty()) {return end();}return Iterator(buckets[0], &buckets, 0, bucket_count);}Iterator end() const {return Iterator(nullptr, &buckets, bucket_count, bucket_count);}
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/bicheng/88590.shtml
繁体地址，请注明出处：http://hk.pswp.cn/bicheng/88590.shtml

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

史上最详细Java并发多线程（面试必备，一篇足矣）

史上最详细Java并发多线程（面试必备，一篇足矣）

第一章&#xff1a;线程基础 1.1 线程与进程 进程&#xff1a;系统资源分配的基本单位&#xff0c;拥有独立的内存空间 线程&#xff1a;CPU调度的基本单位&#xff0c;共享进程内存空间 关系&#xff1a;一个进程可包含多个线程&#xff0c;线程切换成本远低于进程 1.2 线程的…
阅读更多...
【DataFlow】数据合成流水线工具

【DataFlow】数据合成流水线工具

1.整体解读 核心思想&#xff1a;以数据为中心的AI&#xff08;Data-Centric AI&#xff09; DataFlow 的核心目标是通过一系列自动化“流水线”&#xff08;Pipelines&#xff09;来处理和生成高质量的数据&#xff0c;从而提升大语言模型&#xff08;LLM&#xff09;在特定领…
阅读更多...
Hangfire 调用报错解决方案总结

Hangfire 调用报错解决方案总结

System.ArgumentNullException: 值不能为 null 错误在使用 Hangfire 时确实是一个常见问题&#xff0c;特别是在配置 Hangfire 服务器时。问题分析这个错误通常发生在以下情况&#xff1a;没有正确配置 Hangfire 服务器队列配置缺失或不正确连接字符串配置问题解决方案要点正确…
阅读更多...
MySQL的使用

MySQL的使用

MySQL的使用一、mysql中的周边命令1. 检查版本2. 查看字符集3. 查看客户端连接4. 查看最后一条警告消息二、数据库、数据表的管理1. 语法规则2. 数据库2.1 查看数据库2.2 创建数据库2.3 选择数据库2.4 查看创建数据库命令2.5 创建库时添加字符集2.6 修改数据库字符集2.7 删除数…
阅读更多...
2025Nginx最新版讲解/面试

2025Nginx最新版讲解/面试

维护系统多服务器部署&#xff0c;将我们请求代理到各个服务器。代理正向代理&#xff0c;代理对象是我们的客户端&#xff0c;目标对象不知道我们用户。VPN就是典型的正向代理。反向代理&#xff0c;代理对象是服务端&#xff0c;用户不知道服务端具体信息。而这正是Nginx所做…
阅读更多...
JAVASCRIPT 前端数据库-V8--仙盟数据库架构-—-—仙盟创梦IDE

JAVASCRIPT 前端数据库-V8--仙盟数据库架构-—-—仙盟创梦IDE

老版本 在v1 版本中我们讲述了 基础版的应用 JAVASCRIPT 前端数据库-V1--仙盟数据库架构-—-—仙盟创梦IDE-CSDN博客 接下载我们做一个更复杂的的其他场景 由于&#xff0c;V1查询字段必须 id 接下来我们修改了了代码 JAVASCRIPT 前端数据库-V2--仙盟数据库架构-—-—仙盟创…
阅读更多...
UNIX 域套接字实现本地进程间通信

UNIX 域套接字实现本地进程间通信

&#x1f680; 使用 UNIX 域套接字 (AF_UNIX) 实现高效进程通信 在 Linux 和其他类 UNIX 系统中&#xff0c;进程间通信 (IPC) 的方法有很多种&#xff0c;例如管道、消息队列、共享内存等。然而&#xff0c;当你的应用程序需要在 同一台机器上的不同进程间进行高效、低延迟的数…
阅读更多...
【Axure教程】中继器间图片的传递

【Axure教程】中继器间图片的传递

中继器在Axure中可以作为图片保存的数据库&#xff0c;在实际系统中&#xff0c;我们经常需要将选择数据库的图片添加到其他图片列表中&#xff0c;所以今天就教大家&#xff0c;怎么在Axure中实现中继器之间的图片传递&#xff0c;包含将一个中继器中的图片列表传递到另一个中…
阅读更多...
专题：2025云计算与AI技术研究趋势报告|附200+份报告PDF、原数据表汇总下载

专题：2025云计算与AI技术研究趋势报告|附200+份报告PDF、原数据表汇总下载

原文链接&#xff1a;https://tecdat.cn/?p42935 关键词&#xff1a;2025, 云计算&#xff0c;AI 技术&#xff0c;市场趋势&#xff0c;深度学习&#xff0c;公有云&#xff0c;研究报告 云计算和 AI 技术正以肉眼可见的速度重塑商业世界。过去十年&#xff0c;全球云服务收…
阅读更多...
从代码学习深度强化学习 - PPO PyTorch版

从代码学习深度强化学习 - PPO PyTorch版

文章目录 前言PPO 算法简介从 TRPO 到 PPOPPO 的两种形式：惩罚与截断代码实践：PPO 解决离散动作空间问题 (CartPole)环境与工具函数定义策略与价值网络PPO 智能体核心实现训练与结果代码实践：PPO 解决连续动作空间问题 (Pendulum)环境准备适用于连续动作的网络PPO 智能体 (连…
阅读更多...
PortsWiggerLab: Blind OS command injection with output redirection

PortsWiggerLab: Blind OS command injection with output redirection

实验目的This lab contains a blind OS command injection vulnerability in the feedback function.The application executes a shell command containing the user-supplied details. The output from the command is not returned in the response. However, you can use o…
阅读更多...
星云穿越与超光速飞行特效的前端实现原理与实践

星云穿越与超光速飞行特效的前端实现原理与实践

文章目录 1，引言2，特效设计思路3，技术原理解析1. 星点的三维分布2. 视角推进与星点运动3. 三维到二维的投影4. 星点的视觉表现5. 色彩与模糊处理4，关键实现流程图5，应用场景与优化建议6，总结1，引言 在现代网页开发中，炫酷的视觉特效不仅能提升用户体验，还能为产品增添…
阅读更多...
【Linux】C++项目分层架构：核心三层与关键辅助

【Linux】C++项目分层架构：核心三层与关键辅助

C 项目分层架构全指南&#xff1a;核心三层 关键辅助一、核心三层架构 传统的三层架构&#xff08;或三层体系结构&#xff09;是构建健壮系统的基石&#xff0c;包括以下三层&#xff1a; 1. 表现层&#xff08;Presentation Layer&#xff09; 负责展示和输入处理&#xff0…
阅读更多...
【机器学习】保序回归平滑校准算法

【机器学习】保序回归平滑校准算法

保序回归平滑校准算法&#xff08;SIR&#xff09;通过分桶合并线性插值解决广告预估偏差问题&#xff0c;核心是保持原始排序下纠偏。具体步骤&#xff1a;1&#xff09;按预估分升序分桶&#xff0c;统计每个分桶的后验CTR&#xff1b;2&#xff09;合并逆序桶重新计算均值&a…
阅读更多...
项目开发日记

项目开发日记

框架整理学习UIMgr&#xff1a;一、数据结构与算法 1.1 关键数据结构成员变量类型说明m_CtrlsList<PageInfo>当前正在显示的所有 UI 页面m_CachesList<PageInfo>已打开过、但现在不显示的页面&#xff08;缓存池&#xff09; 1.2 算法逻辑查找缓存页面&#xff1a;…
阅读更多...
60 美元玩转 Li-Fi —— 开源 OpenVLC 平台入门（附 BeagleBone Black 驱动简单解析）

60 美元玩转 Li-Fi —— 开源 OpenVLC 平台入门（附 BeagleBone Black 驱动简单解析）

60 美元玩转 Li-Fi —— 开源 OpenVLC 平台入门&#xff08;附 BeagleBone Black 及驱动解析&#xff09;一、什么是 OpenVLC&#xff1f; OpenVLC 是由西班牙 IMDEA Networks 研究所推出的开源可见光通信&#xff08;VLC / Li-Fi&#xff09;研究平台。它把硬件、驱动、协议栈…
阅读更多...
Python性能优化

Python性能优化

Python 以其简洁和易用性著称，但在某些计算密集型或大数据处理场景下，性能可能成为瓶颈。幸运的是，通过一些巧妙的编程技巧，我们可以显著提升Python代码的执行效率。本文将介绍8个实用的性能优化技巧，帮助你编写更快、更高效的Python代码。 　　一、优化前的黄金法则：先测…
阅读更多...
easyui碰到想要去除顶部栏按钮边框

easyui碰到想要去除顶部栏按钮边框

只需要加上 plain"true"<a href"javascript:void(0)" class"easyui-linkbutton" iconCls"icon-add" plain"true"onclick"newCheck()">新增</a>
阅读更多...
C++字符串详解：原理、操作及力扣算法实战

C++字符串详解：原理、操作及力扣算法实战

一、C字符串简介在C中&#xff0c;字符串的处理方式主要有两种&#xff1a;字符数组&#xff08;C风格字符串&#xff09;和std::string类。虽然字符数组是C语言遗留的底层实现方式&#xff0c;但现代C更推荐使用std::string类&#xff0c;其封装了复杂的操作逻辑&#xff0c;提…
阅读更多...
CMU15445-2024fall-project1踩坑经历

CMU15445-2024fall-project1踩坑经历

p1目录&#xff1a;lRU\_K替换策略LRULRU\_K大体思路SetEvictableRecordAccessSizeEvictRemoveDisk SchedulerBufferPoolNewPageDeletePageFlashPage/FlashAllPageCheckReadPage/CheckWritePagePageGuard并发设计主逻辑感谢CMU的教授们给我们分享了如此精彩的一门课程&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023