- 1SpringBoot整合Lombok以及各种使用技巧
- 202、Java 数据结构：时间复杂度与空间复杂度_java 线性时间复杂度
- 3EduCoder_web实训作业--JavaScript学习手册十二：Math、日期和异常处理_javascript学习手册十二:math、日期和异常处理
- 4AI大模型低成本快速定制法宝：RAG和向量数据库_rag ai
- 5Unable to connect to ADB....for IPv4 or IPv6 respectively 的Android Studio问题解决_adb连接ipv6地址
- 63D gaussian splatting 代码阅读(一)：Forward_3d gaussian splatting 加速渲染源码解读forward.cu
- 7爬虫scrapy-将某网站内的试题爬取出来并保存为本地markdown文件_爬取题库
- 8Linux：详解 用户，用户组的解释创建等。_linux用户
- 9pandas 读取CSV报错_pandas读csv编码错误
- 10Transformer详解_transformer流程
【数据结构 —— 一文看懂哈希表】_哈希表随机数法
赞
踩
哈希表
什么是哈希表
哈希表是通过哈希函数和冲突处理算法将一组关键字映射到一个有限连续的地址集上，并以关键字在地址集中的映射作为记录在表中的位置，那么这个表称为哈希表。
哈希函数
一、直接定址法
直接根据关键字的信息确定关键字的存储位置的方法称为直接定址法。
通过
H
(
k
e
y
)
=
k
e
y
H(key) = key
H(key)=key 或者
H
(
k
e
y
)
=
a
∗
k
e
y
+
b
H(key) = a*key+b
H(key)=a∗key+b
直接计算得到映射地址的方法。
二、除留余数法
此方法为大多数题目所常考的方法
H
(
k
e
y
)
=
k
e
y
%
m
H(key) = key\%m
H(key)=key%m
m通常为不超过哈希表长度的最大素数。
%
\%
%意为取整除之后的余数
三、随机数法
通过计算机语言中的随机数函数得到一个映射地址，实质上还是一个哈希函数
H
(
k
e
y
)
=
r
a
n
d
o
m
(
k
e
y
)
H(key) = random(key)
H(key)=random(key)
此方法针对于关键字之间长度不同较为有效
处理冲突的算法
什么是冲突?
冲突是指两个不同的关键字经过哈希函数映射后得到同一个哈希地址。一般需要通过处理算法，将后来的关键字安排到新的位置。
一、开放定址法
开放定址意为将哈希表中剩余的空位向冲突的关键字开放，其数学表达形式如下。
H i = ( H ( k e y ) + d i ) % M H_i=(H(key) + d_i)\%M Hi=(H(key)+di)%M
这里H(key)为首次哈希得到的冲突的地址，而
H
i
H_i
Hi为经过
i
i
i次线性探测得到的新地址。
M
M
M为哈希表的长度，
d
i
d_i
di为在地址上的偏移量，
根据
d
i
d_i
di取值形式的不同，将开放定址法分为以下几种。
1.线性探测法
如果经过一次哈希得到的哈希地址是冲突的，那么在此基础上将地址向后移动，寻找空着的位置，此为线性探测法的思想。
d
i
=
(
1
,
2
,
3
,
4
,
.
.
.
,
k
)
d_i = (1,2,3,4,...,k)
di=(1,2,3,4,...,k)
k
≤
M
−
1
k \le M-1
k≤M−1
2.平方探测法
平方探测法则就是将
d
i
d_i
di的值取从0开始的整数的平方。
d
i
=
0
2
,
1
2
,
−
1
2
,
2
2
,
−
2
2
,
.
.
.
d_i=0^2,1^2,-1^2,2^2,-2^2,...
di=02,12,−12,22,−22,...
3.双散列法
再找另外一个哈希函数生成
d
i
d_i
di.
d
i
=
i
∗
H
a
s
h
2
(
k
e
y
)
d_i = i*Hash_2(key)
di=i∗Hash2(key)
如果一次后得到的地址还是冲突的，那么就来两次！
4.伪随机数再散列
当
d
i
d_i
di为伪随机数序列时，开放地址的方法称为伪随机再散列方法。
在C语言中，伪随机函数为
//需要包含头文件 <stdlib.h>
int rand(void);
- 1
- 2
二、拉链法
拉链法是在原有的哈希表的基础上给每一个地址后添加一个指针指向该地址的一个冲突关键字，如果有多个冲突关键字，那么冲突关键字之间形成一个链表，头节点为冲突地址。
三、公共溢出法
假设关键字的最大值为 m m m那么先设置哈希表的大小为 m m m，然后再设立另一个表 O v e r T a b l e OverTable OverTable来接收一次哈希冲突后的关键字，将冲突的关键字依次存入，当查找时出现冲突，就到 O v e r T a b l e OverTable OverTable表中查找溢出关键字。
四、再哈希法
这里注意区别开放定址法中的双散列法，其数学表达式为
H
(
k
e
y
)
=
H
a
s
h
i
(
k
e
y
)
H(key) = Hash_i(key)
H(key)=Hashi(key)
其中
H
a
s
h
i
(
)
Hash_i()
Hashi()是一个以不同哈希函数组成的序列，当出现冲突的时候就换一个哈希函数来产生新的地址，而不是再第一次产生的地址上计算地址偏移量。这是两者的区别
哈希表的查找及其分析
聚集
聚集是哈希表中常出现的一种现象，是同义词冲突的探查序列和非同义词之间不同的探查序列交织在一起，导致关键字查询需要经过较长的探测距离，降低了散列的效率。
装载因子
装载因子既为关键字的数量和哈希表长度之比，表达的是所有关键字都存入哈希表以后，哈希表的装满程度，很多时候，哈希表的平均查找长度和采用什么哈希函数没有关系，而是和装载因子有直接关系，装载因子越大，冲突也就会越多。
