公司网站空间怎么续费,小程序多用户商城源码,郑州做网站优化的公,各类服装网站建设前言 在本篇博客中#xff0c;作者将会带领你使用C语言来实现一个哈希表。 一.什么是哈希表 在实现哈希表之前#xff0c;我们先来学习一下什么是哈希表。 在传统的数据结构中#xff0c;例如数组#xff0c;链表和二叉平衡树等数据结构#xff0c;这些数据结构的元素关键…前言 在本篇博客中作者将会带领你使用C语言来实现一个哈希表。 一.什么是哈希表 在实现哈希表之前我们先来学习一下什么是哈希表。 在传统的数据结构中例如数组链表和二叉平衡树等数据结构这些数据结构的元素关键码与其存储位置之间没有对应的关系因此在这些数据结构中进行查找的时候必须要经过关键码的多次比较来实现使得顺序的数据结构的查找时间复杂度为O(n)平衡树的查找时间复杂度为O(logn)它们的搜索效率都取决于比较的次数。 那么我们能不能设计出一种数据结构不需要通过关键码的比较就可以直接定位到我们需要搜索的元素呢 就这样哈希表诞生了。 哈希表通过一种哈希函数使得元素的存储位置(value)和关键码(key)之间建立一一映射的关系使其查找的时间复杂度为O(1)。 举例 如果你还是不是很明白那么请看下面这个例子。 假设现在我需要存储一堆int类型的数据通过哈希表的方式来存储我们可以先设计出一个hash函数 hash(key) key % m。%为取模 其中key为我们需要存储的int数据m为哈希表的长度这个哈希表的本质是一个数组所以说也就是数组的长度通过key是m算出来的值为key这个数据的存储位置。 如下图所示 如上就是哈希表的存储方式。 二.哈希表的分类 哈希表又分为闭散列哈希和开散列哈希如上面的图就是一个闭散列的哈希那么闭散列哈希和开散列哈希又有什么区别呢。 闭散列哈希本质就是一个数组将我们需要存储的值直接存入数组中但是这样会有一个问题如上面的图所示17已经被我们存入到了7下标的位置如果现在我们需要存27呢 27经过hash函数计算后得到的结果还是存在7下标的位置而这个时候7下标的位置已经又17呢这样就会引发哈希冲突的问题。 如下图所示 哈希冲突 对于哈希冲突的解决方法我们可以通过优化哈希函数来解决但是这种方法只能减少函数冲突而不能完全避免哈希冲突所以在这里对于哈希函数的优化就不过多讲解。 那么我们还可以怎么解决哈希冲突呢于是就有了闭散列哈希和开散列哈希两种哈希表。 闭散列哈希 所谓的闭散列哈希表就是我们上图中的哈希表一样哈希表就是一个简单的数组当发生哈希冲突的时候我们从当前位置开始进行向后探测直到找到空位就将该数进行插入。 如下图所示 当插入其他数据时如果发生哈希冲突解决方法也一样当向后探测到末尾时将从0下标位置开始探测即形成一个环形探测。同时如果哈希表已满将会对哈希表进行扩容但是扩容后还需要又重新映射的操作在这里先不解释在后面的开散列哈希中进行讲解。 开散列哈希 从闭散列哈希中可以看出闭散列哈希的缺陷是很大的在极限情况下闭散列哈希的查找可能就变成了数组的查找使其时间复杂度变为O(n)所以为了避免这种情况就引出了开散列哈希。 在开散列哈希中 我们不再简单的使用一个数组来存储数据而是通过链表的方式来存储数据当不同的数据通过哈希函数算出来的位置相同时我们将这一类数据归类为一个集合每一个子集也称为一个桶各个桶中的元素通过链表的方式链接起来每个链表的头节点保存到哈希数组中。 如下图所示。 通过上面的这种方式我们就可以很好的解决哈希冲突问题。 三.哈希表的实现 在本篇博客中只实现开散列因为开散列更实用。 哈希结点类的定义 首先我们来定义一下一个hash结点的结构体看看一个结点中需要有那些变量。 //定义哈希结点templateclass Tstruct hash_node{T _val;//存储的数据hash_node* _next;//指向下一个结点//构造函数hash_node(const T* val):_val(val), _next(nullptr){}}; 哈希结点的定义非常简单就是一个存储数据的val和指向下一个结点的指针 所以整个哈希表的结构如下图所示 哈希表类定义 定义完了哈希结点接下来就可以来定义我们的哈希表类了。 //哈希表其中Val为我们存储数据的类型Hash我为哈希函数templateclass Val, class Hash HashValclass hash{typedef hash_nodeVal Node;private:std::vectorNode* _vec;//哈希数组size_t _nums;//有效数据个数}; 在哈希表类中有两个成员变量一个是哈希数组数组中的元素都是一个哈希结点的指针_nums代表哈希表中已经有多少个数据。 接下来看一下模板参数第一个模板参数为插入数据的类型第二个模板参数为一个哈希函数因为我需要使用这个哈希函数来将数据类型转换为整数方便我们计算出映射位置。 例如如果我需要存储的val是一个string类型的数据那么字符串不能直接计算出映射位置需要将这个string类型转换为整数才能计算出映射位置。 int类型的哈希函数 同时由于我们的哈希函数是一个缺省参数即我们需要在我们的实现中有一个自己的哈希函数这里我们先来实现一个适用于普通类型的哈希函数。 这里的哈希函数其实是一个仿函数如果你不知道仿函数可以先去了解一下什么是仿函数。 //符合int要求的哈希函数仿函数templateclass Kstruct Hash{size_t operator()(const K tmp){return (size_t)tmp;}}; 对于处理int类型的哈希函数来说非常简单我们直接将int值返回就好了。 例如如果我需要存储14通过哈希函数后返回的就是14后续插入的时候在通过这个14计算映射下标即可。 构造函数和析构函数 对于构造函数来说我们只需要给成员变量进行一个初始化即可。 这里的_vec成员变量我们默认这个数组初始化为10的大小同时内容都为nullptr。 //构造函数hash():_nums(0), _vec(10, nullptr)//哈希数组默认大小为10{}//析构函数~hash(){}
insert插入函数 下面是插入函数的实现。 我们在插入数据之前需要先判断该数据存不存在哈希表中如果已经存在就不再插入了 同时要判断如果此时有效数据的个数数组的长度我们需要给哈希数组进行一个扩容避免哈希冲突过多时导致同一个桶中链接的结点越来越多链接越来越长从而影响查找的效率。 //增bool insert(const Val data){Hash hash_func;//定义哈希函数类对象//先判断做一个去重Node* cur find(data);//这里find还没实现后面会实现if (cur ! nullptr)return false;if (_vec.size() _nums)//插入之前判断是否需要扩容{reserve();//这里reserve也没有实现后面会实现}Node* new_node new Node(data);//开辟一个新的哈希结点new_node-_val data;//找到需要插入的位置并将结点链接到哈希表中size_t index hash_func(data) % _vec.size();new_node-_next _vec[index];_vec[index] new_node;_nums;//有效数据个数加1return true;}
reserve扩容函数 对于扩容操作我们默认将哈希数组扩容一个二倍。 注意 扩容不单单只是将哈希数组扩大二倍还需要将原来的结点重新计算映射位置插入到新的哈希数组中。 如下图所示。 从图中我们可以看到在旧的哈希数组中结点13是在3下标里面的当扩容了新的哈希数组后结点13是在13下标里面的也就是说扩容后原来结点的映射位置会发生变化所以我们需要将所有的结点都重新计算一遍映射位置重新插入。 //扩容void reserve(){Hash hash_func;size_t new_capacity 2 * _vec.size();//扩容扩2倍//先开辟一块更大的数组std::vectorNode* new_vec(new_capacity, nullptr);//遍历原来的哈希数组将结点链接到新的数组中for (auto tmp : _vec){while (tmp ! nullptr){//保存tmp的下一个结点Node* tmp_next tmp-_next;//计算新的映射位置并插入结点size_t index hash_func(tmp-_val) % new_vec.size();tmp-_next new_vec[index];new_vec[index] tmp;tmp tmp_next;}}//与原来的旧数组进行交换_vec.swap(new_vec);}
erase删除函数 对于删除函数来说我们需要先找到删除数据的映射位置然后在这个桶里面去找到我们需要删除的结点。 //删bool erase(const Val data){Hash hash_func;//先找到映射位置size_t index hash_func(data) % _vec.size();Node* cur _vec[index];Node* prev nullptr;while (cur ! nullptr){if (cur-_val data){if (prev nullptr)//说明要删除的结点就是桶中的第一个结点_vec[index] cur-_next;elseprev-_next cur-_next;delete cur;_nums--;return true;}else{prev cur;cur cur-_next;}}return false;} find查找函数 对于查找函数来说就比较简单了先计算出映射位置然后再该位置的桶中去查找即可。 //查返回查找结点的指针Node* find(const Val data){Hash hash_func;//先查找映射位置size_t index hash_func(data) % _vec.size();Node* cur _vec[index];while (cur ! nullptr){if (cur-_val data)return cur;elsecur cur-_next;}return nullptr;}
string类型的哈希函数 在上面的实现中我们的哈希表基本上只能用来存储int类型的数据如果我们想要存储string类型的数据的时候怎么办因为哈希表的存储是需要整数值计算下标的而string字符串类型无法直接得出一个整数值所以我们需要自己实现一个关于string类型的哈希函数即通过string类型得出一个整数值。 注意 这里需要用到模板的特化不了解模板的特化的可以先看下面这篇博客。 【C】模板进阶_函数模板进阶-CSDN博客 //符合string要求的哈希函数templatestruct Hashstd::string{size_t operator()(const std::string str){size_t count 0;for (auto ch : str){count count * 131 (size_t)ch;}return count;}}; 在这个哈希函数中我们可以先遍历每一个字符将每一个字符转换为整型然后再加一个值最后我们就可以得到一个count整型就能通过count这个整型计算对应的映射位置。 对应字符串类型的哈希函数为什么这样设计为什么要乘131我是参考别人来完成的具体内容可以下面这篇博客。 各种字符串Hash函数 - clq - 博客园 (cnblogs.com) 四.所有源代码
blog_hash.h
#pragma once
#include vector
#include string
#include iostreamnamespace blog_hash
{//定义哈希结点templateclass Tstruct hash_node{T _val;//存储的数据hash_node* _next;//指向下一个结点//构造函数hash_node(const T val):_val(val), _next(nullptr){}};//符合int要求的哈希函数仿函数templateclass Kstruct Hash{size_t operator()(const K tmp){return (size_t)tmp;}};//符合string要求的哈希函数templatestruct Hashstd::string{size_t operator()(const std::string str){size_t count 0;for (auto ch : str){count count * 131 (size_t)ch;}return count;}};//哈希表templateclass Val, class Hash HashValclass hash{typedef hash_nodeVal Node;private:std::vectorNode* _vec;//哈希数组size_t _nums;//有效数据个数public://构造函数hash():_nums(0), _vec(10, nullptr)//哈希数组默认大小为10{}//析构函数~hash(){}//增bool insert(const Val data){Hash hash_func;//先判断做一个去重Node* cur find(data);if (cur ! nullptr)return false;if (_vec.size() _nums) //插入之前判断是否需要扩容{reserve();}Node* new_node new Node(data);//开辟一个新的哈希结点new_node-_val data;//找到需要插入的位置并将结点链接到哈希表中size_t index hash_func(data) % _vec.size();new_node-_next _vec[index];_vec[index] new_node;_nums;//有效数据个数加1return true;}//删bool erase(const Val data){Hash hash_func;//先找到映射位置size_t index hash_func(data) % _vec.size();Node* cur _vec[index];Node* prev nullptr;while (cur ! nullptr){if (cur-_val data){if (prev nullptr)//说明要删除的结点就是桶中的第一个结点{_vec[index] cur-_next;}else{prev-_next cur-_next;}delete cur;_nums--;return true;}else{prev cur;cur cur-_next;}}return false;}//改//查返回查找结点的指针Node* find(const Val data){Hash hash_func;//先查找映射位置size_t index hash_func(data) % _vec.size();Node* cur _vec[index];while (cur ! nullptr){if (cur-_val data)return cur;elsecur cur-_next;}return nullptr;}//打印函数方便我们做调试void Print(){for (auto tmp : _vec){while (tmp ! nullptr){std::cout tmp-_val ;tmp tmp-_next;}}std::cout std::endl;}//私有成员函数private://扩容void reserve(){Hash hash_func;size_t new_capacity 2 * _vec.size();//扩容扩2倍//先开辟一块更大的数组std::vectorNode* new_vec(new_capacity, nullptr);//遍历原来的哈希数组将结点链接到新的数组中for (auto tmp : _vec){while (tmp ! nullptr){//保存tmp的下一个结点Node* tmp_next tmp-_next;//计算新的映射位置并插入结点size_t index hash_func(tmp-_val) % new_vec.size();tmp-_next new_vec[index];new_vec[index] tmp;tmp tmp_next;}}//与原来的旧数组进行交换_vec.swap(new_vec);}};} test.cpp
#includeblog_hash.h
using namespace blog_hash;using Node blog_hash::hash_nodeint;void Test1()
{blog_hash::hashint h;h.insert(3);h.insert(3);h.insert(3);h.insert(3);h.insert(3);h.insert(13);h.insert(23);h.insert(33);h.insert(5);h.insert(6);h.Print();
}void Test2()
{blog_hash::hashint h;h.insert(3);h.insert(3);h.insert(3);h.insert(3);h.insert(3);h.insert(13);h.insert(23);h.insert(33);h.insert(5);h.insert(6);//测试查找Node* ret h.find(23);std::cout ret-_val std::endl;
}void Test3()
{blog_hash::hashint h;h.insert(3);h.insert(3);h.insert(3);h.insert(3);h.insert(3);h.insert(13);h.insert(23);h.insert(33);h.insert(5);h.insert(6);//测试删除h.erase(7);h.erase(8);h.Print();}void Test4()
{blog_hash::hashstd::string h;h.insert(abc);h.insert(abc);h.insert(bca);h.insert(cba);h.insert(asdgfas);h.insert(wqer);h.insert(zxv);h.Print();
}int main()
{Test1();Test2();Test3();Test4();return 0;
}
