先找出你的能力在那里,然后再决定你是谁。
—— 塔拉·韦斯特弗 《你当像鸟飞往你的山》
目录
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系列关联式容器实现。在C++98标准中,STL提供了一组底层基于红黑树的关联式容器,如map和set。这些容器在最坏情况下的查询复杂度为O(log N),即需要进行与红黑树高度成比例的比力操作。当树的节点数目巨大时,查询效率大概会受到显著影响。
为了进一步提拔查询性能,C++11引入了四种unordered系列的关联式容器,包括unordered_map、unordered_set、unordered_multimap和unordered_multiset。这些容器在使用方式上与传统的红黑树关联式容器相似,但其底层实现基于哈希表。通过哈希函数的高效映射,unordered容器在平均情况下可以或许实现O(1)的常数级查询复杂度,极大地进步了数据访问速度,尤其适用于对查询性能要求较高的场景。
总之,哈希表及其在C++中的实现,不但优化了数据存储与检索效率,还推动了现代软件开辟在处理大规模数据时的能力边界,成为盘算机科学范畴中不可或缺的核心技术之一。
2、哈希表的底层机制:原理与挑战
2.1 核心功能剖析:效率与灵活性的均衡
在序次结构和均衡树中,元素的关键码与其存储位置之间并没有直接的对应关系。因此,在查找一个元素时,必须通过多次比力其关键码。在序次查找中,时间复杂度为 O(N),而在均衡树中,查找时间复杂度为树的高度 O(log2N)),搜刮效率取决于查找过程中元素比力的次数。
理想的搜刮方法:可以不经过任何比力,一次直接从表中得到要搜刮的元素。为此,我们可以构造一种特殊的存储结构,通过一个哈希函数(hashFunc)将元素的存储位置与其关键码(key)创建逐一映射关系。在这种结构中:
- 插入元素:通过哈希函数盘算待插入元素的存储位置,并将元素存储在该位置。
- 搜刮元素:盘算元素的关键码对应的存储位置,直接访问该位置。如果该位置的元素关键码与待查找的元素类似,则搜刮成功。
2.2 哈希辩论的本质:问题与应对计谋
对于两个数据元素的关键字 ,如果其下标不同,对应的元素值也不同。但哈希函数盘算效果却是类似,即 Hash(ki)==Hash(kj),简单说两个不同的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} 这组值映射到M=11的表中,采用的哈希函数:
除法散列法也叫做除留余数法,顾名思义,假设哈希表的巨细为M,那么通过key除以M的余数作为映射位置的下标,也就是哈希函数为:h(key) = key % M。
3、闭散列的精确实现:从设计到优化
3.1 整体框架设计:面向扩展的架构
首先我们需要进行一个简单的框架搭建:
- 我们需要一个HashData类,来储存数据
- HashTable类底层是vector容器
- 因为会有不同范例的key,所以我们需要一个仿函数来将不同范例转换为size_t,这样才支持哈希函数映射
- 因为闭散列的删除不能直接删除节点,否则会导致线性探测失效,所以HashData类里需要纪录状态
- //版本一 --- 开放地址法(闭散列)
- #include<utility>
- #include<iostream>
- #include<vector>
- using namespace std;
- //节点状态
- enum status
- {
- EXIST,
- EMPTY,
- DELETE
- };
- //设计节点
- template<class K, class V>
- struct HashData
- {
- //键值对
- pair<K, V> _kv;
- //状态
- status _status;
- };
- // kv键值,仿函数解决不同类型key转换为size_t类型的下标
- template<class K,class V,class Hash=HashFunc<K>>
- class HashTable
- {
- public:
- HashTable()
- {
- _table.resize(10);
- }
- private:
- //底层是vector容器
- vector<HashData K, V>> _table;
- size_t _n;//有效数据个数
- Hash hs;//仿函数
- };
复制代码 3.2 仿函数的灵活性:高效哈希的关键
仿函数的作用是将不同数据范例的key转换为可以使用的size_t范例,这样可以才气一 一映射已往
对于可以直接表现范例转换的范例直接转换即可。而对于不能直接转换的范例(好比string)就要进行特殊处理了!
- template<class K>
- struct HashFunc
- {
- size_t operator()(const K& key)
- {
- return (size_t)key;
- }
- };
- template<>
- struct HashFunc<string>
- {
- size_t operator()(const string& s)
- {
- // BKDR
- size_t hash = 0;
- for (auto ch : s)
- {
- hash += ch;
- hash *= 131;
- }
- return hash;
- }
- };
复制代码 3.3 插入操作:辩论检测与位置分配
- 首先插入之前要先检查是否在哈希表中已经有数据了
- 然后检查该次是否需要进行扩容
- 通过key值选取合适位置进行插入,有效个数++
- bool insert(const pair<K, V>&kv)
- {
- //插入前先进行一个检查
- if (Find(kv.first)) return false;
- //是否需要扩容
- if (_n >= _table.size() * 0.7)
- {
- //进行替换
- HashTable<K, 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进行线性探测即可
- HashData<K, 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
- HashData<K, 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 pair<K, V>& kv)
- {
- if (Find(kv.first))
- return 0;
- //负载因子>=0.7 扩容
- if (_n*10 / _tables.size() >= 7)
- {
- HashTable<K, V>newht;
- 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;
- }
- HashData<K, 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)
- {
- HashData<K, V>* ret = Find(key);
- if (ret == nullptr)
- return 0;
- ret->_state = DELETE;
- return 1;
-
- }
- private:
- vector<HashData<K, V>> _tables;
- size_t _n; //标识数据个数
- };
复制代码 这样我们就实现了开辟地址法(闭散列)的哈希表!!!
4. 开散列的灵活实现:从底子到高效
我们已经实现了闭散列版本的哈希表,本日计划实现另一种哈希表的实现方式——开散列版本(也称哈希桶)。在深入实现之前,让我们先分析所需的工作。
开散列的核心头脑是将哈希表设计为一个数组,每个数组元素对应一个映射地址。为了办理哈希辩论,开散列采用链表的情势将辩论的元素链接起来,从而确保高效的查找和插入操作。
由于涉及到链表的使用,我们可以直接使用 STL库的 list 数据结构。然而,list 本质上是一个双向循环链表,对我们这样简单的场景来说,大概显得有些复杂且不敷高效。为了简化实现并节流内存空间,我们可以自行构造一个简单的单向非循环链表,完全可以满足需求,同时节流约一半的空间。
通过这一设计,我们既可以制止闭散列中大概出现的过多探测问题,又能以较低的实现成本构建一个功能完备且高效的哈希表。
4.1 节点设计:指针与数据的均衡艺术
因为我们要实现单链表结构,肯定要来先设计一下节点框架:
- //节点设计
- template<class K, class V, class Hash = HashFunc<K>>
- struct HashNode
- {
- //储存的数据
- pair<K, V> _kv;
- //下一个节点的指针
- HashNode<K, V>* _next;
- HashNode(const pair<K, V>& kv)
- :_kv(kv)
- , _next(nullptr)
- {}
- };
复制代码 4.2 整体框架搭建:链表与逻辑的融合
设计完成节点后,就可以动手构建整体框架了。哈希桶的底层结构通常由一个指针数组构成,同时需要引入一个变量用于纪录当前有效元素的个数,以便在负载因子过高时实时触发扩容操作。
实现的核心功能包括插入、删除和查找三个基本操作。需要注意的是,不同范例的数据在插入时需要通过哈希函数转换为 size_t 范例,这样才气将数据正确映射到数组中的对应位置。
在实现这些功能时,需要重点关注以下几点:
- 插入操作:根据哈希函数确定目标位置,处理大概的辩论,将新元素插入到对应链表中。
- 删除操作:查找到目标位置的链表节点并删除,同时需要妥善处理链表毗连。
- 查找操作:根据哈希函数定位到目标链表,然后序次查找目标节点。
通过上述基本功能的实现,我们可以构建一个高效的哈希桶结构,为后续功能扩展和优化打下结实底子。
- namespace hash_bucket
- {
- //仿函数 转整形
- template<class K>
- struct HashFunc
- {
- size_t operator()(const K& key)
- {
- return (size_t)key;
- }
- };
- template<>
- struct HashFunc<string>
- {
- size_t operator()(const string& s)
- {
- // BKDR
- size_t hash = 0;
- for (auto ch : s)
- {
- hash += ch;
- hash *= 131;
- }
- return hash;
- }
- };
- //节点设计
- template<class K, class V, class Hash = HashFunc<K>>
- struct HashNode
- {
- //储存的数据
- pair<K, V> _kv;
- //下一个节点的指针
- HashNode<K, V>* _next;
- HashNode(const pair<K, V>& kv)
- :_kv(kv)
- , _next(nullptr)
- {}
- };
- //开散列的哈希表
- // key value 仿函数(转换为size_t)
- template<class K, class V, class Hash = HashFunc<K>>
- class HashTable
- {
- typedef HashNode<K, 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:
- vector<Node*> _tables; // 指针数组
- //vector<list<pair<K, V>>> _tables;
- size_t _n = 0; // 表中存储数据个数
- //struct Date
- //{
- // list<pair<K, V>>_list;
- // map<pair<K, V>>_map;
- // size_t len; // len <=8 _list >8 存_map 红黑树
- //};
- //vector<Date>_tables;
- //size_t n = 0;
- };
- }
复制代码 4.3 插入函数:链表拓展与哈希分布
实现插入函数时,可以按照以下步调进行:
- 检查键是否存在:在插入新元素之前,首先检查当前键是否已经存在于哈希表中,只有在键不存在时才进行插入操作。
- 检查是否需要扩容:根据当前的负载因子(有效元素数与桶容量的比值),判定是否需要扩容以包管操作的效率。
- 盘算哈希值并定位映射位置:使用仿函数盘算键的哈希值 hashi,从而确定其在哈希表中的映射位置。
- 创建并插入新节点:构造一个新节点,并采用头插法将其插入到对应位置的链表中。
关于扩容逻辑,需要特别注意优化实现。最直观的方法是遍历原哈希表,将数据重新插入到新的哈希表中,并释放旧节点。然而,这种方式多做了无意义的节点释放与重建操作。实际上,我们可以直接将原有的节点从旧哈希表中迁移到新哈希表中,无需释放和重新分配,既节流了时间也优化了内存使用。
- bool Insert(const pair<K, V>& kv)
- {
- //先查找,已经有了相同数据插入失败
- if (Find(kv.first))
- return 0;
- Hash hash;
- // 负载因子等于1时候 进行扩容
- if (_n==_tables.size())
- {
- //HashTable<K, V>newht;
- //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);
- // // 多次插入 繁琐
- // 这?如果使?上?的?法,扩容时创建新的结点,后?还要使?旧结
- //点,浪费了
- // 下?的?法,直接移动旧表的结点到新表,效率更好
- vector<Node*> 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::HashTable<int, 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::HashTable<string, 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谢谢阅读!!!
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。 |