算法笔记(2)| 散列

散列就是指将元素通过一个函数转换为一个整数，并且该整数能够尽可能地唯一代表该元素。

1.整数转换

设有一个数组M，一个数组N，判断数组N中的哪些数字在数组M中出现过,，则可以用如下方法解决：

#include<stdio.h>
#include<iostream>
using namespace std;
int main(){
    int m,n,x;
    bool isExist[1000]={false};
    for(int i=0;i<n;i++){
        cin>>x;
        isExits[x]=true;
    }
    for(int i=0;i<m;i++){
        cin>>x;
        if(isExist[x]==false){
            cout<<"not exits";
        } 
        else{
            cout<<"exist";
        }
    }
    return 0;
}

2.字母转换

当数组中只有字母时，则可以将每一个字母自定义为一个数字，例如：[A,Z]——>[0,25]，[a,z]——>[26,51]。

int hashFunc(char s[],int len){  //字符串和字符串的长度 
    int id;
    for(int i=0;i<len;i++){
        if(s[i]>='A' && s[i]<='Z'){  //如果是大写字母 
            id=id*52+(s[i]-'A');
        }
        else{  //如果是小写字母 
            id=id*52+(s[i]-'a')+26;
        }
    } 
    return id;
}

3.字符串转换

当一个数组中既有数也有字母时，可以按照字母转换的方法，也将数字自定义有单独的数来对应，即[A,Z]——>[0,25]，[a,z]——>[26,51]，[0,9]——>[52,61]：

int hashFunc(char s[],int len){
    int id;
    for(int i=0;i<len;i++){
        if(s[i]>='A' && s[i]<='Z'){  //如果是大写字母 
            id=id*62+(s[i]-'A');
        }
        if(s[i]>='a' && s[i]<='z'){  //如果是小写字母 
            id=id*62+(s[i]-'a')+26;
        }
        else{
            id=id*62+(s[i]-'0')+52;
        }
    }
    return id;
}