在传统的数据结构中#xff0c;例如数组#xff0c;链表和二叉平衡树等数据结构#xff0c;这些数据结构的元素关键…前言

在传统的数据结构中例如数组链表和二叉平衡树等数据结构这些数据结构的元素关键码与其存储位置之间没有对应的关系因此在这些数据结构中进行查找的时候必须要经过关键码的多次比较来实现使得顺序的数据结构的查找时间复杂度为O(n)平衡树的查找时间复杂度为O(logn)它们的搜索效率都取决于比较的次数。

那么我们能不能设计出一种数据结构不需要通过关键码的比较就可以直接定位到我们需要搜索的元素呢

哈希表通过一种哈希函数使得元素的存储位置(value)和关键码(key)之间建立一一映射的关系使其查找的时间复杂度为O(1)。

假设现在我需要存储一堆int类型的数据通过哈希表的方式来存储我们可以先设计出一个hash函数

hash(key)

其中key为我们需要存储的int数据m为哈希表的长度这个哈希表的本质是一个数组所以说也就是数组的长度通过key是m算出来的值为key这个数据的存储位置。

如下图所示

哈希表又分为闭散列哈希和开散列哈希如上面的图就是一个闭散列的哈希那么闭散列哈希和开散列哈希又有什么区别呢。

闭散列哈希本质就是一个数组将我们需要存储的值直接存入数组中但是这样会有一个问题如上面的图所示17已经被我们存入到了7下标的位置如果现在我们需要存27呢

27经过hash函数计算后得到的结果还是存在7下标的位置而这个时候7下标的位置已经又17呢这样就会引发哈希冲突的问题。

如下图所示

对于哈希冲突的解决方法我们可以通过优化哈希函数来解决但是这种方法只能减少函数冲突而不能完全避免哈希冲突所以在这里对于哈希函数的优化就不过多讲解。

那么我们还可以怎么解决哈希冲突呢于是就有了闭散列哈希和开散列哈希两种哈希表。

闭散列哈希

所谓的闭散列哈希表就是我们上图中的哈希表一样哈希表就是一个简单的数组当发生哈希冲突的时候我们从当前位置开始进行向后探测直到找到空位就将该数进行插入。

如下图所示

当插入其他数据时如果发生哈希冲突解决方法也一样当向后探测到末尾时将从0下标位置开始探测即形成一个环形探测。

同时如果哈希表已满将会对哈希表进行扩容但是扩容后还需要又重新映射的操作在这里先不解释在后面的开散列哈希中进行讲解。

开散列哈希

从闭散列哈希中可以看出闭散列哈希的缺陷是很大的在极限情况下闭散列哈希的查找可能就变成了数组的查找使其时间复杂度变为O(n)所以为了避免这种情况就引出了开散列哈希。

在开散列哈希中

我们不再简单的使用一个数组来存储数据而是通过链表的方式来存储数据当不同的数据通过哈希函数算出来的位置相同时我们将这一类数据归类为一个集合每一个子集也称为一个桶各个桶中的元素通过链表的方式链接起来每个链表的头节点保存到哈希数组中。

首先我们来定义一下一个hash结点的结构体看看一个结点中需要有那些变量。

Tstruct

_next;//指向下一个结点//构造函数hash_node(const

val):_val(val),

哈希结点的定义非常简单就是一个存储数据的val和指向下一个结点的指针

哈希表类定义

//哈希表其中Val为我们存储数据的类型Hash我为哈希函数templateclass

Val,

在哈希表类中有两个成员变量一个是哈希数组数组中的元素都是一个哈希结点的指针_nums代表哈希表中已经有多少个数据。

接下来看一下模板参数第一个模板参数为插入数据的类型第二个模板参数为一个哈希函数因为我需要使用这个哈希函数来将数据类型转换为整数方便我们计算出映射位置。

例如如果我需要存储的val是一个string类型的数据那么字符串不能直接计算出映射位置需要将这个string类型转换为整数才能计算出映射位置。

同时由于我们的哈希函数是一个缺省参数即我们需要在我们的实现中有一个自己的哈希函数这里我们先来实现一个适用于普通类型的哈希函数。

这里的哈希函数其实是一个仿函数如果你不知道仿函数可以先去了解一下什么是仿函数。

Kstruct

对于处理int类型的哈希函数来说非常简单我们直接将int值返回就好了。

