C++数据结构查找——哈希表(包含GIF和相关图示)
目录
一、介绍
哈希表(Hash Table)
1.定义
"散列表"也叫哈希表,是一个 根据键值(Key)直接访问在内存中的存储位置 的数据结构。哈希表通过一个哈希函数(散列函数),将键值(Key)映射为哈希表中的一个位置,我们可以通过这个位置来访问记录。
2.举例
为了方便理解,在另外一篇文章我看到一个很好的例子,以下加以阐述:
example:有一天你想给李四(键值Key)打电话,但是李四的电话你忘记了,这个时候你打开电话簿,电话薄里储存了人名首字母以及首字母对应的电话号码的页数的目录(哈希表),这个目录是由你所确定的一个法则得来的:将人名的姓转换为英文再转换为单个首字母(如王二→Wang→W),这个法则就是哈希函数,通过目录你找到了李四所对应的首字母L,在首字母L的后面你找到了李四的电话所在的页数(位置),翻到该页你找到了李四的电话(记录),然后你就可以给李四打电话了。
💡tips:为什么叫哈希表呢?因为散列表的英文就是Hash Table,谐音过来就是哈希表,为了方便起见,本文将直接称呼散列为哈希。
3.本质
哈希表的底层结构是数组,哈希表就是基于数组实现的一个数据结构,其意义在于可以根据一个键值Key就可以查找到一个数据在数组中的位置或者下标,从而加快查找的速度。我们可以知道,要想在一个数组里面查找我们想要的元素,我们可以利用顺序查找、折半查找、分块查找等方法(想知道这些方法的实现可以看我的另外一篇文章:查找算法:顺序查找、折半查找、分块查找
但是这些方法都远不及我们的这个哈希表,只需要一个键值就可以直接查找到该数据,因此查找速度十分之快。
哈希冲突(Hash Collision)
1.定义
在理想的情况下,每一个Key通过哈希函数的运算后得出来的值都是不一样的,但现实中,往往会出现两个不同的关键字经过同一个哈希函数的运算后得出来的值相同,这种情况就称之为哈希冲突。
2.举例
假如我们的电话簿有张三和张六这两个人,那么按照我们的哈希函数,也就是法则:取名字的姓的英文并转换为首字母,这个时候张三和张六这两个关键字经过哈希函数的处理之后都是Zhang,指向的都是存储了地址为0的一个数据域,这就造成了哈希冲突。
二、哈希函数的构造
tips:下面的图的数据都是虚构的,目的在于理解各个方法
哈希函数的构造方法有很多种,评价一个哈希函数的好坏我们可以通过不同关键字的冲突次数来评估,一个好的哈希函数产生哈希冲突的次数低,完全不产生哈希冲突的哈希函数也叫完美哈希函数,另外,一个好的哈希函数不会有过于复杂的计算,也就是说,如果你将关键字转换为对应地址的时间过长,那么我们查找数据的时候也会十分慢,因此一个好的哈希函数既要计算快,又要不冲突
直接定址法
这种方法适用于关键字简单且关键字连续的情况
i.举例1
如下图是一个国家不同年龄对应的不同人数的部分数据,我们要通过年龄来得到这个年龄的元素,我们观察年龄可以发现是从0-n岁的,恰好可以对应于一个连续的存储空间,因此我们可以直接把年龄作为地址,也就是:
Hashfunction(age)=age
address ( peoplenumber ) =Hashfunction ( age )
ii.举例2
如下图是一个不同年份对应着的不同人口数量,关键字为不同年份,我们要通过不同年份来得到不同年份对应的人口数量,我们同样观察关键字,发现也是连续的,但并不是从0开始,难道我们用来存储记录的底层数组就只能从下标1979开始来存储记录吗,这显然是浪费内存与愚蠢的,我们这个时候就应该对哈希函数进行一个简单调整,即:
Hashfunction ( year ) = year - 1980
address ( peoplenumber ) = Hashfunction ( year )
iii.总结
直接定址法得到的哈希函数具有函数简单,地址分布均匀,且不会产生冲突的优点,但是需要预先知道关键字的分布情况,适合于查找表较小且关键字连续的情况,即:
Hashfunction ( key ) = A*key+B (A、B为常数)
数字分析法
当关键字中的一部分存在于其他的大部分关键字中,或者说大部分关键字都有着一个相同的部分,这个时候我们在对关键字调用哈希函数的时候我们就可以去掉这一部分,下面的例子就可以很好地说明数字分析法的作用
i.举例
观察下图,我们要通过电话来查找这个号码的号主,因此关键字就是电话,我们对关键字进行观察,我们可以发现所有的电话都是以135为前缀的移动的电话号码,因此我们就可以将这个前缀给他去掉再对其进行哈希函数的调用
ii.总结
这种方法是适用于所有的哈希函数的构建的,因为在去除了相同的部分之后会对我们的hash更加有益,可以直接作为哈希函数的构建方法,也可以作为其中的一种调优方法
除余法与平方法
除余法是最为常见的一种构造方式,具体方法就是选取一个素数(只能被1和自身整除的数),并用关键字去取余,取余后得到的数就作为地址,即:
Hashfunction ( key ) = key % 素数
同样,平方法就是对关键字进行平方操作后得到的数作为地址即:
Hashfunction ( key ) = key * key
其他方法
三、处理哈希冲突
链地址法:
当一个关键字通过哈希函数之后产生的地址值和另外一个不同的关键字通过哈希函数产生的地址值相同时(即 Hashfunction ( key1 ) = Hashfunction ( key2 ) ),这个时候我们并不去寻找下一个地址,而是以当前得到的地址为头节点开辟一个链表空间,然后将发生哈希冲突的键值对存入这个链表中
gif举例
创造链表头数组,每个数组包含一个头节点,若发生哈希冲突则以链表头中的头节点延伸产生链表用来存储经过哈希函数运算之后地址相同的键值对(存储了key和value的一个数据结构),这么说可能有点难懂,通过下面的gif图我相信可以更好的帮助读者理解:
哈希函数采用的是取余法,即:
Address=Hasfunction(Key)
Hashfunction(Key)=Key%7
i.我们对 7:seven 这个键值对进行存储,经过哈希函数之后得到的地址为0
ii.我们对0这个地址进行检查,发现里面没有存储键值对,我们就直接将该键值对存入下标为0的内存空间中
iii.我们对 14:fourteen 这个键值对进行存储,经过哈希函数之后得到的地址为0
iv.我们对 0 这个地址进行检查,发现里面已经存储了键值对了
v.那我们就以这个头节点创建一个链表,并在下一个节点对键值对 14:fourteen 进行存储
vi.同样的我们对 15:fifteen 这个键值对进行存储,最后存储到哈希表下标为1的位置
开放寻址法:
当一个键值对中的关键字通过哈希函数之后产生的地址值和另外一个不同的关键字通过哈希函数产生的地址值相同时(即 Hashfunction ( key1 ) = Hashfunction ( key2 ) ),这个时候key2对应的值还能放进Hashfunction ( key2 )中吗,显然不行,这样就会覆盖点key1所对应的值,因此这个时候我们就去查看Hashfunction ( key2 )的下一个地址,如果可用的话,就把key2的值存入这个新地址中
gif举例
以下图的gif为例我们可以对开放寻址法有更好的理解:
哈希函数采用的是取余法,即:
Address=Hasfunction(Key)
Hashfunction(Key)=Key%7
i.我们对第一个键值对 7:seven 进行存储
ii.经过哈希函数之后我们找到了哈希表中的位置 0
iii.我们对这个位置进行检查,发现没有存储数据,那么我们就将该键值对进行存储
iv.我们对第二个键值对 14:fourteen 进行存储
v.经过哈希函数之后我们找到了哈希表中的位置 0
vi.我们对这个位置进行检查,发现已经存储了数据
vii.我们对当前地址的下一个地址进行检查,发现没有存储数据,那么我们就将该键值对进行存储,如果发现下一个地址也存了数据,那么就继续查看下一个地址直到发现没有存储数据的地址单元
四、STL库中的哈希表使用
在STL标准库中,哈希表是unordered_map,需要在头文件中#include<unordered_map>才能使用,下面我展示几个STL库中常用的哈希表的函数
#include<stdio.h>
#include<iostream>
#include<unordered_map>
using namespace std;
int main()
{
//构造哈希表
unordered_map<int,string> um;//哈希表定义unordered_map<type_key,type_value>,也就是说key是int类型的,value是string类型的
//赋值操作
um[0]="aa";//可通过操作符[]来规定key的对应value,um[key]="value"
um[1]="bb";
um[2]="cc";
um.insert({3,"10"});//map.insert(pair<key_type,value_type>(key,value))
um.insert({4,"29"});
um.emplace(5,"hi");//map.emplace(key,value)
um.emplace(6,"hi1");//emplace比insert效率高
//迭代器操作
//1.通过auto生成迭代器来打印各节点数据
for (auto node:um)//通过auto编译器可以自动识别节点类型
{
cout<<node.first<<":"<<node.second<<endl;//节点第一个数据就是key,第二个数据就是key对应的值
}
//2.通过iterator
for (unordered_map<int,string>::iterator it=um.begin(); it!=um.end(); it++)
{
int key=it->first;
string value=it->second;
cout<<"key为"<<key<<" value为"<<value<<endl;
}
//访问操作
cout<<um[2]<<endl;//通过[key]访问key为2的value
cout<<um.at(0)<<endl;//通过at(key)访问key为0的value
//容量操作
cout<< um.empty()<<endl;//查看是否为空
cout<<um.size()<<endl;//得到哈希表容量
//以key为参数查找哈希表中的value,若查找成功就返回该位置上的迭代器,否则返回um.end()
unordered_map<int,string>::iterator iter;
iter=um.find(2);
cout<<iter->second<<endl;//第二个才是value
//删除某个位置的元素或某个范围内的元素
unordered_map<int, string>::iterator iter_begin = um.begin();
unordered_map<int, string>::iterator iter_end =um.end();
//um.erase(iter_begin); //删除开始位置的元素
um.erase(iter_begin, iter_end); //删除开始位置和结束位置之间的元素
um.erase(5); //删除key为5的键值对
//查找哈希表中元素所存在的桶编号
int positon=um.bucket(5);//查找key5所在的桶的编号
//得到桶的个数
int bucketnum=um.bucket_count();
//得到对应下标的桶内的元素数量
int bucketsize=um.bucket_size(3);
//清空哈希表
um.clear();
return 0;
}
想要看更加详细的STL库哈希表的时候建议看这篇文章,我个人觉得写的不错的:
五、哈希表的实现
1.链地址法
算法实现
对于链地址法我们使用节点作为存储结构,因此我们就需要定义节点类:
节点类:
class node
{
public:
int key;//关键值
int value;//关键值所对应的值
node* next;//指向当前节点的下一个节点的指针
};
因为我们要对哈希表进行操作,因此我们也需要定义一个哈希表类,内部包含了一些成员以及方法:
哈希表类:
class Hashtable
{
public:
node* element;//定义一个链表头指针
void init();//初始化函数
int hashfunc(int key);//哈希函数
void insert(int key,int value);//插入键值对
int find(int key);//通过关键值得到关键值对应的数据
};
初始化函数:
void Hashtable::init()
{
element=new node[maxsize];//通过指针批量创建节点类的实例从而得到链表头数组
for (int i = 0; i < maxsize; i++)//初始化链表头数组中的所有节点
{
element[i].key=empty;//初始化头结点的相关数据
element[i].value=empty;
element[i].next=NULL;
}
}
哈希函数:
这里的哈希函数我们采用的是取余法,选择了7这个素数
int Hashtable::hashfunc(int key)
{
return key%7;
}
插入函数:
void Hashtable::insert(int key,int value)
{
if (element[hashfunc(key)].value==empty)//如果当前key值对应的头节点中未存储数据
{
element[hashfunc(key)].key=key;//那么就直接将该键值对存入
element[hashfunc(key)].value=value;
}
else//如果当前key值对应的头结点中存储了数据说明发生了哈希冲突
{
node* ptr=element[hashfunc(key)].next;//定义一个指针指向头节点的下一个节点
if (ptr==NULL)//如果该指针为空说明这个链表当前只有一个头节点
{
node* newnode=(node*)malloc(sizeof(node));//因此我们就创建一个新的节点用来存键值对
element[hashfunc(key)].next=newnode;//将头节点与新节点相连
element[hashfunc(key)].next->key=key;//对键值对进行存储
element[hashfunc(key)].next->value=value;
element[hashfunc(key)].next->next=NULL;
}
else//如果该链表含有多个节点
{
while (ptr->next!=NULL)//我们就将指针指到最后一个节点
{
ptr=ptr->next;
}
node* newnode=(node*)malloc(sizeof(node));//并创建一个新的节点
ptr->next=newnode;//将最后一个节点与新节点相连
ptr->next->key=key;//并将键值对进行存储
ptr->next->value=value;
ptr->next->next=NULL;
}
}
}
哈希查找函数:
int Hashtable::find(int key)
{
node* ptr=element[hashfunc(key)].next;//生成一个指针指向当前头节点的下一个节点
if (ptr==NULL)//通过指针检查链表是否只有一个头节点
{
if (key==element[hashfunc(key)].key)//直接对该头节点进行检查
{
return element[hashfunc(key)].value;//如果Key值相同就返回value
}
else
{
return ERROR;//否则返回查找失败
}
}
else//链表不只有一个头节点
{
while (ptr!=NULL)//循环检查每个节点的Key值
{
if (ptr->key==key)
{
return ptr->value;//发现相同key值就返回value
}
else
{
ptr=ptr->next;//否则指针移动到下一个节点
}
}
return ERROR;//如果链表遍历完毕都还未返回value说明查找失败
}
}
主函数:
int main()
{
Hashtable ht;
ht.init();
ht.insert(7,111);
ht.insert(14,222);
ht.insert(15,333);
int tempkey;
cin>>tempkey;
cout<<"key:"<<tempkey<<" 对应的值为:"<<ht.find(tempkey)<<endl;
return 0;
}
代码执行结果
全部代码
#include<stdio.h>
#include<iostream>
#define empty 0
#define maxsize 100
#define ERROR -1
using namespace std;
class node
{
public:
int key;//关键值
int value;//关键值所对应的值
node* next;//指向当前节点的下一个节点的指针
};
class Hashtable
{
public:
node* element;//定义一个链表头指针
void init();//初始化函数
int hashfunc(int key);//哈希函数
void insert(int key,int value);//插入键值对
int find(int key);//通过关键值得到关键值对应的数据
};
void Hashtable::init()
{
element=new node[maxsize];//通过指针批量创建节点类的实例从而得到链表头数组
for (int i = 0; i < maxsize; i++)//初始化链表头数组中的所有节点
{
element[i].key=empty;//初始化头结点的相关数据
element[i].value=empty;
element[i].next=NULL;
}
}
int Hashtable::hashfunc(int key)
{
return key%7;
}
void Hashtable::insert(int key,int value)
{
if (element[hashfunc(key)].value==empty)//如果当前key值对应的头节点中未存储数据
{
element[hashfunc(key)].key=key;//那么就直接将该键值对存入
element[hashfunc(key)].value=value;
}
else//如果当前key值对应的头结点中存储了数据说明发生了哈希冲突
{
node* ptr=element[hashfunc(key)].next;//定义一个指针指向头节点的下一个节点
if (ptr==NULL)//如果该指针为空说明这个链表当前只有一个头节点
{
node* newnode=(node*)malloc(sizeof(node));//因此我们就创建一个新的节点用来存键值对
element[hashfunc(key)].next=newnode;//将头节点与新节点相连
element[hashfunc(key)].next->key=key;//对键值对进行存储
element[hashfunc(key)].next->value=value;
element[hashfunc(key)].next->next=NULL;
}
else//如果该链表含有多个节点
{
while (ptr->next!=NULL)//我们就将指针指到最后一个节点
{
ptr=ptr->next;
}
node* newnode=(node*)malloc(sizeof(node));//并创建一个新的节点
ptr->next=newnode;//将最后一个节点与新节点相连
ptr->next->key=key;//并将键值对进行存储
ptr->next->value=value;
ptr->next->next=NULL;
}
}
}
int Hashtable::find(int key)
{
node* ptr=element[hashfunc(key)].next;//生成一个指针指向当前头节点的下一个节点
if (ptr==NULL)//通过指针检查链表是否只有一个头节点
{
if (key==element[hashfunc(key)].key)//直接对该头节点进行检查
{
return element[hashfunc(key)].value;//如果Key值相同就返回value
}
else
{
return ERROR;//否则返回查找失败
}
}
else//链表不只有一个头节点
{
while (ptr!=NULL)//循环检查每个节点的Key值
{
if (ptr->key==key)
{
return ptr->value;//发现相同key值就返回value
}
else
{
ptr=ptr->next;//否则指针移动到下一个节点
}
}
return ERROR;//如果链表遍历完毕都还未返回value说明查找失败
}
}
int main()
{
Hashtable ht;
ht.init();
ht.insert(7,111);
ht.insert(14,222);
ht.insert(15,333);
int tempkey;
cin>>tempkey;
cout<<"key:"<<tempkey<<" 对应的值为:"<<ht.find(tempkey)<<endl;
return 0;
}
2.开放寻址法
在开放寻址法中我们使用数组作为键值对的存储结构,也可以用链表作为存储结构,在这里我使用了两个数组用来分别存储key和value
算法实现
哈希表类:
class Hashtable
{
public:
int v[maxsize];//用来存储value
int k[maxsize];//用来存储key
int hashfunc(int key);//哈希函数
void initHashtable();//初始化函数
void insert(int key,int value);//插入键值对
int find(int key);//哈希查找
};
哈希函数:
int Hashtable::hashfunc(int key)
{
return key%7;
}
初始化哈希表:
void Hashtable::initHashtable()
{
for (int i = 0; i < maxsize; i++)
{
v[i]=empty;//对两个数组进行初始化
k[i]=empty;
}
}
插入键值对:
void Hashtable::insert(int key,int value)
{
int temp=key;
int flag=0;//标志位
while (v[hashfunc(temp)]!=empty)//当发现哈希冲突的时候
{
if (temp==key-1)//先看下面的注释再看这个注释:当到达原本的key值前面的一个地址时说明插入失败
{
flag=1;//标志位变化
break;
}
temp+=1;//地址加一
if (temp==maxsize+1)//如果地址已经到达了最大
{
temp=0;//从数组头开始检查
}
}
if (flag==0)//通过标志位来判断是否插入成功
{
v[hashfunc(temp)]=value;
k[hashfunc(temp)]=key;
}
}
哈希查找:
int Hashtable::find(int key)
{
int flag=0;
int temp=key;
while (k[hashfunc(temp)]!=key)
{
if (temp==key-1)//先看下面的注释再看这个注释:当到达原本的key值前面的一个地址时说明查找失败
{
flag=1;//标志位变化
break;
}
temp+=1;
if (temp==maxsize+1)
{
temp=0;
}
}
if (flag==0)
{
return v[hashfunc(temp)];
}
else
{
return ERROR;//查找失败
}
}
主函数:
int main()
{
Hashtable ht;
ht.initHashtable();
ht.insert(7,111);
ht.insert(14,222);
int key;
cin>>key;
cout<<"key:"<<key<<" 对应的值为:"<<ht.find(key)<<endl;
return 0;
}
全部代码
#include<stdio.h>
#include<iostream>
#define maxsize 100
#define empty 0
#define ERROR -1
using namespace std;
class Hashtable
{
public:
int v[maxsize];//用来存储value
int k[maxsize];//用来存储key
int hashfunc(int key);//哈希函数
void initHashtable();//初始化函数
void insert(int key,int value);//插入键值对
int find(int key);//哈希查找
};
int Hashtable::hashfunc(int key)
{
return key%7;
}
void Hashtable::initHashtable()
{
for (int i = 0; i < maxsize; i++)
{
v[i]=empty;//对两个数组进行初始化
k[i]=empty;
}
}
void Hashtable::insert(int key,int value)
{
int temp=key;
int flag=0;//标志位
while (v[hashfunc(temp)]!=empty)//当发现哈希冲突的时候
{
if (temp==key-1)//先看下面的注释再看这个注释:当到达原本的key值前面的一个地址时说明插入失败
{
flag=1;//标志位变化
break;
}
temp+=1;//地址加一
if (temp==maxsize+1)//如果地址已经到达了最大
{
temp=0;//从数组头开始检查
}
}
if (flag==0)//通过标志位来判断是否插入成功
{
v[hashfunc(temp)]=value;
k[hashfunc(temp)]=key;
}
}
int Hashtable::find(int key)
{
int flag=0;
int temp=key;
while (k[hashfunc(temp)]!=key)
{
if (temp==key-1)//先看下面的注释再看这个注释:当到达原本的key值前面的一个地址时说明查找失败
{
flag=1;//标志位变化
break;
}
temp+=1;
if (temp==maxsize+1)
{
temp=0;
}
}
if (flag==0)
{
return v[hashfunc(temp)];
}
else
{
return ERROR;//查找失败
}
}
int main()
{
Hashtable ht;
ht.initHashtable();
ht.insert(7,111);
ht.insert(14,222);
int key;
cin>>key;
cout<<"key:"<<key<<" 对应的值为:"<<ht.find(key)<<endl;
return 0;
}
代码执行结果
六、总结
👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍
哈希表是一个查找效率非常之高的数据结构,其中我们需要对其原理进行深刻的理解,包括哈希函数的构造、选用,以及哈希冲突的处理方式,另外我强烈建议读者自己试着去实现哈希表,这样子可以体会到其中原理,并且能够深入的理解如何处理哈希冲突,同时也可以巩固链表等相关知识,是百利而无一害的,而且实现起来也十分简单,如果喜欢本文的话麻烦点点赞哦!
👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍👍