哈希表链地址法解决冲突（字典与哈希表（HashMap））

本文目录

• 字典与哈希表（HashMap）
• 用链表和数组实现HASH表，几种碰撞冲突解决方
• 一文理解哈希冲突四种解决方法
• 哈希查找的解决冲突
• 构建哈希表常见的解决冲突的方法：拉链法和线性探测法
• 解决hash冲突的三个方法
• 线性探测再散列技术是如何解决冲突的
• Python数据结构-哈希表（Hash Table）

字典与哈希表（HashMap）

哈希表的存储方式是以数组为基础，每个元素是一个链表，链表上的元素的查找是根据特定的哈希算法决定的，并尽量避免哈希冲突。

哈希表解决冲突的方案：

三种：线性探测再散列、平方探测再散列、随机探测再散列

（表格解释：从前向后插入数据，如果插入位置已经占用，发生冲突，冲突的另起一行，计算地址，直到地址可用，后面冲突的继续向下另起一行。最终结果取最上面的数据（因为是最“占座”的数据））

产生hash冲突后在存储数据后面加一个指针，指向后面冲突的数据
上面的例子，用链地址法则是下面这样：

没找到想要的？点击
参考HashMap 查看更多HashMap精讲

用链表和数组实现HASH表，几种碰撞冲突解决方

1.开放地址法
开放地执法有一个公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k《=m-1)
其中，m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,…m-1，称线性探测再散列。
如果di取1，则每次冲突之后，向后移动1个位置.如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,…k*k,-k*k(k《=m/2)，称二次探测再散列。
如果di取值可能为伪随机数列。称伪随机探测再散列。
2.再哈希法
当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。
比如上面第一次按照姓首字母进行哈希，如果产生冲突可以按照姓字母首字母第二位进行哈希，再冲突，第三位，直到不冲突为止
3.链地址法（拉链法）
将所有关键字为同义词的记录存储在同一线性链表中。
4.建立一个公共溢出区
假设哈希函数的值域为用以存储发生冲突的记录。

一文理解哈希冲突四种解决方法

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

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

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

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=hash3(key)....

参考文献：

文章1

视频（非常易懂）

哈希查找的解决冲突

