我们以一道例题来举例:哈希表。
这道题目是这么做的:
关键字
k
k
k除以
m
m
m,取余数作为在
H
a
s
h
Hash
Hash表中的位置。
函数表达式可以写成:
哈希函数
h
(
k
)
=
k
h(k) = k
h(k)=k
m
o
d
mod
mod
m
m
m
一般
m
m
m 选择为素数,建议选择
2
e
5
+
10
2e5+10
2e5+10。
代码:
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int, int>
#define For(i, a, b) for(int i = a;i <= b;i++)
const int N = 2e5 + 3;
const int null = 0x3f3f3f3f;
int n, h[N];
int get(int x){
int idx = (x % N + N) % N;
while (h[idx] != null && h[idx] != x){
idx = (idx == N ? 0 : idx + 1);
}
return idx;
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
memset(h, 0x3f, sizeof h);
int n, x;
string op;
cin >> n;
while (n--){
cin >> op;
cin >> x;
if (op[0] == 'I'){
h[get(x)] = x;
}else{
cout << (h[get(x)] == x ? "Yes\n" : "No\n");
}
}
return 0;
}
代码:
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define PII pair<int, int>
#define For(i, a, b) for(int i = a;i <= b;i++)
const int N = 2e5 + 3;
int head[N], val[N], nxt[N], idx;
void add(int x){
int k = (x % N + N) % N;
val[idx] = x;
nxt[idx] = head[k];
head[k] = idx++;
}
bool get(int x){
int k = (x % N + N) % N;
int res = head[k];
while (res != -1){
if (val[res] == x){
return 1;
}
res = nxt[res];
}
return 0;
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
memset(head, -1, sizeof head);
int n;
cin >> n;
while (n--){
char op;
cin >> op;
int x;
cin >> x;
if (op == 'I'){
add(x);
}else{
if (get(x)){
cout << "Yes\n";
}else{
cout << "No\n";
}
}
}
return 0;
}
字符串
H
a
s
h
Hash
Hash(字符串前缀
H
a
s
h
Hash
Hash法),把字符串
s
s
s 变成一个
p
p
p 进制数字(
H
a
s
h
Hash
Hash值),实现不同的字符串映射到不同的数字。
字符串
s
s
s 中 的每个字符本质上就是一个数字(
A
S
C
I
I
ASCII
ASCII值)。
s
=
s
0
s
1
s
2
s
3
?
?
?
s
n
?
1
s = s_0 s_1s_2s_3···s_n - 1
s=s0?s1?s2?s3????sn??1
h
(
s
)
=
s
0
?
p
n
?
1
+
s
1
?
p
n
?
2
+
?
?
?
+
s
n
?
1
?
p
0
h(s) = s_0·p^{n-1}+s_1·p^{n-2}+···+s_n-1·p^0
h(s)=s0??pn?1+s1??pn?2+???+sn??1?p0
代码:
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int unsigned long long
#define PII pair<int, int>
#define For(i, a, b) for(int i = a;i <= b;i++)
const int N = 1e5 + 10;
int n, m;
char s[N];
int h[N], p[N];
int get(int l, int r){
return h[r] - h[l - 1] * p[r - l + 1];
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m >> s + 1;
h[0] = 0;
p[0] = 1;
For (i, 1, n){
h[i] = h[i - 1] * 131 + s[i];
p[i] = p[i - 1] * 131;
}
while (m--){
int l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
if ((get(l1, r1)) == get(l2, r2)) {
cout << "Yes\n";
}else{
cout << "No\n";
}
}
return 0;
}
今天的文章就到这里啦,三连必回哦!