哈希（哈希表的应用）

145 阅读 0 评论 96 点赞

我是靠谱客的博主俭朴蜜蜂，这篇文章主要介绍哈希（哈希表的应用），现在分享给大家，希望可以做个参考。

将一个由若干个不同正整数构成的整数序列插入到一个哈希表中，然后输出输入数字的位置。

哈希函数定义为 H(key)=key%TSize，其中 TSize 是哈希表的最大大小。

利用只具有正增量的二次探测法来解决冲突。

注意，哈希表的大小最好是素数，如果用户给出的最大大小不是素数，则必须将表大小重新定义为大于用户给出的大小的最小素数。

输入格式

第一行包含两个整数 MSize和 N，分别表示用户定义的表的大小以及输入数字的数量。

第二行包含 N个不同的正整数，数字之间用空格隔开。

输出格式

在一行中，输出每个输入数字的相应位置（索引从 0 开始），数字之间用空格隔开，行尾不得有多余空格。

如果无法插入某个数字，则输出 -

数据范围

1≤MSize≤10^4,

1≤N≤MSize,

输入数字均在 [1,10^5]范围内。

输入样例：

复制代码

输出样例：

复制代码

1
0 1 4 -

题解

复制代码

#include<iostream>
#include<vector>
#include<bits/stdc++.h>
typedef long long int ll;
const int N=1e5+10;
using namespace std;
ll str[N];
int main(){
    ll n,m,a,t=0,x,c=0;
    vector<ll> mp;
    memset(str,0,sizeof(str));
    cin>>m>>n;
    for(int i=0;i<n;i++){
        cin>>a;
        mp.push_back(a);
    }
    if(m==1)
    m=2;
    else{
        for(int i=m;;i++){
        t=0;
        for(int j=2;j<i;j++){
            if(i%j==0){
                t=1;
                break;
            }
        }
        if(t==0){
            m=i;
            break;
        }
    }
    }
    for(int i=0;i<n;i++){
        t=mp[i]%m;
        if(str[t]==0){
            cout<<t<<" ";
            str[t]=1;
        }
        else{
            c=0;
            for(int j=1;j<m;j++){
                x=(t+j*j)%m;
                if(str[x]==0){
                    c=1;
                    cout<<x<<" ";
                    str[x]=1;
                    break;
                } 
            }
            if(c==0)
            cout<<"-"<<" ";
        }
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<vector>
#include<bits/stdc++.h>
typedef long long int ll;
const int N=1e5+10;
using namespace std;
ll str[N];
int main(){
    ll n,m,a,t=0,x,c=0;
    vector<ll> mp;
    memset(str,0,sizeof(str));
    cin>>m>>n;
    for(int i=0;i<n;i++){
        cin>>a;
        mp.push_back(a);
    }
    if(m==1)
    m=2;
    else{
        for(int i=m;;i++){
        t=0;
        for(int j=2;j<i;j++){
            if(i%j==0){
                t=1;
                break;
            }
        }
        if(t==0){
            m=i;
            break;
        }
    }
    }
    for(int i=0;i<n;i++){
        t=mp[i]%m;
        if(str[t]==0){
            cout<<t<<" ";
            str[t]=1;
        }
        else{
            c=0;
            for(int j=1;j<m;j++){
                x=(t+j*j)%m;
                if(str[x]==0){
                    c=1;
                    cout<<x<<" ";
                    str[x]=1;
                    break;
                } 
            }
            if(c==0)
            cout<<"-"<<" ";
        }
    }
    return 0;
}