深圳网站空间购买,宿松网站建设,自己网站上放个域名查询,网站 编码文档文章目录 前言#x1f4d4;一、unordered系列关联式容器#x1f4d5;1.1 unordered 容器概述#x1f4d5;1.2 哈希表在 unordered 容器中的实现原理#x1f4d5;1.3 unordered 容器的特点 #x1f4d4;二、unordered_set 和 unordered_map 的基本操作#x1f4d5;2.1 un… 文章目录 前言一、unordered系列关联式容器1.1 unordered 容器概述1.2 哈希表在 unordered 容器中的实现原理1.3 unordered 容器的特点 二、unordered_set 和 unordered_map 的基本操作2.1 unordered_set 的基本用法1. 创建和初始化2. 插入元素3. 查找元素4. 删除元素5. 大小和清空 2.2 unordered_map 的基本用法1. 创建和初始化2. 插入元素3. 查找元素4. 删除元素5. 大小和清空 三、哈希表3.1 哈希表的基本原理3.2 哈希函数3.3 解决冲突的几种办法1. 开放地址法Open Addressinga. 线性探测Linear Probingb. 二次探测Quadratic Probingc. 双重哈希Double Hashing 2. 拉链法Chaining 四、哈希表的模拟实现4.1 开放地址法线性探测1. DefaultHashFunc 哈希函数类2. HashData 类3. HashTable 类4. 私有成员 ️总结4.2 拉链法哈希桶1. HashNode 类2. HashTable 类成员变量构造函数和析构函数插入操作 Insert查找操作 Find删除操作 Erase打印操作 Print ️总结 结语 前言
在C的世界中哈希表是一种高效、独特的数据结构被广泛应用于需要快速查找、插入、删除的场景。通过哈希函数将数据映射到表中它不仅提高了操作效率还在解决冲突时展现了精巧的设计。哈希表在算法的应用中尤为重要无论是缓存、字典处理还是集合操作都离不开它的身影。本篇博客将带你一步步深入理解哈希表的实现原理及其应用让你在编码之路上更上一层楼。 一、unordered系列关联式容器
在 C 标准库中unordered 系列容器如 unordered_map 和 unordered_set是一类基于哈希表实现的关联式容器。与传统的 map 和 set 容器不同unordered 容器通过哈希函数实现了无序存储能够在均摊 O ( 1 ) O(1) O(1) 时间复杂度内完成插入、查找和删除操作。这使得 unordered 系列容器在处理需要快速查找的场景中非常高效。
1.1 unordered 容器概述
unordered 容器包含以下几种类型主要用于不同类型的键值对或集合操作
unordered_set一个不包含重复元素的集合存储的是唯一的键。unordered_multiset与 unordered_set 相似但允许包含重复元素。unordered_map一个键值对的容器每个键只能出现一次键是唯一的。unordered_multimap一个键值对的容器允许键重复。
与传统的有序容器如 map 和 set不同unordered 容器中的元素没有特定的顺序。因此unordered_map 和 unordered_set 更加适用于不关心元素顺序、仅关注快速访问的场景。
1.2 哈希表在 unordered 容器中的实现原理
unordered 容器的核心数据结构是哈希表它利用哈希函数将键映射到表中的位置。在哈希表中unordered 容器采用了一种**桶bucket**的机制来存储数据
哈希函数将键值映射到特定的哈希值这个哈希值会决定键值对存储的位置即桶。桶哈希表中的每个位置称为一个桶键值对根据哈希值分布在不同的桶中。冲突处理当多个键映射到同一个桶时使用链表或其他方法来解决冲突。这种冲突解决方法通常称为拉链法。
1.3 unordered 容器的特点
均摊时间复杂度在理想的情况下插入、查找和删除的平均时间复杂度为 O ( 1 ) O(1) O(1)。无序性unordered 容器不维护元素的顺序元素顺序与插入顺序无关。哈希函数与相等比较器可以指定自定义的哈希函数和比较器适用于自定义类型和不同的哈希策略。
二、unordered_set 和 unordered_map 的基本操作
2.1 unordered_set 的基本用法
unordered_set 是一个集合用于存储唯一的元素元素的顺序是无序的。主要用在需要快速查找元素的场景中。
1. 创建和初始化
#include unordered_set
#include iostreamint main() {std::unordered_setint uset {1, 2, 3, 4, 5}; // 初始化// 遍历输出元素for (const int num : uset) {std::cout num ;}std::cout std::endl;return 0;
}2. 插入元素
使用 insert 方法插入元素。如果元素已存在insert 不会插入重复元素。
uset.insert(6); // 插入元素6
uset.insert(3); // 3已存在不插入3. 查找元素
使用 find 方法查找元素若找到则返回元素的迭代器否则返回 end()。
if (uset.find(3) ! uset.end()) {std::cout 3 存在于集合中 std::endl;
}4. 删除元素
使用 erase 方法删除指定元素可以传入元素值或迭代器。
uset.erase(4); // 删除元素45. 大小和清空
size() 获取集合的大小。clear() 清空集合中的所有元素。
std::cout 集合大小: uset.size() std::endl;
uset.clear();2.2 unordered_map 的基本用法
unordered_map 是一种键值对关联容器使用哈希表实现。每个键是唯一的可以通过键快速访问对应的值。
1. 创建和初始化
#include unordered_map
#include iostream
#include stringint main() {std::unordered_mapstd::string, int umap {{apple, 3}, {banana, 5}, {orange, 2}}; // 初始化// 遍历键值对for (const auto kv : umap) {std::cout kv.first - kv.second std::endl;}return 0;
}2. 插入元素
使用 insert 或 operator[] 插入键值对。operator[] 如果键不存在会插入新键并初始化值为默认值。
umap[grape] 10; // 插入或更新键为 grape 的值
umap.insert({melon, 8}); // 插入键值对 {melon, 8}3. 查找元素
使用 find 方法查找元素若找到则返回指向键值对的迭代器否则返回 end()。
auto it umap.find(banana);
if (it ! umap.end()) {std::cout 香蕉数量: it-second std::endl;
}4. 删除元素
使用 erase 方法删除指定键的元素。
umap.erase(orange); // 删除键 orange5. 大小和清空
size() 获取 unordered_map 的键值对数量。clear() 清空所有元素。
std::cout 键值对数量: umap.size() std::endl;
umap.clear();三、哈希表
哈希表是一种基于哈希函数的数据结构用于快速存储和查找数据。它的核心思想是将键Key通过哈希函数转换为数组索引从而实现快速的数据访问。哈希表被广泛用于字典、缓存、集合等需要高效查找的场景是以上所介绍容器的底层结构。
3.1 哈希表的基本原理
哈希表包含以下几个核心概念
哈希函数将任意类型的键映射到数组中的一个索引位置。桶Bucket哈希表的每个索引位置称为一个桶存储一个或多个元素。冲突Collision当不同的键被映射到相同的索引时发生冲突。负载因子Load Factor表示哈希表的填充程度用公式 负载因子 元素个数 / 桶的数量 表示。负载因子过高会影响性能通常哈希表会在负载因子达到一定值时扩容。
哈希表的操作如插入、删除、查找在理想情况下的时间复杂度为 O ( 1 ) O(1) O(1)。这是因为哈希表可以通过哈希函数将键快速映射到对应的存储位置。
3.2 哈希函数
哈希函数是哈希表性能的核心其目的是将键均匀地分布在哈希表的桶中减少冲突的发生。好的哈希函数具有以下特性
均匀性不同的键被分布在不同的桶中避免过多的冲突。快速计算哈希函数的计算速度应尽可能快以提高哈希表操作的整体效率。
在 C 中标准库提供了许多内置类型的哈希函数如 std::hashint、std::hashstd::string 等。此外用户也可以为自定义类型定义自己的哈希函数。
3.3 解决冲突的几种办法
1. 开放地址法Open Addressing
开放地址法是在哈希表中找一个新的空位来存储冲突元素。当发生冲突时通过探测寻找下一个可用位置存放新元素。开放地址法常见的探测方式有
a. 线性探测Linear Probing
在发生冲突时线性探测通过固定步长通常为 1逐步查找下一个空位直到找到可用位置。
公式hash(key) i其中 i 是冲突次数。优点实现简单。缺点容易出现“聚集”现象即相邻的桶很容易连续被填满降低查找效率。
int linearProbing(int hashValue, int i, int tableSize) {return (hashValue i) % tableSize;
}b. 二次探测Quadratic Probing
二次探测通过平方增长的步长来查找下一个位置避免线性探测的“聚集”问题。
公式hash(key) i^2。优点减少了聚集现象。缺点在高负载因子下探测序列可能重复循环导致找不到空位。
int quadraticProbing(int hashValue, int i, int tableSize) {return (hashValue i * i) % tableSize;
}c. 双重哈希Double Hashing
双重哈希采用两个哈希函数在发生冲突时根据第二个哈希函数的值决定步长。
公式hash1(key) i * hash2(key)。优点能有效降低聚集现象冲突处理更加均匀。缺点需要设计两个独立的哈希函数且对负载因子要求较高。
int doubleHashing(int hashValue, int i, int tableSize, int hash2) {return (hashValue i * hash2) % tableSize;
}2. 拉链法Chaining
拉链法将每个哈希表位置桶设计为一个链表所有被哈希到同一位置的元素都存储在该链表中。插入新元素时将其添加到链表中查找时则遍历该链表。
优点 实现简单链表支持动态扩展不受哈希表容量影响。插入、删除操作简单尤其适合不定长数据结构如链表、树等。 缺点 冲突严重时链表可能变长影响查找效率最坏情况为 O ( n ) O(n) O(n)。需要额外的链表存储空间。
四、哈希表的模拟实现
4.1 开放地址法线性探测
1. DefaultHashFunc 哈希函数类
DefaultHashFunc 是一个通用的哈希函数模板类用于将键转换为哈希值。代码对整型和字符串类型分别进行了不同的哈希计算
对于整型或其他非字符串类型直接将键转换为 size_t 类型。对于 string 类型定义了一个专门的特化版本使用一种常见的哈希算法将字符串中的每个字符逐步加入到哈希值中并乘以一个质数131来增加分布的均匀性。
templateclass K
class DefaultHashFunc {
public:size_t operator()(const K key) {return (size_t)key;}
};template
class DefaultHashFuncstring {
public:size_t operator()(const string str) {size_t hash 0;for (auto ch : str) {hash * 131;hash ch;}return hash;}
};2. HashData 类
HashData 类表示哈希表中的一个数据节点包含一个键值对 _kv 和一个 STATE 状态 _state。STATE 枚举类定义了三个状态
EXIST表示该位置有数据。EMPTY表示该位置为空。DELETE表示该位置的数据已被删除。
这种状态管理方便在开放地址法中处理删除操作。
enum STATE {EXIST,EMPTY,DELETE
};templateclass K, class V
class HashData {
public:pairK, V _kv;STATE _state EMPTY;
};3. HashTable 类
HashTable 是哈希表的主体类支持以下操作
构造函数初始化哈希表容量默认大小为 10。
public:HashTable() {_table.resize(10);}插入操作 Insert向哈希表插入一个键值对 kv。如果负载因子达到 0.7进行扩容操作即 resize。 扩容操作创建一个新的哈希表将所有旧数据重新插入到新表中。这样可以重新计算哈希值以确保数据均匀分布。线性探测若哈希值对应的桶已经存在数据使用线性探测法查找下一个空闲位置直到找到空位。
bool Insert(const pairK, V kv) {// 扩容,扩容之后映射关系变了需要重新映射if ((double)_n / _table.size() 0.7) {size_t newSize _table.size() * 2;// 遍历旧表重新映射到新表HashTableK, V, HashFunc newHT;newHT._table.resize(newSize);for (size_t i 0; i _table.size(); i) {newHT.Insert(_table[i]._kv);}_table.swap(newHT._table);}// 线性探测// 起始位置处理空间大小是capacity还是sizeHashFunc hf;size_t hashi hf(kv.first) % _table.size();while (_table[hashi]._state EXIST) {hashi;hashi % _table.size();}_table[hashi]._kv kv;_table[hashi]._state EXIST;_n;return true;
}查找操作 Find通过哈希函数定位键在哈希表中的位置若发生冲突则使用线性探测逐步查找直到找到匹配的键或遇到空位置。
HashDataconst K, V* Find(const K key) {// 线性探测HashFunc hf;size_t hashi hf(key) % _table.size();while (_table[hashi]._state ! EMPTY) {if (_table[hashi]._state EXIST _table[hashi]._kv.first key) {return (HashDataconst K, V*) _table[hashi];}hashi;hashi % _table.size();}return nullptr;
}删除操作 Erase先通过 Find 方法查找键的位置如果找到则将该位置的状态标记为 DELETE并减少元素计数 _n。
bool Erase(const K key) {HashDataconst K, V* ret Find(key);if (ret) {ret-_state DELETE;--_n;return true;}return false;
}4. 私有成员
_table存储 HashData 的向量作为哈希表的实际存储容器。_n存储有效数据的个数用于计算负载因子并触发扩容操作。
private:vectorHashDataK, V _table;size_t _n 0; // 存储有效数据的个数
};️总结
哈希函数代码定义了默认的 DefaultHashFunc支持不同类型的键。开放地址法线性探测处理冲突的方式当发生哈希冲突时逐步向后探测下一个空位。扩容机制当负载因子达到一定值时动态扩展哈希表大小并重新分配数据减少冲突。
4.2 拉链法哈希桶
这里我们继续沿用以上的DefaultHashFunc 哈希函数类。
1. HashNode 类
HashNode 类表示哈希表中的一个节点包含一个键值对 _kv 和一个指向下一个节点的指针 _next。该类用于构成链表以解决哈希冲突。
templateclass K, class V
class HashNode {
public:pairK, V _kv;HashNodeK, V* _next;HashNode(const pairK, V kv): _kv(kv), _next(nullptr) {}
};_kv存储键值对。_next指向链表中的下一个节点。
2. HashTable 类
HashTable 使用拉链法来处理哈希冲突。每个桶存储一个链表的头节点当多个键映射到相同的哈希位置时通过链表存储多个节点。
成员变量
_tablestd::vector 的每个位置存储一个链表头节点指针表示一个桶。_n存储哈希表中当前有效数据的数量。
private:vectorNode* _table; // 指针数组size_t _n 0; // 存储了多少有效数据构造函数和析构函数
构造函数初始化哈希表大小为 10 个桶。析构函数遍历每个桶的链表并释放所有节点的内存。
HashTable() {_table.resize(10, nullptr);
}~HashTable() {for (size_t i 0; i _table.size(); i) {Node* cur _table[i];while (cur) {Node* next cur-_next;delete cur;cur next;}_table[i] nullptr;}
}插入操作 Insert
插入操作首先检查键是否已存在若存在则返回 false避免重复插入。若键不存在执行以下步骤
扩容若负载因子达到 1则将哈希表容量扩大一倍。 新建一个更大的表并将旧表中的元素重新哈希并插入新表。 计算哈希值根据哈希函数 HashFunc 计算哈希值。插入到链表将新节点插入到对应桶的链表头部头插法方便且高效。
bool Insert(const pairK, V kv) {if (Find(kv.first)) {return false;}HashFunc hf;if (_n _table.size()) {size_t newSize _table.size() * 2;vectorNode* newTable;newTable.resize(newSize, nullptr);for (size_t i 0; i _table.size(); i) {Node* cur _table[i];while (cur) {Node* next cur-_next;size_t hashi hf(cur-_kv.first) % newSize;cur-_next newTable[hashi];newTable[hashi] cur;cur next;}_table[i] nullptr;}_table.swap(newTable);}size_t hashi hf(kv.first) % _table.size();Node* newnode new Node(kv);newnode-_next _table[hashi];_table[hashi] newnode;_n;return true;
}查找操作 Find
查找操作使用哈希函数计算键的位置遍历该位置的链表查找对应键的节点。如果找到则返回节点指针否则返回 nullptr。
Node* Find(const K key) {HashFunc hf;size_t hashi hf(key) % _table.size();Node* cur _table[hashi];while (cur) {if (cur-_kv.first key) {return cur;}cur cur-_next;}return nullptr;
}删除操作 Erase
删除操作与查找类似通过哈希值定位到对应的链表找到目标节点后将其从链表中移除。
如果要删除的节点是链表头节点直接更新桶头指针。否则将该节点从链表中删除。
bool Erase(const K key) {HashFunc hf;size_t hashi hf(key) % _table.size();Node* prev nullptr;Node* cur _table[hashi];while (cur) {if (cur-_kv.first key) {if (prev nullptr) {_table[hashi] cur-_next;} else {prev-_next cur-_next;}--_n;delete cur;return true;}prev cur;cur cur-_next;}return false;
}打印操作 Print
打印哈希表中的内容展示每个桶中的链表结构用于观察哈希表的分布情况。
void Print() {for (size_t i 0; i _table.size(); i) {printf([%d]-, i);Node* cur _table[i];while (cur) {cout cur-_kv.first : cur-_kv.second -;cur cur-_next;}printf(NULL\n);}cout endl;
}️总结
哈希函数使用默认的 HashFunc 计算键的哈希值映射到对应桶位置。拉链法每个桶使用链表来处理哈希冲突链表结构灵活且易于扩展。扩容当负载因子达到 1 时哈希表自动扩容以减少冲突。 结语
哈希表不仅仅是一个工具更是一种思想。它带给我们的不仅是高效的算法更是对数据结构和算法优化的深刻理解。掌握了哈希表的设计与实现你将拥有在数据密集型任务中快速处理信息的能力。希望本篇博客能帮助你在C的学习道路上更进一步感受到编程的魅力。
今天的分享到这里就结束啦如果觉得文章还不错的话可以三连支持一下17的主页还有很多有趣的文章欢迎小伙伴们前去点评您的支持就是17前进的动力
