哈希查找的解决冲突

哈希查找的解决冲突,第1张

影响哈希查找效率的一个重要因素是哈希函数本身。当两个不同的数据元素的哈希值相同时,就会发生冲突。为减少发生冲突的可能性,哈希函数应该将数据尽可能分散地映射到哈希表的每一个表项中。解决冲突的方法有以下两种:
(1) 开放地址法
如果两个数据元素的哈希值相同,则在哈希表中为后插入的数据元素另外选择一个表项。
当程序查找哈希表时,如果没有在第一个对应的哈希表项中找到符合查找要求的数据元素,程序就会继续往后查找,直到找到一个符合查找要求的数据元素,或者遇到一个空的表项。
(2) 链地址法
将哈希值相同的数据元素存放在一个链表中,在查找哈希表的过程中,当查找到这个链表时,必须采用线性查找方法。
例3 6是一个简单的哈希查找算法程序,你可以将它和本章结尾的有关代码一起编译连接成一个可执行程序。
例3.6一个简单的哈希查找算法程序
1: #include<stdlibh>
2: #include<stringh>
3: #include listh
4: #include hashh
5:
6: #define HASH_SIZE 1024
7:
8: static listnode_t hashTable[HASH_SIZE];
9:
10: void insert(const char s)
11: {
12: listnode_t ele = newNode((void ) s)
13: unsigned int h = hash(s) % HASH_SIZE;
14:
15: ele->next = hashTable[h]
16: hashTable[h] = ele;
17: }
18:
19: void print (void)
20: {
21: int h;
22:
23: for (h = 0; h < HASH_SIZE; h++)
24: {
25: listnode_t lp = hashTalbe[h];
26:
27: if(lp == NULL)
28: continue;
29: printf([%d] , h);
30: while (lp)
31: {
32: printf(\t'%s' , lp->ustr)
33: lp = ip->next;
34: }
35: putchar ('\n');
36: }
37: }
38:
39: const char search(const char s)
40: {
39: unsigned int h = hash(s) % HASH_SIZE;
42: listnode_t lp = hashTable[h];
43:
44: while (lp)
45: {
46: if (! strcmp (s, lp->ustr))
47: return lp->ustr;
48: lp = lp->next;
49: }
50: return NULL;
51: }
请参见:
3 4 哪一种查找方法最方便
3.5 哪一种查找方法最快
3.8 怎样查找链表中的数据
_____________________________________________
以下是一个简单示例:
#include<iostream>
#include<string>
using namespace std;
#define m 5 //人数
#define n 10 //哈希表长度
#define q 7 //随机数
struct name{
char py;
int k;
};
name namelist[n];
struct hash{
char py;
int k;
int s;
};
hash hashlist[n];
void listname()
{
char f;
int s0,r,i;
namelist[0]py=as;
namelist[1]py=sa;
namelist[2]py=d;
namelist[3]py=f;
namelist[4]py=g;
for(i=0;i<m;i++)
{
s0=0;
f=namelist[i]py;
for(r=0;(f+r)!='\0';r++)
s0+=(f+r);
namelist[i]k=s0;
}
}
void creathash()
{
int i;
for(i=0;i<n;i++)
{
hashlist[i]py=;
hashlist[i]k=0;
hashlist[i]s=0;
}
for(i=0;i<m;i++)
{
int sum=0;
int adr=(namelist[i]k)%q;
int d=adr;
if(hashlist[adr]s==0)
{
hashlist[adr]py=namelist[i]py;
hashlist[adr]k=namelist[i]k;
hashlist[adr]s=1;
}
else
{
while(hashlist[d]k!=0)
{
d=(d+namelist[i]k%5+1)%q;
sum+=1;
}
hashlist[d]py=namelist[i]py;
hashlist[d]k=namelist[i]k;
hashlist[d]s=sum+1;
}
}
}
void find()
{
string nam;
int s0=0,r,sum=1,adr,d;
cout<<请输入姓名的拼音:<<endl;
cin>>nam;;
for(r=0;r<20;r++)
s0+=nam[r];
adr=s0%q;
d=adr;
if(hashlist[adr]k==s0)
cout<<姓名:<<hashlist[d]py<< <<关键字:<<s0<< <<查找长度为: 1<<endl;
else if(hashlist[adr]k==0)
cout<<无此记录!<<endl;
else
{
int g=0;
while(g==0)
{
d=(d+s0%5+1)%q;
sum+=1;
if(hashlist[d]k==0)
{
cout<<无此记录!<<endl;
g=1;
}
if(hashlist[d]k==s0)
{
cout<<姓名:<<hashlist[d]py<< <<关键字:<<s0<< <<查找长度为: 1<<endl;
g=1;
}
}
}
}
void display()
{
int i;
float av=0;
for(i=0;i<n;i++)
{
cout<<姓名:<<hashlist[i]py<< <<关键字:<<hashlist[i]k<<搜索长度:<<hashlist[i]s<<endl;
}
for(i=0;i<7;i++)
{
av+=hashlist[i]s;
}
av/=m;
cout<<平均查找长度:=<<av<<endl;
}
int main()
{
char x;
listname();
creathash();
cout<<d 显示哈希表 f 查找 任意键退出 请选择:<<endl;
while(cin>>x){
if(x=='d'){display(); cout<<endl;}
else if(x=='f'){find();cout<<endl;}
else break;
}
return 0;
}

