以空间换时间——散列思想

以空间换时间作散列查找

1.简单版：查找数字

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

const int MAXSIZE=100;

//m个数字{x,y,z...}在n个数字{a,b,c...}中是否出现以及出现的次数
int main(){
    int n,m;
    int num;
    scanf("%d",&n);
    int hashTable[MAXSIZE];
    memset(hashTable,0,sizeof(hashTable));

    for(int i=0;i<n;++i){
        scanf("%d",&num);
        hashTable[num]++;
    }
    scanf("%d",&m);
    for(int i=0;i<m;++i){
        scanf("%d",&num);
        if(hashTable[num]!=0){
            printf("%d EXIT!\t%d times\n",num,hashTable[num]);
        }else{
            printf("%d NOT EXIT!\n",num);
        }
    }
    return 0;


}

2.升级版：查找字符串

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

const int MAXSIZE=62*62*62+10;

//m个字符串{x,y,z...}在n个字符串{a,b,c...}中是否出现以及出现的次数
//字符串组成：[a-z],[A-z],[0-9],一共62个字符
//每个字符串个数为3
int hashFunc(char str[],int len){
    int num=0;
    for(int i=0;i<len;++i){
        if('a'<=str[i]&&str[i]<='z'){
            num=num*36+(str[i]-'a');
        }
        else if('A'<=str[i]&&str[i]<='Z'){
            num=num*36+(str[i]-'A'+26);
        }
        else if('0'<=str[i]&&str[i]<='9'){
            num=num*36+(str[i]-'0'+26);
        }
    }
    return num;
}

int main(){
    int n,m;
    char str[100][5],temp[5];
    scanf("%d",&n);
    int hashTable[MAXSIZE];
    memset(hashTable,0,sizeof(hashTable));

    for(int i=0;i<n;++i){
        scanf("%s",str[i]);
        int num=hashFunc(str[i],3);
        hashTable[num]++;
    }
    scanf("%d",&m);
    for(int i=0;i<m;++i){
        scanf("%s",temp);
        int num=hashFunc(temp,3);
        if(hashTable[num]!=0){
            printf("%s EXIT!\t%d times\n",temp,hashTable[num]);
        }else{
            printf("%s NOT EXIT!\n",temp);
        }
    }
    return 0;


}