例如如果我需要存储14通过哈希函数后返回的就是14后续插入的时候在通过这个14计算映射下标即可。

构造函数和析构函数

这里的_vec成员变量我们默认这个数组初始化为10的大小同时内容都为nullptr。

_vec(10,

nullptr)//哈希数组默认大小为10{}//析构函数~hash(){}

insert插入函数

我们在插入数据之前需要先判断该数据存不存在哈希表中如果已经存在就不再插入了

同时要判断如果此时有效数据的个数数组的长度我们需要给哈希数组进行一个扩容避免哈希冲突过多时导致同一个桶中链接的结点越来越多链接越来越长从而影响查找的效率。

//增bool

hash_func;//定义哈希函数类对象//先判断做一个去重Node*

cur

_nums)//插入之前判断是否需要扩容{reserve();//这里reserve也没有实现后面会实现}Node*

new_node

Node(data);//开辟一个新的哈希结点new_node-_val

data;//找到需要插入的位置并将结点链接到哈希表中size_t

index

new_node;_nums;//有效数据个数加1return

true;}

扩容不单单只是将哈希数组扩大二倍还需要将原来的结点重新计算映射位置插入到新的哈希数组中。

从图中我们可以看到在旧的哈希数组中结点13是在3下标里面的当扩容了新的哈希数组后结点13是在13下标里面的也就是说扩容后原来结点的映射位置会发生变化所以我们需要将所有的结点都重新计算一遍映射位置重新插入。

//扩容void

_vec.size();//扩容扩2倍//先开辟一块更大的数组std::vectorNode*

nullptr);//遍历原来的哈希数组将结点链接到新的数组中for

(auto

tmp-_next;//计算新的映射位置并插入结点size_t

index

tmp_next;}}//与原来的旧数组进行交换_vec.swap(new_vec);}

erase删除函数

对于删除函数来说我们需要先找到删除数据的映射位置然后在这个桶里面去找到我们需要删除的结点。

//删bool

nullptr)//说明要删除的结点就是桶中的第一个结点_vec[index]

cur-_next;delete

对于查找函数来说就比较简单了先计算出映射位置然后再该位置的桶中去查找即可。

find(const

在上面的实现中我们的哈希表基本上只能用来存储int类型的数据如果我们想要存储string类型的数据的时候怎么办因为哈希表的存储是需要整数值计算下标的而string字符串类型无法直接得出一个整数值所以我们需要自己实现一个关于string类型的哈希函数即通过string类型得出一个整数值。

这里需要用到模板的特化不了解模板的特化的可以先看下面这篇博客。

//符合string要求的哈希函数templatestruct

operator()(const

在这个哈希函数中我们可以先遍历每一个字符将每一个字符转换为整型然后再加一个值最后我们就可以得到一个count整型就能通过count这个整型计算对应的映射位置。

对应字符串类型的哈希函数为什么这样设计为什么要乘131我是参考别人来完成的具体内容可以下面这篇博客。

各种字符串Hash函数

_next;//指向下一个结点//构造函数hash_node(const

val):_val(val),

_next(nullptr){}};//符合int要求的哈希函数仿函数templateclass

Kstruct

(size_t)tmp;}};//符合string要求的哈希函数templatestruct

operator()(const

_nums;//有效数据个数public://构造函数hash():_nums(0),

_vec(10,

nullptr)//哈希数组默认大小为10{}//析构函数~hash(){}//增bool

insert(const

//插入之前判断是否需要扩容{reserve();}Node*

new_node

Node(data);//开辟一个新的哈希结点new_node-_val

data;//找到需要插入的位置并将结点链接到哈希表中size_t

index

new_node;_nums;//有效数据个数加1return

true;}//删bool

nullptr)//说明要删除的结点就是桶中的第一个结点{_vec[index]

cur-_next;}delete

std::endl;}//私有成员函数private://扩容void

reserve(){Hash

_vec.size();//扩容扩2倍//先开辟一块更大的数组std::vectorNode*

nullptr);//遍历原来的哈希数组将结点链接到新的数组中for

(auto

tmp-_next;//计算新的映射位置并插入结点size_t

index

tmp_next;}}//与原来的旧数组进行交换_vec.swap(new_vec);}};}

test.cpp

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

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;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()

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

{Test1();Test2();Test3();Test4();return