哈希是通过对数据进行再压缩,提高效率的一种解决方法。但由于通过哈希函数产生的哈希值是有限的,而数据可能比较多,导致经过哈希函数处理后仍然有不同的数据对应相同的索引值。这时候就产生了 哈希冲突 ( 两个值都需要同一个地址索引位置 )。

装填因子(装填因子=数据总数 / 哈希表长)、哈希函数、处理冲突的方法

其实也就是哈希表的实现 。

1开放地址方法(再散列法)

可以通俗理解为所有的地址都对所有的数值开放,而不是链式地址法的封闭方式,一个数值固定在一个索引地址位置。

p1=hash(key)如果冲突就在p1地址的基础上+1或者散列处理,p2=hash(p1)

(1)线性探测

按顺序决定值时,如果某数据的值已经存在,则在原来值的基础上往后加一个单位,直至不发生哈希冲突。

(2)再平方探测

按顺序决定值时,如果某数据的值已经存在,则在原来值的基础上先加1的平方个单位,若仍然存在则减1的平方个单位。随之是2的平方,3的平方等等。直至不发生哈希冲突。

和线性探测相比就是改变探测了步长。因为如果都是+1来探测在数据量比较大的情况下,效率会很差。

(3)伪随机探测

按顺序决定值时,如果某数据已经存在,通过随机函数随机生成一个数,在原来值的基础上加上随机数,直至不发生哈希冲突。

2链式地址法(HashMap的哈希冲突解决方法)

对于 相同的值,使用链表进行连接 。使用数组存储每一个链表。

优点:

(1)拉链法 处理冲突简单,且无堆积现象 ,即非同义词决不会发生冲突,因此平均查找长度较短;

(2)由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;

(3)开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;

       (4)在用拉链法构造的散列表中,删除结点的 *** 作易于实现。只要简单地删去链表上相应的结点即可。

        缺点:

指针占用较大空间时,会造成空间浪费 ,若空间用于增大散列表规模进而提高开放地址法的效率。

3建立公共溢出区

建立公共溢出区存储所有哈希冲突的数据。

4再哈希法

对于冲突的哈希值再次进行哈希处理,直至没有哈希冲突。

可以理解为p=hash(key)如果冲突就p=hash2(key)

参考文献:

文章1

视频(非常易懂)

27 mod 8 = 3, 17 mod 8 = 1, 9 mod 8 = 1, 19 mod 8 = 3, 16 mod 8 = 0, 43 mod 8 = 3, 53 mod 8 = 5, 8 mod 8 = 0, 63 mod 8 = 7,于是链地址法解决冲突的哈希表为:

后面的冲突的关键字一般插入在链表的表头

HashMap在实际开发中用到的频率非常高,面试中也是热点。所以决定写一篇文章进行分析,希望对想看源码的人起到一些帮助,看之前需要对链表比较熟悉。
以下都是我自己的理解,欢迎讨论,写的不好轻喷。

HashMap中的数据结构为散列表,又名哈希表。在这里我会对散列表进行一个简单的介绍,在此之前我们需要先回顾一下 数组 链表 的优缺点。

数组和链表的优缺点取决于他们各自在内存中存储的模式,也就是直接使用 顺序存储 链式存储 导致的。无论是数组还是链表,都有明显的缺点。而在实际业务中,我们想要的往往是寻址、删除、插入性能都很好的数据结构,散列表就是这样一种结构,它巧妙的结合了数组与链表的优点,并将其缺点弱化(并不是完全消除)

