Hash思路

Hash表又称为散列表,一般由Hash函数(散列函数)与链表结构共同实现。与离散化思想类似,当我们要对若干复杂信息进行统计时,可以用Hash函数把这些复杂信息映射到一个容易维护的值域内。因为值域变简单、范围变小,有可能造成两个不同的原始信息被Hash函数映射为相同的值,所有我们需要处理这种冲突情况。
有一种称为"开散列"的解决方案是,建立一个邻接表结构,以Hash函数的值域作为表头数组head,映射后的值相同的原始信息被分到同一类,构成一个链表接在对应的表头之后,链表的节点上可以保存原始信息和一些统计数据。
Hash表主要包括来两个基本操作:
1．计算Hash函数的值。
2．定位到对应链表中依次遍历、比较。
无论是检查任意一个给定的原始信息在Hash表中是否存在,还是更新它在Hash表中的统计数据,都需要基于这两个基本操作进行。
当Hash函数设计较好时,原始信息会被比较均匀地分配到各个表头之后,从而使每次查找,统计的时间降低到"原始信息总数除以表头数组长度"。若原始信息总数与表头数组长度都是O(N)级别且Hash函数分散均匀,几乎不产生冲突,那么每次查找，统计的时间复杂度期望为O(1)。
例如，我们要在一个长度为N的随机整数序列A中统计每个数出现了多少次。当数列A中的值都比较小时,我们可以直接用一个数组计数(建立一个大小等于值域的数组进行统计和映射,其实就是最简单的Hash思想)。当数列A中的值很大时，我们可以把A排序后扫描统计。这里我们换一个思路,尝试一下Hash表的做法。
设计Hash函数为H(x)=(x mod P)+1,其中P是一个比较大的质数,但不超过N。显然,这个Hash函数把数列A分成P类,我们可以依次考虑数列中的每个数A[i]，定位到head[H(A[i])]这个表头所指向的链表。如果该链表中不包含A[i],我们就在表头后插入一个新节点A[i],并在该节点上记录A[i]出现了1次,否则我们就在直接找到已经存在的A[i]节点将其出现次数+1。因为整数序列A是随机的,所以最终所有的A[i]会比较均匀地分散在各个表头之后,整个算法的时间复杂度可以近似达到O(N)。
上面的例子是一个非常简单的Hash表的直观应用。对于非随机的数列,我们可以设计更好的Hash函数来保证其时间复杂度。同样的,如果我们需要维护的是比大整数复杂得多得信息的某些特性(如是否存在,出现次数等),也可以用Hash表来解决。字符串就是一种比较一般化的信息,在本节的后半部分,我们将会介绍一个程序设计竞赛中极其常用的字符串Hash算法。

一般哈希-拉链法、开放寻址法

(1) 拉链法
    int h[N], e[N], ne[N], idx;

    // 向哈希表中插入一个数
    void insert(int x)
    {
        int k = (x % N + N) % N;
        e[idx] = x;
        ne[idx] = h[k];
        h[k] = idx ++ ;
    }

    // 在哈希表中查询某个数是否存在
    bool find(int x)
    {
        int k = (x % N + N) % N;
        for (int i = h[k]; i != -1; i = ne[i])
            if (e[i] == x)
                return true;

        return false;
    }

(2) 开放寻址法
    int h[N];

    // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
    int find(int x)
    {
        int t = (x % N + N) % N;
        while (h[t] != null && h[t] != x)
        {
            t ++ ;
            if (t == N) t = 0;
        }
        return t;
    }

C++ 代码

#include <cstring>
#include <iostream>

using namespace std;

const int N = 1e5 + 3;  // 取大于1e5的第一个质数，取质数冲突的概率最小 可以百度

//* 开一个槽 h
int h[N], e[N], ne[N], idx;  //邻接表

void insert(int x) {
    // c++中如果是负数 那他取模也是负的 所以 加N 再 %N 就一定是一个正数
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx++;
}

bool find(int x) {
    //用上面同样的 Hash函数 讲x映射到 从 0-1e5 之间的数
    int k = (x % N + N) % N;
    for (int i = h[k]; i != -1; i = ne[i]) {
        if (e[i] == x) {
            return true;
        }
    }
    return false;
}

int n;

int main() {
    cin >> n;

    memset(h, -1, sizeof h);  //将槽先清空 空指针一般用 -1 来表示

    while (n--) {
        string op;
        int x;
        cin >> op >> x;
        if (op == "I") {
            insert(x);
        } else {
            if (find(x)) {
                puts("Yes");
            } else {
                puts("No");
            }
        }
    }
    return 0;
}