网站源码 下载,网站建设方案报价,无锡网站推广优化,小程序在线开发先找出你的能力在哪里#xff0c;然后再决定你是谁。
—— 塔拉韦斯特弗 《你当像鸟飞往你的山》 目录
1. C 与哈希表#xff1a;核心概念与引入
2. 哈希表的底层机制#xff1a;原理与挑战
2.1 核心功能解析#xff1a;效率与灵活性的平衡
2.2 哈希冲突的本质#x…
先找出你的能力在哪里然后再决定你是谁。
—— 塔拉·韦斯特弗 《你当像鸟飞往你的山》 目录
1. C 与哈希表核心概念与引入
2. 哈希表的底层机制原理与挑战
2.1 核心功能解析效率与灵活性的平衡
2.2 哈希冲突的本质问题与应对策略
2.3 开散列与闭散列两大解决方案的比较
3. 闭散列的精确实现从设计到优化
3.1 整体框架设计面向扩展的架构
3.2 仿函数的灵活性高效哈希的关键
3.3 插入操作冲突检测与位置分配
3.4 查找操作速度与准确的双重保障
3.5 删除操作标记与重构的细节优化
4. 开散列的灵活实现从基础到高效
4.1 节点设计指针与数据的平衡艺术
4.2 整体框架搭建链表与逻辑的融合
4.3 插入函数链表拓展与哈希分布
4.4 删除函数节点清理与空间复用
4.5 查找操作定位效率的优化实践
4.6 功能测试多场景验证与性能分析 1、C 与哈希表核心概念与引入
哈希表Hash Table是一种重要的数据结构它通过哈希函数将键映射到表中的特定位置从而实现对记录的快速访问支持高效的插入和查找操作。
哈希表的概念最早由H. P. Luhn于1953年提出他首次描述了利用哈希函数加速数据检索的过程。自此这一思想逐步演化并广泛应用于数据库管理系统和编程语言中成为计算机科学领域的重要基础之一。
随着计算机硬件性能的提升和数据量的爆炸性增长哈希表的作用愈发凸显。作为一种高效的数据结构哈希表在软件工程、数据库系统、网络搜索引擎等领域扮演着不可或缺的角色尤其在处理大规模数据和高频率查询时展现出卓越的性能优势。
在C中哈希表的功能主要通过unordered系列关联式容器实现。在C98标准中STL提供了一组底层基于红黑树的关联式容器如map和set。这些容器在最坏情况下的查询复杂度为O(log N)即需要进行与红黑树高度成比例的比较操作。当树的节点数量庞大时查询效率可能会受到显著影响。
为了进一步提升查询性能C11引入了四种unordered系列的关联式容器包括unordered_map、unordered_set、unordered_multimap和unordered_multiset。这些容器在使用方式上与传统的红黑树关联式容器相似但其底层实现基于哈希表。通过哈希函数的高效映射unordered容器在平均情况下能够实现O(1)的常数级查询复杂度极大地提高了数据访问速度尤其适用于对查询性能要求较高的场景。
总之哈希表及其在C中的实现不仅优化了数据存储与检索效率还推动了现代软件开发在处理大规模数据时的能力边界成为计算机科学领域中不可或缺的核心技术之一。
2、哈希表的底层机制原理与挑战
2.1 核心功能解析效率与灵活性的平衡
在顺序结构和平衡树中元素的关键码与其存储位置之间并没有直接的对应关系。因此在查找一个元素时必须通过多次比较其关键码。在顺序查找中时间复杂度为 O(N而在平衡树中查找时间复杂度为树的高度 O(log2N))搜索效率取决于查找过程中元素比较的次数。
理想的搜索方法可以不经过任何比较一次直接从表中得到要搜索的元素。为此我们可以构造一种特殊的存储结构通过一个哈希函数hashFunc将元素的存储位置与其关键码key建立一一映射关系。在这种结构中
插入元素通过哈希函数计算待插入元素的存储位置并将元素存储在该位置。搜索元素计算元素的关键码对应的存储位置直接访问该位置。如果该位置的元素关键码与待查找的元素相同则搜索成功。
2.2 哈希冲突的本质问题与应对策略
对于两个数据元素的关键字 如果其下标不同对应的元素值也不同。但哈希函数计算结果却是相同即 HashkiHashkj简单说两个不同的key可能会映射到同个位置去 这种现象称为哈希冲突或哈希碰撞。
哈希冲突的发生可能是由于哈希函数的设计问题。一个好的哈希函数应该满足以下原则
定义域覆盖所有关键字哈希函数的定义域必须包含所有需要存储的关键字如果散列表允许有 m个地址则哈希函数的值域应当在 0到 m-1 之间。均匀分布哈希函数应能将关键字均匀地映射到整个地址空间中减少冲突的概率。计算简单哈希函数应设计得尽可能简单以提高计算效率。
然而由于存储空间有限哈希函数难以完全避免哈希冲突的发生。因此发生哈希冲突时系统需要采取适当的处理方法。通常哈希冲突的解决方案有两种常见方法闭散列Open Addressing和开散列Chaining。
在闭散列中当发生冲突时寻找一个空位将元素存储在散列表中。这通常通过线性探测、二次探测或双重散列等技术实现。
在开散列中当发生冲突时多个元素被存储在同一个地址位置的链表中通常采用链表或其他数据结构来存储这些“同义词”。
在讨论哈希冲突的处理方法时另一个重要的概念是负载因子Load Factor。负载因子是哈希表中元素个数与表的总容量之间的比值通常表示为 负载因子反映了哈希表的“密集程度”。当负载因子较高时意味着哈希表中存储的元素接近其总容量发生哈希冲突的概率增大相反负载因子较低时哈希表中的元素较少冲突的概率较小。
负载因子的应用与影响 影响哈希冲突的概率负载因子越大哈希表中的元素越密集碰撞的概率也越高。为了降低冲突发生的概率通常在负载因子达到一定阈值时会进行哈希表的扩容将哈希表的容量增大从而降低负载因子并减少冲突。 闭散列中的负载因子在闭散列法中当负载因子增大时查找、插入等操作的时间复杂度会增加。因为哈希表的空闲位置减少冲突发生后需要进行探测可能导致操作变得低效。为避免这种情况当负载因子超过一定值通常为 0.7 或 0.75时会触发扩容操作将哈希表的大小翻倍并重新计算每个元素的哈希地址。 开散列中的负载因子在开散列法中负载因子的增大会导致链表的长度增加进而影响查找效率。当负载因子过高时链表变长查找、插入和删除操作的时间复杂度会退化为线性时间 O(n)。因此在开散列中通常也会采取相似的策略监控负载因子的变化当负载因子超过某个阈值时进行扩容或重新哈希。
2.3 开散列与闭散列两大解决方案的比较
哈希散列方法是一种高效的数据存储和检索方式其核心在于哈希函数和哈希表的构建。通过哈希函数将数据映射到数组索引上可以快速定位元素。然而当多个数据被映射到相同的索引即哈希冲突时需要采取有效的策略进行处理。根据解决冲突的方式哈希表分为两种类型闭散列和开散列。
闭散列开放定址法
闭散列的核心思想是将冲突的元素存放到哈希表中的其他空位置。其主要实现方式是线性探测
插入通过哈希函数计算得到目标位置。如果该位置为空则直接插入若发生冲突则从冲突位置开始依次向后探测直到找到空位置为止再插入元素。例如若元素44计算出的哈希地址为4但位置4已存有元素4则继续向后探测找到下一个空位置存放44。删除采用伪删除标记代替物理删除以免影响其他元素的搜索路径。例如若直接删除元素4则会导致后续查找44时路径断裂因此采用标记伪删除的方法。
优点
实现简单无需额外数据结构支持。
缺点
容易产生数据堆积又称“聚集”即多个冲突元素连续占据空位置导致后续插入和查找的效率显著下降。空间利用率较低特别是在装载因子较高时冲突频率增加性能退化明显。
为缓解上述问题可以使用二次探测法或其他改进方法优化冲突处理。
开散列链地址法
开散列通过为每个哈希地址维护一个链表来解决冲突
插入计算哈希地址后将冲突元素添加到对应链表的末尾。删除直接从链表中删除目标元素链表结构确保不会影响其他元素的查找。
优点
空间利用率高能更好地适应高装载因子。冲突处理灵活不会产生数据堆积查找效率相对稳定。
缺点
需要额外的链表存储空间。链表操作增加了一定的复杂性。
演示两种方法 {19,30,5,36,13,20,21,12,24,96} 这组值映射到M11的表中采用的哈希函数
除法散列法也叫做除留余数法顾名思义假设哈希表的大小为M那么通过key除以M的余数作为映射位置的下标也就是哈希函数为h(key) key % M。 3、闭散列的精确实现从设计到优化
3.1 整体框架设计面向扩展的架构
首先我们需要进行一个简单的框架搭建 我们需要一个HashData类来储存数据HashTable类底层是vector容器因为会有不同类型的key所以我们需要一个仿函数来将不同类型转换为size_t这样才支持哈希函数映射因为闭散列的删除不能直接删除节点否则会导致线性探测失效所以HashData类里需要记录状态 //版本一 --- 开放地址法闭散列
#includeutility
#includeiostream
#includevector
using namespace std;//节点状态
enum status
{EXIST,EMPTY,DELETE
};
//设计节点
templateclass K, class V
struct HashData
{//键值对pairK, V _kv;//状态status _status;
};
// kv键值仿函数解决不同类型key转换为size_t类型的下标
templateclass K,class V,class HashHashFuncK
class HashTable
{
public:HashTable(){_table.resize(10);}
private://底层是vector容器vectorHashData K, V _table;size_t _n;//有效数据个数Hash hs//仿函数
};3.2 仿函数的灵活性高效哈希的关键
仿函数的作用是将不同数据类型的key转换为可以使用的size_t类型这样可以才能一 一映射过去 对于可以直接显示类型转换的类型直接转换即可。而对于不能直接转换的类型比如string就要进行特殊处理了
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};template
struct HashFuncstring
{size_t operator()(const string s){// BKDRsize_t hash 0;for (auto ch : s){hash ch;hash * 131;}return hash;}
};3.3 插入操作冲突检测与位置分配 首先插入之前要先检查是否在哈希表中已经有数据了 然后检查该次是否需要进行扩容 通过key值选取合适位置进行插入有效个数 bool insert(const pairK, Vkv)
{//插入前先进行一个检查if (Find(kv.first)) return false;//是否需要扩容if (_n _table.size() * 0.7){//进行替换HashTableK, V newHT;newHT._table.resize(_table.size() * 2);//进行赋值for (auto s : _table){ if (s._status EXIST)newHT.insert(s._kv);}//进行替换_table.swap(newHT._table);}//进行插入//hash地址size_t hash0 kv.first % _table.size();size_t hashi hash0;size_t i 1;//寻找合适位置进行插入// 线性探测while (_table[hashi].status EXIST){hashi (hash0 i) % _table.size(); //取模解决回绕问题i;}//找到合适位置了进行插入_table[hashi]._kv kv;_table[hashi].status EXIST;_n;return true;
}3.4 查找操作速度与准确的双重保障
查找逻辑很简单对Key进行线性探测即可
HashDataK, V* Find(const K key)
{size_t hash0 hs(key) % _table.size();size_t hashi hash0;size_t i 1;while (_table[hashi]._state ! EMPTY){if (_table[hashi]._state EXIST _table[hashi]._kv.first key) //这里需要加判断状态语句 我们删除只是该状态{return _table[hashi];}// 线性探测hashi (hash0 i) % _table.size();i;}return nullptr;
}3.5 删除操作标记与重构的细节优化
删除先通过key找到需要删除的数据 然后将状态设置为DELETE, 有效个数- -
//删除
bool Erase(const K key)
{//size_t hash0 hs(key) % _tables.size();//size_t hashi hash0;//size_t i 1;//while (_table[hashi]._state ! EMPTY)//{// if (_table[hashi]._state EXIST// _table[hashi]._kv.first key) // {// _table[hashi].status DELETE;// --_n;// return true;// }// // 线性探测// hashi (hash0 i) % _tables.size();// i;//}//return false;//复用 Find HashDataK, V* ret Find(key);if (ret nullptr){return false;}else{ret-_status DELETE;--_n;return true;}
}这里一开始的空间机制可以优化我们使用的哈希函数是除法散列法也叫做除留余数法当使用除法散列法时建议M取不太接近2的整数次冥的个质数(素数)。这样可以有效避免哈希冲突
优化一下采用接近2倍扩容的素数表进行开辟空间扩容
class HashTable
{
public:HashTable():_tables(__stl_next_prime(0)), _n(0){}inline unsigned long __stl_next_prime(unsigned long n){// Note: assumes long is at least 32 bits.static const int __stl_num_primes 28;static const unsigned long __stl_prime_list[__stl_num_primes] {53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};const unsigned long* first __stl_prime_list;const unsigned long* last __stl_prime_list __stl_num_primes;const unsigned long* pos lower_bound(first, last, n);return pos last ? *(last - 1) : *pos;}bool Insert(const pairK, V kv){if (Find(kv.first))return 0;//负载因子0.7 扩容if (_n*10 / _tables.size() 7){HashTableK, Vnewht;newht._tables.resize(__stl_next_prime(_tables.size() 1));for (auto data : _tables){// 旧表的数据映射到新表if (data._state EXIST){newht.Insert(data._kv);}}_tables.swap(newht._tables);}size_t hash0 kv.first % _tables.size();size_t hashi hash0;size_t i 1;int flag 1;while (_tables[hashi]._state EXIST){// 线性探测hashi (hash0 i) % _tables.size();i;/*hashi (hash0 (i*i*flag)) % _tables.size();if (hashi _tables.size())hashi _tables.size();if (flag 1){flag -1;}else{i;flag 1;}*/}_tables[hashi]._kv kv;_tables[hashi]._state EXIST;_n;return 1;}HashDataK, V* Find(const K key){size_t hash0 key % _tables.size();size_t hashi hash0;size_t i 1;while (_tables[hashi]._state ! EMPTY){if (_tables[hashi]._state EXIST _tables[hashi]._kv.first key){return _tables[hashi];}// 线性探测hashi (hash0 i) % _tables.size();i;}return nullptr;}bool Erase(const K key){HashDataK, V* ret Find(key);if (ret nullptr)return 0;ret-_state DELETE;return 1;}
private:vectorHashDataK, V _tables;size_t _n; //标识数据个数
};这样我们就实现了开发地址法闭散列的哈希表
4. 开散列的灵活实现从基础到高效
我们已经实现了闭散列版本的哈希表今天计划实现另一种哈希表的实现方式——开散列版本也称哈希桶。在深入实现之前让我们先分析所需的工作。
开散列的核心思想是将哈希表设计为一个数组每个数组元素对应一个映射地址。为了解决哈希冲突开散列采用链表的形式将冲突的元素链接起来从而确保高效的查找和插入操作。 由于涉及到链表的使用我们可以直接利用 STL库的 list 数据结构。然而list 本质上是一个双向循环链表对我们这样简单的场景来说可能显得有些复杂且不够高效。为了简化实现并节省内存空间我们可以自行构造一个简单的单向非循环链表完全可以满足需求同时节省约一半的空间。
通过这一设计我们既可以避免闭散列中可能出现的过多探测问题又能以较低的实现成本构建一个功能完备且高效的哈希表。
4.1 节点设计指针与数据的平衡艺术
因为我们要实现单链表结构肯定要来先设计一下节点框架
//节点设计
templateclass K, class V, class Hash HashFuncK
struct HashNode
{//储存的数据pairK, V _kv;//下一个节点的指针HashNodeK, V* _next;HashNode(const pairK, V kv):_kv(kv), _next(nullptr){}
};4.2 整体框架搭建链表与逻辑的融合
设计完成节点后就可以着手构建整体框架了。哈希桶的底层结构通常由一个指针数组构成同时需要引入一个变量用于记录当前有效元素的个数以便在负载因子过高时及时触发扩容操作。
实现的核心功能包括插入、删除和查找三个基本操作。需要注意的是不同类型的数据在插入时需要通过哈希函数转换为 size_t 类型这样才能将数据正确映射到数组中的对应位置。
在实现这些功能时需要重点关注以下几点
插入操作根据哈希函数确定目标位置处理可能的冲突将新元素插入到对应链表中。删除操作查找到目标位置的链表节点并删除同时需要妥善处理链表连接。查找操作根据哈希函数定位到目标链表然后顺序查找目标节点。
通过上述基本功能的实现我们可以构建一个高效的哈希桶结构为后续功能扩展和优化打下坚实基础。
namespace hash_bucket
{//仿函数 转整形templateclass Kstruct HashFunc{size_t operator()(const K key){return (size_t)key;}};templatestruct HashFuncstring{size_t operator()(const string s){// BKDRsize_t hash 0;for (auto ch : s){hash ch;hash * 131;}return hash;}};//节点设计 templateclass K, class V, class Hash HashFuncKstruct HashNode{//储存的数据pairK, V _kv;//下一个节点的指针HashNodeK, V* _next;HashNode(const pairK, V kv):_kv(kv), _next(nullptr){}};//开散列的哈希表// key value 仿函数转换为size_ttemplateclass K, class V, class Hash HashFuncKclass HashTable{typedef HashNodeK, V Node;inline unsigned long __stl_next_prime(unsigned long n){static const int __stl_num_primes 28;static const unsigned long __stl_prime_list[__stl_num_primes] {53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};const unsigned long* first __stl_prime_list;const unsigned long* last __stl_prime_list __stl_num_primes;const unsigned long* pos lower_bound(first, last, n);return pos last ? *(last - 1) : *pos;}public:HashTable():_tables(__stl_next_prime(0)),_n(0){}private:vectorNode* _tables; // 指针数组//vectorlistpairK, V _tables;size_t _n 0; // 表中存储数据个数//struct Date//{// listpairK, V_list;// mappairK, V_map;// size_t len; // len 8 _list 8 存_map 红黑树//};//vectorDate_tables;//size_t n 0;};}4.3 插入函数链表拓展与哈希分布
实现插入函数时可以按照以下步骤进行
检查键是否存在在插入新元素之前首先检查当前键是否已经存在于哈希表中只有在键不存在时才进行插入操作。检查是否需要扩容根据当前的负载因子有效元素数与桶容量的比值判断是否需要扩容以保证操作的效率。计算哈希值并定位映射位置利用仿函数计算键的哈希值 hashi从而确定其在哈希表中的映射位置。创建并插入新节点构造一个新节点并采用头插法将其插入到对应位置的链表中。
关于扩容逻辑需要特别注意优化实现。最直观的方法是遍历原哈希表将数据重新插入到新的哈希表中并释放旧节点。然而这种方式多做了无意义的节点释放与重建操作。实际上我们可以直接将原有的节点从旧哈希表中迁移到新哈希表中无需释放和重新分配既节省了时间也优化了内存使用。
bool Insert(const pairK, V kv)
{//先查找已经有了相同数据插入失败if (Find(kv.first))return 0;Hash hash;// 负载因子等于1时候 进行扩容if (_n_tables.size()){//HashTableK, Vnewht;//newht._tables.resize(__stl_next_prime(_tables.size() 1));//for (size_t i 0; i _tables.size(); i)//{// Node* cur _tables[i];// while (cur)// {// newht.Insert(cur-_kv);// cur cur-_next;// }//}//_tables.swap(newht._tables);// // 多次插入 繁琐// 这?如果使?上?的?法扩容时创建新的结点后?还要使?旧结//点浪费了// 下?的?法直接移动旧表的结点到新表效率更好vectorNode* newtable(__stl_next_prime(_tables.size() 1));for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;// 头插到新链表size_t hashi hash(cur-_kv.first) % newtable.size();cur-_next newtable[hashi];newtable[hashi] cur;cur next;}_tables[i] nullptr;}_tables.swap(newtable);}size_t hashi hash(kv.first) % _tables.size();// 头插Node* newnode new Node(kv);newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return 1;
}4.4 删除函数节点清理与空间复用
删除的逻辑是根据key值找到对应的位置在该位置的链表中检索是否有相等的数值。如果有就进行删除否则返回false
bool Erase(const K key)
{if (Find(key) nullptr)return 0;Hash hash;size_t hashi hash(key) % _tables.size();Node* cur _tables[hashi];Node* prev nullptr;while (cur){if (cur-_kv.first key){if (prev nullptr) //只有一个节点{_tables[hashi] cur-_next; }else //中间节点{prev-_next cur-_next;}delete cur;--_n;return 1;}else{// 在链表里遍历到删除的数据prev cur;cur cur-_next;}}return 0;
}4.5 查找操作定位效率的优化实践
查找的逻辑和删除类似根据key值找到映射位置再在该链表中进行检索找到返回节点指针反之返回空指针。
Node* Find(const K key)
{Hash hash;size_t hashi hash(key) % _tables.size();Node* cur _tables[hashi];while (cur){if (cur-_kv.first key){return cur;}cur cur-_next;}return __nullptr;
}4.6 功能测试多场景验证与性能分析
这里我们分别测试插入删除插入寻找字符串的处理
int main()
{int a[] { 19,30,5,36,13,20,21,12,24,96 };hash_bucket::HashTableint, int ht2;for (auto e : a){ht2.Insert({ e,e });}cout ht2.Find(96) endl;cout ht2.Find(30) endl;cout ht2.Find(19) endl endl;ht2.Erase(96);ht2.Erase(19);ht2.Erase(30);cout ht2.Find(96) endl;cout ht2.Find(30) endl;cout ht2.Find(19) endl endl;hash_bucket::HashTablestring, string ht3;const char* a2[] { abcd,sort,insert };for (auto e : a2){ht3.Insert({ e,e });}cout ht3.Find(abcd) endl;cout ht3.Erase(abcd) endl;return 0;
}看起来没有问题调试看看分布 通过对监视窗口的查看我们可以验证我们的代码正常运行的
Thanks谢谢阅读