散列表的做法是将key映射到数组的某个下标,存取的时候通过key获取到下标(index)然后通过下标直接存取。速度极快,而将key映射到下标需要使用 散列函数 ,又名 哈希函数 。说到哈希函数可能有人已经想到了,如何将key映射到数组的下标。

图中计算下标使用到了以下两个函数:

值得注意的是,下标并不是通过hash函数直接得到的,计算下标还要对hash值做index()处理。
Ps:在散列表中,数组的格子叫做 ,下标叫做 桶号 ,桶可以包含一个key-value对,为了方便理解,后文不会使用这两个名词。

以下是哈希碰撞相关的说明:

以下是下标冲突相关的说明:

很多人认为哈希值的碰撞和下标冲突是同一个东西,其实不是的,它们的正确关系是这样的, hashCode发生碰撞,则下标一定冲突;而下标冲突,hashCode并不一定碰撞

上文提到,在jdk18以前HashMap的实现是 散列表 = 数组 + 链表 ,但是到目前为止我们还没有看到链表起到的作用。事实上,HashMap引入链表的用意就是解决下标冲突。

下图是引入链表后的散列表:

如上图所示,左边的竖条,是一个大小为16的数组,其中存储的是链表的头结点,我们知道,拥有链表的头结点即可访问整个链表,所以认为这个数组中的每个下标都存储着一个链表。其具体做法是,如果发现下标冲突,则 后插入的节点以链表的形式追加到前一个节点的后面

这种使用链表解决冲突的方法叫做: 拉链法 (又叫链地址法)。HashMap使用的就是拉链法,拉链法是冲突发生以后的解决方案。

Q:有了拉链法,就不用担心发生冲突吗?
A:并不是!由于冲突的节点会不停的在链表上追加,大量的冲突会导致单个链表过长,使查询性能降低。所以一个好的散列表的实现应该从源头上减少冲突发生的可能性,冲突发生的概率和哈希函数返回值的均匀程度有直接关系,得到的哈希值越均匀,冲突发生的可能性越小。为了使哈希值更均匀,HashMap内部单独实现了hash()方法。

以上是散列表的存储结构,但是在被运用到HashMap中时还有其他需要注意的地方,这里会详细说明。

现在我们清楚了散列表的存储结构,细心的人应该已经发现了一个问题:Java中数组的长度是固定的, 无论哈希函数是否均匀,随着插入到散列表中数据的增多,在数组长度不变的情况下,链表的长度会不断增加 。这会导致链表查询性能不佳的缺点出现在散列表上,从而使散列表失去原本的意义。为了解决这个问题,HashMap引入了扩容与负载因子。

以下是和扩容相关的一些概念和解释:

Ps: 扩容要重新计算下标 扩容要重新计算下标 扩容要重新计算下标 ,因为下标的计算和数组长度有关,长度改变,下标也应当重新计算。

在18及其以上的jdk版本中,HashMap又引入了红黑树。

红黑树的引入被用于替换链表,上文说到,如果冲突过多,会导致链表过长,降低查询性能,均匀的hash函数能有效的缓解冲突过多,但是并不能完全避免。所以HashMap加入了另一种解决方案,在往链表后追加节点时,如果发现链表长度达到8,就会将链表转为红黑树,以此提升查询的性能。

哈希表(Hash Table) :通过键 key 和一个映射函数 Hash(key) 计算出对应的值 value,把关键码值映射到表中一个位置来访问记录,以加快查找的速度。
哈希函数(Hash Function) :将哈希表中元素的关键键值映射为元素存储位置的函数。
哈希冲突(Hash Collision) :不同的关键字通过同一个哈希函数可能得到同一哈希地址。
哈希表的两个核心问题是: 「哈希函数的构建」 「哈希冲突的解决方法」

常用的哈希函数方法有:直接定址法、除留余数法、平方取中法、基数转换法、数字分析法、折叠法、随机数法、乘积法、点积法等。
常用的哈希冲突的解决方法有两种:开放地址法和链地址法。

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j,使得 abs(nums[i] - nums[j]) <= t ,同时又满足 abs(i - j) <= k 。

如果存在则返回 true,不存在返回 false。

给定两个数组 nums1 和 nums2 ,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

给你两个整数数组 nums1 和 nums2 ,请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数,应与元素在两个数组中都出现的次数一致(如果出现次数不一致,则考虑取较小值)。可以不考虑输出结果的顺序。

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ,验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)

力扣217
力扣389
力扣496

内容参考: >

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/yw/13408842.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023-07-30
下一篇 2023-07-30

发表评论

登录后才能评论

评论列表(0条)

保存