29_哈希冲突和解决方法1
需积分: 0 81 浏览量
2022-08-03
13:04:52
上传
评论
收藏 737KB PDF 举报
问
题
哈
希
冲
突
及
其
解
决
⽅
法
是
⾯
试
中
的
常
⻅
问
题
之⼀
，
需
要
掌
握
⼀下
。
这
节
内
容
的
概
念
偏
多
，
为
了
不
造
成
阅
读
疲
劳
，
可
能
会
适
当
地
简
写
⼀
些
，
如
果
想
深
⼊
理
解
的
话
，
可
以
看看
本
⽂
最
后
的
参
考
博
客
。
哈
希
表
在
处
理
哈
希
冲
突
之
前
，
⾸
先
得
清
楚
什
么
是
哈
希
表
，
以
及
哈
希
函
数
如
何
产
⽣
的
。
哈
希
表
（
hash table
）
是
⼀
种
通
过
关
键
字
（
key
）
和
值
（
value
）
进
⾏
访
问
的
数
据
结
构
。
既
然
要
访
问
，
那
肯
定
需
要
知
道
访
问
的
内
容
存
放
在
哪
⾥
，
所
以
这
就
需
要
通
过
⼀
种
映
射
关
系
将
访
问
元
素
的
关
键
字
和
元
素
的
存
储
地址
关
联
起
来
，
⽽
这
种
映
射
关
系
就
是
通
过
哈
希
函
数
来
实
现
的
。
哈
希
函
数
在
元
素
的
关
键
字
k
和
元
素
的
存
储
位
置
p
之
间
建
⽴
⼀个
对
应
关
系
f
，
使
得
，
这
个
对
应
关
系
f
就
称
为
哈
希
函
数
。
按
照
这
种
对
应
关
系
，
在
创
建
哈
希
表
时
，
将
关
键
字
为
k
的
元
素
存
放
在地址
为
的
单
元
上
；
之
后
若
需
要
查
找
关
键
字
k
时
，
再
利
⽤
哈
希
函
数
计
算
出
该
元
素
的
存
储
位
置
，
就
可
以
直
接
获
取
到
该
元
素
了
。
（
这
应
该
也
是
为
什
么
哈
希
查
找
时
间
复
杂
度
为
的
原
因
吧
）
那
我
们
怎
么
知
道
这
个
映
射
关
系
f
是
什
么
呢
？
那
就
需
要
⾃
⼰
构
造
⼀个
这
样
的
哈
希
函
数
了
。
哈
希
函
数
的
构
造
原
则
：
①
函
数
本
⾝
便
于
计
算
；
②
计
算
出
来
的
地址
分
布
均
匀
，
即
对
任
⼀
关
键
字
，
对
应
不
同
地址
的
概
率
相
等
，
⽬的
是
尽
可
能
减
少
冲
突
。
接
下
来
介
绍
5
种
构
造
哈
希
函
数
的
⽅
法
：（
具
体
原
理
不
展
开
讲
述
了
，
有
需
要
了
解
可
以
看看
参
考
博
客
，
担
⼼
⾯
试
问
这
么
详
细
的
话
可
以
记
住
其
中⼀两
种
⽅
法
应
该
就
够
了
，
例
如
除
留
余
数
法
和
伪
随
机
数
法
，
其
他
的
了
解
即
可
）
1.
数
字
分
析
法
如
果
事
先
知
道
关
键
字
集
合
，
并
且
每
个
关
键
字
的
位
数
⽐
哈
希
表
的
地址
码
位
数
多
时
，
可
以从
关
键
字
中
选
出分
布
较
均
匀
的
若
⼲
位
，
构
成
哈
希
地址
。
2.
平
⽅
取
中
法
当
⽆
法
确
定
关
键
字
中
哪
⼏
位
分
布
较
均
匀
时
，
可
以
先
求
出
关
键
字
的
平
⽅
值
，
然
后
按
需
要
取
平
⽅
值
的
中
间
⼏
位作
为
哈
希
地址
。
3.
分
段
叠
加
法
这
种
⽅
法
是
按
哈
希
表
地址
位
数
将
关
键
字
分
成
位
数
相
等
的
⼏
部
分
（
最
后
⼀
部
分
可
以
较
短
），
然
后
将
这
⼏
部
分
相
加
，
舍
弃
最
⾼
进
位
后
的
结
果
就
是
该
关
键
字
的
哈
希
地址
。
4.
除
留
余
数
法
假
设
哈
希
表
⻓
为
，
为
⼩
于
等
于
的
最
⼤
素
数
，
则
哈
希
函
数
为
：
其
中 为
取
余
运
算
评论0