数据结构第四节——哈希表

初遇哈希，甚感懵比...

哈希表：用一个好的哈希函数(哈希函数由自己定义)，将一些关键字从一个大集合中映射到一个小集合中，然后将这个小集合的信息储存起来。例如用一个数组储存这些信息，这个储存新的（小的集合）信息的数组，就叫做哈希表。

下面通过一些简单的例子，来帮助理解哈希表。

const int mod = 11;
int Hash[mod]; //定义一个mod大小的哈希表,哈希表中每个格子是一个数组元素a[i];


//定义哈希函数
int Hashf( int x ){
    return x % mod; 
    //利用哈希函数 求大集合中元素在哈希表中的位置
}


//定义插入函数（将大集合中元素插入哈希表）
void Inser ( int x ){
    int addr = Hashf( x );  //用定义的哈希函数求得大集合中元素在哈希表中的位置
    Hash[addr] = x;         //将大元素填入哈希表中的对应位置
}
//将大集合中元素插入哈希表后，
//就可以通过哈希表中相应的哈希值（小集合中元素）通过哈希表（数组）映射出大元素中的元素


//定义查找函数，在哈希表中查找是否存在 x
bool isExist ( int x ){    
    int addr = Hashf(x);    //寻找 大集合 x 在哈希表中的位置
    return Hash[addr] == x; // 如果存在则返回1 不存在则返回0
}

通过上述例子，我们大致了解了哈希表的基本构成。同时我们可以发现，当我们在向哈希表中存入数据时，如果没有构造出一个很好的哈希函数，就有可能出现大集合中的多个元素，在哈希表中占据同一个位置的情况。

然而如果只是单纯的运用数组储存，则无法同时储存多个数据。联想前面的知识，我们想到了一个不错的解决方法——在冲突位置，使用 “ 链表 ” 将多个元素”挂在“哈希表的对应位置上。

但如果真的使用链表处理，容易使我们的哈希表显得”臃肿“，不过好在我们还有一种可以开辟动态储存空间的STL利器——Vector。

​ 那么下面我们就来介绍一下，如何利用vecor，构建一个不错的哈希表。

const int mod = 11;
vector<int>Hash[mod]; //定义一个mod大小的哈希表，哈希表中每个格子是一个动态变化的vector

//定义哈希函数
int Hashf( int x ){ 
    return x % mod;
}

//定义搜索函数
void Inser ( int x ){
    int addr = Hashf( x );
    Hash[addr].push_back(x);
    //Hash[addr] 是一个 vector 可以调用相关stl函数
}

//定义查找函数
bool isExist ( int x ){
    int addr = Hashf(x);
    int l = Hash[addr].size(); //求出哈希表中，x对应格子中所含元素个数
                               // 相当于，链表情况下，链表上挂着的元素个数

       for( int i = 0; i < l; i++ ){ //将整个链上的元素遍历一遍，寻找是否有 x
        if ( Hash[addr][i] == x ) return true; //vector中元素从0开始储存，依次遍历
    }
    return false;
}

一般的，我们手写哈希函数的时候，我们一般情况下要求Hash（x） = x % p ， 其中p为素数。

（ 理由需要数论知识支撑，今天暂不考虑 ）

字符串哈希

当我们比较两个字符串中的内容时，字符串哈希将成为解决这类问题的一大利器。

​ 要使用哈希表解决此类问题，首先我们要定义一个哈希函数，将一个大集合字符串转换为与之相对的小集合——数字。

​ 我们定义它的哈希函数为：

int Hashf ( char s[] , int n ){
    int res = 0;
    for ( int i = 1; i <= n; i++ ){
        res = ( res * base + ( s[i] - 'a' + 1 ) ) % p;
        return res;
    }
}

​ 其中，base 比字符集合中字符数量大的一个素数（ base > s.size() ） 且base是素数。

通过字符串哈希，对于两个字符串相a，b似程度的判断问题，我们可以过先将字符串a储存在哈希表中。再通过哈希表，与b中元素逐个对照，记录相似元素数目，最后通过相似度进行判断。

例一、查重判断

蜗蜗大学迎来了毕业季。现在有一批毕业生的论文需要查重。

蜗蜗大学的毕业论文是用数字写成的，现在蜗蜗教授用经验找出了一些可能是抄袭的论文，蜗蜗教授需要你来做出更准确的判断。

你现在被给到两篇论文，第一份是前人留下的，第二份是你需要进行查重的。

如果第二篇论文中的数字在第一篇论文里出现过，就会被标记。如果第二篇论文被标记的数字数量大于等于50%，这篇论文就被判定为抄袭。

现在由你进行查重判断，如果是抄袭，输出Yes，否则输出No。

输入格式

第一行包含两个整数n,m。

接下来一行，包含n个整数a1,a2,…,an，表示第一篇论文。

接下来一行，包含m个整数b1,b2,…,bn，表示第二篇论文。

输出格式

输出一行 Yes 或者 No 。

样例输入

5 6
1 2 3 4 5
3 4 5 6 7 8

样例输出

Yes

数据规模

对于1100%的数据，保证1≤n,m≤2×10^{5,0≤ai,bi≤10}9。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int P = 9999971;
int n, m ,a[200001], b[200001];
vector<int> c[P];

int main()
{
    scanf("%d %d", &n,&m);

    //首先读入两篇论文
    for ( int i = 1; i <= n; i++ ) scanf("%d",&a[i] );
    for ( int i = 1; i <= m; i++ ) scanf("%d",&b[i] );

    //将哈希表中的元素清空(vector 从0开始！！！）
    for ( int i = 0; i < n; i++ ) c[i].clear();

    //将论文a存入哈希表中
    for ( int i = 1; i <= n; i++ ) {

        //求出论文a中每个元素的哈希值（即其在哈希表中的位置）
        int addr_ai = a[i] % P;

        //将论文a中每个元素根据其哈希值（即其在哈希表中的对应位置）放入哈希表中
        c[addr_ai].push_back( a[i] ); //vector c[P]; 是哈希表

    }

    //现在的哈希表是已经将a储存好了的
    //我们只需要拿b和a进行对照，并判断相似程度即可。
    int sim = 0; //记录相似数
    for ( int i = 1; i <= m ; i++ ){

        //求出论文b中每个元素的哈希值（即其在哈希表中的位置）
        int addr_bi = b[i] % P;

        //求出b中每个元素的在哈希表中的对应位置上所含元素个数（类似于对应格子上链表所挂元素长度）
        int l = c[addr_bi].size();

        bool ok = false;
        //对于b中每个元素（现在还在 i 循环中！！！）
        //c[addr_bi][]即为b中第i个元素在哈希表中的位置（该位置上挂着l个元素）
        //下面遍历这l个元素，如果存在则相似数sim ++ ;
        for ( int j = 0; j < l  && !ok ; j++ ){
            if( c[addr_bi][j] == b[i] ) ok = true;
            if ( ok ) sim++;
        }
    }
    //最后判断相似程度，如果相似度过半，则判定抄袭
    // 相似度 = 相似数量（sim） / 总数（ m ）

    //if ( sim / m >= 0.5 ) printf("YES\n");
	//由于不能简单的运用除法，因此将其转化为等价的乘法判断
    if ( 2 * sim >= m ) printf("Yes\n");
    else printf("No\n");

    return 0;
}

嗯...例题随缘吧，事实证明，少了例题，学不明白，awsl...