- 1【Python小游戏】植物大战僵尸的实现与源码分享_python植物大战僵尸,所有植物
- 2深度访谈：最强开源大模型Llama 3发布，Meta的AGI路径和开源哲学
- 3实践探讨Python如何进行异常处理与日志记录
- 4深入分析Spring Boot2，解决 java.lang.ArrayStoreException异常_springboot启动报错arraystoreexception
- 5数据仓库、数据湖、湖仓一体都是什么意思，究竟有什么区别？
- 6给定一个数组nums，将数组中的元素向右移动k个位置，其中k是非负数。
- 7无处不在的AI：被科技巨头盯上的Agent智能体的崭新时代
- 8MySQL5.7以上版本sql_mode=only_full_group_by问题解决办法_5.7.40 sql mode=only full group by
- 9JSP连接access数据库
- 10git命令-7.推送主分支_* (no branch)的分支推送到主分支
C++之哈希表的使用_c++哈希表用法
赞
踩
C++中的STL提供了hash_map来实现哈希表功能，在介绍hash_map的使用方法之前，我们先从哈希函数和哈希冲突来了解哈希表。
一、 哈希函数
所谓哈希函数就是从关键字（Key）到值（Value）的映射：
V
a
l
u
e
=
H
(
K
e
y
)
Value=H(Key)
Value=H(Key)
值反映了关键字的存储地址。
1、数字分析法
选取关键字中的几位数字作为值，一般选取数字分布比较均匀的几位。
H
(
k
1
k
2
k
3
k
4
k
5
k
6
k
7
)
=
k
2
k
3
k
5
H(k_1 k_2 k_3 k_4 k_5 k_6 k_7)= k_2 k_3 k_5
H(k1k2k3k4k5k6k7)=k2k3k5
2、直接定址法
选取线性函数作为哈希函数
H
(
K
e
y
)
=
a
∗
K
e
y
+
b
H(Key)=a*Key+b
H(Key)=a∗Key+b
3、折叠法
将关键字分成数字相同的几段（最后一段数字可以不够），然后相加得到值。
H
(
k
1
k
2
k
3
k
4
k
5
k
6
k
7
)
=
(
k
1
+
k
4
+
k
7
)
(
k
2
+
k
5
)
(
k
3
+
k
6
)
H(k_1 k_2 k_3 k_4 k_5 k_6 k_7)=( k_1+k_4+k_7)( k_2+k_5)( k_3+k_6)
H(k1k2k3k4k5k6k7)=(k1+k4+k7)(k2+k5)(k3+k6)
k
1
k
2
k
3
k_1 k_2 k_3
k1k2k3
k
4
k
5
k
6
k_4 k_5 k_6
k4k5k6
+
k
7
+ k_7
+k7
4、平方取中法
将关键字求平方之后选取中间的几位作为值
5、除留余数法
关键字除以
P
P
P得到的余数作为值，其中P为小于哈希表长度的最大质数。
H
(
K
e
y
)
=
K
e
y
M
O
D
P
H(Key)=Key \quad MOD \quad P
H(Key)=KeyMODP
6、随机数法
选取一个随机函数作为哈希函数
H
(
K
e
y
)
=
r
a
n
d
o
m
(
K
e
y
)
H(Key)=random(Key)
H(Key)=random(Key)
二、 哈希冲突
对于不同的关键字，经过哈希函数的映射可能得到相同的值，也就是发生了冲突，下面介绍几种解决哈希冲突的方法
1、公共溢出区法
新建一块内存用来存储发生冲突的数据
2、再探测法
当发生冲突时，通过一个函数为关键字寻找新的值：
V
a
l
u
e
=
(
H
(
K
e
y
)
+
d
i
)
M
O
D
L
Value=(H(Key)+d_i) \quad MOD \quad L
Value=(H(Key)+di)MODL
其中
L
L
L为哈希表的长度，根据
d
i
d_i
di的取值不同可以细分为以下三种方法:
-
线性探测法
d i = 1 ， 2 ， ⋯ ， L − 1 d_i=1，2，⋯，L-1 di=1，2，⋯，L−1 -
平方探测法
d i = 1 2 ， − 1 2 ， 2 2 ， − 2 2 ， ⋯ d_i=1^2，-1^2，2^2，-2^2，⋯ di=12，−12，22，−22，⋯ -
随机探测法
这时 d i d_i di取的是一组随机数
3、再哈希法
当发生冲突时，再进行一次哈希函数，当然这个哈希函数可以和前面的相同，也可以不同
V
a
l
u
e
=
R
H
(
H
(
K
e
y
)
)
Value=RH(H(Key))
Value=RH(H(Key))
4、链地址法
链地址法是一种将数组与链表结合的方法，这也是最常用的一种方法，将相同值的不同关键字存放于一个链表中，不同的链表即不同的值构成了一个数组。
三、 unordered_map的使用
1、头文件：
#include< unordered_map>
- 1
2、定义一个哈希表(我们以Key和Value都是int变量为例)：
unordered_map<int,int> Hash;
- 1
3、哈希表的建立有下面几种方法：
Hash[1]=3;
Hash.insert<make_pair(1,3)>;
Hash.insert({ {1,3},{2,4} });
- 1
- 2
- 3
4、迭代器：
unordered_map<int,int>::iterator it;
- 1
5、利用迭代器访问变量：
it->first;
it->second;
- 1
- 2
6、哈希表的查找：
it=Hash.find(1);
- 1
若找不到，返回的是Hash.end();
7、修改哈希表：
Hash[1] = 4;
- 1
8、清除哈希表：
Hash.erase(1);
Hash.clear();
- 1
- 2
以上我们介绍了哈希表的几个基本用法，详细的介绍可以访问下方的网址：
https://docs.microsoft.com/en-us/previous-versions/visualstudio/visual-studio-2008/bb982522(v=vs.90)