影响哈希查找效率的一个重要因素是哈希函数本身。当两个不同的数据元素的哈希值相同时，就会发生冲突。为减少发生冲突的可能性，哈希函数应该将数据尽可能分散地映射到哈希表的每一个表项中。解决冲突的方法有以下两种：
(1) 开放地址法
如果两个数据元素的哈希值相同，则在哈希表中为后插入的数据元素另外选择一个表项。
当程序查找哈希表时，如果没有在第一个对应的哈希表项中找到符合查找要求的数据元素，程序就会继续往后查找，直到找到一个符合查找要求的数据元素，或者遇到一个空的表项。
(2) 链地址法
将哈希值相同的数据元素存放在一个链表中，在查找哈希表的过程中，当查找到这个链表时，必须采用线性查找方法。
例3. 6是一个简单的哈希查找算法程序，你可以将它和本章结尾的有关代码一起编译连接成一个可执行程序。
例3．6一个简单的哈希查找算法程序
1: #include《stdlib.h》
2: #include《string.h》
3: #include list.h
4: #include hash.h
5:
6: #define HASH_SIZE 1024
7:
8: static listnode_t *hashTable;
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
16: hashTable = 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;
26:
27: if(lp == NULL)
28: continue;
29: printf( , h);
30: while (lp)
31: {
32: printf(\t’%s’ , lp-》u.str)
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;
43:
44: while (lp)
45: {
46: if (! strcmp (s, lp-》u.str))
47: return lp-》u.str;
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;
struct hash{
char *py;
int k;
int s;
};
hash hashlist;
void listname()
{
char *f;
int s0,r,i;
namelist.py=as;
namelist.py=sa;
namelist.py=d;
namelist.py=f;
namelist.py=g;
for(i=0;i《m;i++)
{
s0=0;
f=namelist.py;
for(r=0;*(f+r)!=’\0’;r++)
s0+=*(f+r);
namelist.k=s0;
}
}
void creathash()
{
int i;
for(i=0;i《n;i++)
{
hashlist.py=;
hashlist.k=0;
hashlist.s=0;
}
for(i=0;i《m;i++)
{
int sum=0;
int adr=(namelist.k)%q;
int d=adr;
if(hashlist.s==0)
{
hashlist.py;
hashlist.k;
hashlist.s=1;
}
else
{
while(hashlist.k!=0)
{
d=(d+namelist.k%5+1)%q;
sum+=1;
}
hashlist.py;
hashlist.k;
hashlist.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;
adr=s0%q;
d=adr;
if(hashlist.k==s0)
cout《《姓名:《《hashlist.py《《 《《关键字:《《s0《《 《《查找长度为: 1《《endl;
else if(hashlist.k==0)
cout《《无此记录！《《endl;
else
{
int g=0;
while(g==0)
{
d=(d+s0%5+1)%q;
sum+=1;
if(hashlist.k==0)
{
cout《《无此记录！《《endl;
g=1;
}
if(hashlist.k==s0)
{
cout《《姓名:《《hashlist.py《《 《《关键字:《《s0《《 《《查找长度为: 1《《endl;
g=1;
}
}
}
}
void display()
{
int i;
float av=0;
for(i=0;i《n;i++)
{
cout《《姓名:《《hashlist.s《《endl;
}
for(i=0;i《7;i++)
{
av+=hashlist.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;
}

构建哈希表常见的解决冲突的方法：拉链法和线性探测法

影响哈希查找效率的一个重要因素是哈希函数本身。当两个不同的 数据元素 的 哈希值 相同时，就会发生冲突。为减少发生冲突的可能性，哈希函数应该将数据尽可能分散地映射到 哈希表 的每一个表项中。解决冲突的方法有以下两种：

所谓开放定址法，即由关键码得到的哈希地址一旦产生了冲突，也就是说，该地址已经存放了数据元素。我们需要寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。常用的找空哈希地址方法有下列三种。

47，7，11，16，92均是由哈希函数得到的没有冲突的哈希地址，因而是直接存入的。Hash(29)=7，哈希地址上冲突，需寻找下一个空的哈希地址：
H 1 = ( Hash(29) + 1 ) % 11 = 8，哈希地址8为空，所以将29存入。
另外，22，8同样在哈希地址上有冲突，也是由 找到空的哈希地址的；而Hash(3)=3，哈希地址上冲突，因为：
H 1 = ( Hash(3) + 1 ) % 11 = 4，仍然冲突
H 2 = ( Hash(3) + 2 ) % 11 = 5，仍然冲突
H 3 = ( Hash(3) + 3 ) % 11 = 6，找到空的哈希地址，存入。
线性探测法可能使第i个哈希地址的同义词存入第i+1个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词……因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。为此，可采用二次探测法，或再哈希函数探测法，以改善“堆积”问题。

与关键码寻找空的哈希地址只有3这个关键码不同，Hash(3)=3，哈希地址上冲突，由
H 1 = ( Hash(3) + ) % 11 = 4，仍然冲突
H 2 = ( Hash(3) - ) % 11 = 2，找到空的哈希地址，存入。

将 哈希值 相同的数据元素存放在一个 链表 中，在查找 哈希表 的过程中，当查找到这个链表时，必须采用线性查找方法。这样的好处是，不怕冲突多；缺点是降低了散列结构的随机存储性能。本质是用单链表结构辅助散列结构的不足。
链地址法又称拉链法，设哈希函数得到的哈希地址域在区间上，以每个哈希地址作为一个指针，指向一个链，即分配指针数组：
ElemType eptr；
建立m个空链表，由哈希函数对关键码转换后，映射到同一哈希地址i的同义词均加入 eptr指向的链表中。
对关键码序列为 {47，7，29，11，16，92，22，8，3，50，37，89，94，21}，哈希函数为Hash(key)=key % 11，用拉链法处理冲突，建表下所示。
设哈希函数产生的哈希地址集为，则分配两个表：
一个基本表ElemType base_tbl；每个单元只能存放一个元素。
一个溢出表ElemType over_tbl；只要关键码对应的哈希地址在基本表上产生冲突，则所有这样的元素一律存入该表中。
查找时，对给定值kx通过哈希函数计算出哈希地址i，先与基本表的base_tbl单元比较，若相等，查找成功；否则，再到溢出表中进行查找。

解决hash冲突的三个方法

通过构造性能良好的哈希函数，可以减少冲突，但一般不可能完全避免冲突，因此解决冲突是哈希法的另一个关键问题。创建哈希表和查找哈希表都会遇到冲突，两种情况下解决冲突的方法应该一致。下面以创建哈希表为例，说明解决冲突的方法。常用的解决冲突方法有以下四种：

开放定址法

这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：

其中H（key）为哈希函数，m 为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。主要有以下三种：

线性探测再散列

这种方法的特点是：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。

二次探测再散列

这种方法的特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活。

伪随机探测再散列

具体实现时，应建立一个伪随机数发生器，（如i=(i+p) % m），并给定一个随机数做起点。

例如，已知哈希表长度m=11，哈希函数为：H（key）= key % 11，则H（47）=3，H（26）=4，H（60）=5，假设下一个关键字为69，则H（69）=3，与47冲突。

如果用线性探测再散列处理冲突，下一个哈希地址为H1=（3 + 1）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 + 2）% 11 = 5，还是冲突，继续找下一个哈希地址为H3=（3 + 3）% 11 = 6，此时不再冲突，将69填入5号单元。

如果用二次探测再散列处理冲突，下一个哈希地址为H1=（3 + 12）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 - 12）% 11 = 2，此时不再冲突，将69填入2号单元。

如果用伪随机探测再散列处理冲突，且伪随机数序列为：2，5，9，……..，则下一个哈希地址为H1=（3 + 2）% 11 = 5，仍然冲突，再找下一个哈希地址为H2=（3 + 5）% 11 = 8，此时不再冲突，将69填入8号单元。

再哈希法

这种方法是同时构造多个不同的哈希函数：

当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

链地址法

这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

建立公共溢出区

这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

优缺点

开放散列（open hashing）/ 拉链法（针对桶链结构）

优点：

缺点：

封闭散列（closed hashing）/ 开放定址法

优点：

缺点：

线性探测再散列技术是如何解决冲突的

线性探测再散列也称杂凑技术。是一种较快的查找技术。

线性探测再散列是哈希表解决冲突的一种计算方法，Hi=(H(key)+di)%m，i=1,2,……k(k《=m-1)，H(key)哈希函数，m哈希表长，di增量序列当，di值可能为1,2,3,...m-1，称线性探测再散列，用该方法处理冲突的方法：开放寻址法、再散列法和链地址法（拉链法）。

解决冲突的方法一般有线性探测再散列法、随机探测法、再哈希法、链地址法等，其中线性再散列法较简单，其计算公式为：Hi＝（H（K）+di）MOD p式中di＝1，2，…

常用的哈希函数

1.直接定址法。仅适合于：地址集合的大小 == 关键字集合的大小。

2.数字分析法。对关键字进行分析，取关键字的若干位或其组合作哈希地址。仅适合于：能预先估计出全体关键字的每一位上各种数字出现的频度。

3.平方取中法。以关键字的平方值的中间几位作为存储地址。

4.折叠法。将关键字分割成位数相同的几部分，然后取这几部分的叠加和(舍去进位)做哈希地址。移位叠加/间界叠加。适合于: 关键字的数字位数特别多，且每一位上数字分布大致均匀情况。

5.除留余数法。取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key%p，p《=m。

6.随机数法。取关键字的伪随机函数值作哈希地址，即H(key)=random(key)，适于关键字长度不等的情况。

以上内容参考：线性探测再散列-学术百科-知网空间

Python数据结构-哈希表（Hash Table）

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

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

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

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

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

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

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

力扣217
力扣389
力扣496

***隐藏网址***