哈希表一些操作的讲解

xingshuyan000 · 2025-01-26 15:34:14 · 题解

题解：P11615 【模板】哈希表

这是一道哈希表的模板题，我这篇题解将会详细讲解哈希表及相关操作。

题目传送门：洛谷 P11615

（其实我是现学现用的，刚刚学会）

声明：这篇题解中的部分内容引用来自百度百科或 OI-wiki。

哈希表

哈希表也叫散列表。

我们先来看一下百度百科上对于哈希表的定义：

散列表（Hash table，也叫哈希表），是根据关键码值（key-value）而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数，存放记录的数组叫做哈希表。

所谓的以 key-value 的形式存储数据，是指任意的键值 key（以下用 k 来表示） 都唯一对应到内存中的某个位置。只需要输入查找的键值，就可以快速地找到其对应的 value（以下用 v 来表示）。我们可以把哈希表理解为一个高级的数组，这里的数组下标可以是一个大整数、浮点数、字符串，甚至可以是个结构体。

下面举几个以 key-value 的形式存储数据的例子：

就是类似于上面这样的。

哈希函数

定义： 要让键值对应到内存中的位置，就要为键值计算索引，也就是计算这个数据应该放到哪里。这个根据键值计算索引的函数就叫做哈希函数，也称散列函数。

其实，哈希函数就是一个映射，这个映射可以把一个 x 值映射为一个 y 值。比如，当 x 是一个范围为 [-10^9,10^9] 的整数时，我们可以通过映射 f，把这个值映射到一个取值区间在 [0,10^5] 的整数 y 上。一般来说，这种操作需要你选取一个较大的质数 M，让 f(x)= x \mod M，这样成为一个哈希函数。

当 key 值是一个字符串时，我们需要用到字符串哈希，这里可以移步至 P3370 这道题，那里面的题解会有字符串哈希的讲解，我在这儿就不多讲了。

哈希冲突

经过前面的讲解，我们容易发现一个问题，如果对同一个数取模，可能会出现不同的键值被映射到了同一个数上面，这就叫做哈希冲突。比如，当模数为 5 时，f(2)=2,f(7)=2,f(12)=2，这就发生了哈希冲突。为了处理哈希冲突，在 OI 中，主要有两种方法：拉链法和开放寻址法。下面，我将分别来讲解这两种方法。

处理哈希冲突的方法一：拉链法

拉链法又称为开散列法。

首先，我们开一个一维数组，大小为你的模数，比如你现在要对 10^5 取模，那么我们就开一个大小为 10^5 的数组，这样从左到右依次是 0,1,2,\cdots,10^5-1，每个数对应一个位置，这个数组的每个位置可以对应每一个取模结果。然后，在原数的取模结果对应位置下面拉一条链，依次连上原数。因为哈希表是一种期望算法，尽管每个位置都会拉下来一条链，但平均下来，每一条链都是非常短的，所以，拉链法的时间复杂度可以近似为 O(1)，时间复杂度还是很好的。

拉链法的大致结构如下图，以上面的 10^5 为例：

（突然感觉有点像一堆糖葫芦）

我们一般用到的哈希表操作是添加操作和查询操作，很少会用到删除操作。

添加操作：要求你插入一个数 x，那就直接计算 x 的哈希值 f(x)，找到数组上对应的位置，然后把数 x 加到下面的链上就好了。

查询操作：要求你查找一个数 x 是否存在于哈希表中，那就找到 x 对应的哈希值，然后去下面的链表里面找找，看能否找到 x。

删除操作：要求你把这个哈希表里的某个数 x 删除，其实并不是真的删除掉这个数，你用一个 bool 变量给对应的数 x 打上标记就好了。

拉链法的 C++ 核心代码（一般模板，不针对本题）：

//拉链法
const int N = 1e7 + 19; //大于1e7最小的质数，可以直接写个程序跑一下
struct Hash{
    int h[N]; //哈希表
    int e[N], ne[N], idx = 0; //这是链表的东西
    void insert(int x) //插入一个数x
    {
        int k = (x % N + N) % N; //k是x对应的哈希值
        //为什么要 (x % N + N) % N 呢？因为处理的时候
        //可能会遇到x是负数的情况，如果对负数取模，
        //结果也是负数，而我们要的是非负整数值，所以
        //通过这样把取模结果转化为非负数
        e[idx] = x;
        ne[idx] = h[k];
        h[k] = idx ++; //链表的基本操作
        return;
    }
    bool find(int x) //查找x
    {
        int k = (x % N + N) % N; //计算x的哈希值
        for(int i = h[k]; i != -1; i = ne[i])
            if(e[i] == x) return true; //如果找到了，返回true
        return false; //遍历完了都没找到，返回false
    }
    void init()
    {
        memset(h, -1, sizeof(h)); //初始化，让h中的初始值都为-1
        return;
    }
};

处理哈希冲突的方法二：开放寻址法

开放寻址法，也是一种常用的处理哈希冲突的方法，其基本思想就是，寻找哈希表中的下一个空位，然后把元素直接扔到这个空位当中。

开放寻址法只需要开一个一维数组即可，不需要再手动模拟链表了，在形式上看来会简单一点。一般来说，开放寻址法开的一维数组大小是数据量的 2 \sim 3 倍，比如本题中的数据量是 5 \times 10^6，那么开放寻址法开的数组大小就要达到 10^7 ，这样可以减小哈希冲突。

我们可以这么理解开放寻址法：把开放寻址法的数组当成一个巨大的食堂，数组中的每个位置当成食堂中的餐桌，每个餐桌只能容纳一个人。我们去食堂买完饭以后，肯定需要去找地方坐，那么按照一般思路，我们就会从第一个餐桌开始，往后依次寻找第一个空闲的餐桌。如果第 i 号餐桌有人，我们就会继续找第 i+1 号餐桌，如果还有人我们会继续找第 i+2 号餐桌，以此类推，直到找到一个空闲的，然后就坐。 （可能这个例子并不完全符合开放寻址法的思路，但基本就是这个意思，这样相对更容易理解一些）

同样，开放寻址法对应三种操作：添加、查询和删除。

添加操作：要求你往哈希表中插入一个数 x，那么你仍然先计算出来 x 的哈希值 k，然后从哈希表中第 k 个位置开始，往后找到第一个没有被占用的位置，然后把 x 扔到这个位置上。

查询操作：要求你在哈希表中查找一个数 x，那么还是先求出来他的哈希值 k，然后从第 k 个位置开始依次往后找，如果在第 i 个位置找到了，那么 x 就存在于第 i 个位置上，如果发现中间位置是空的而且仍然没找到，那么，就说明 x 不存在。

删除操作：要求你删除哈希表中的一个数 x，跟拉链法的思路差不多，都是直接用一个 bool 变量给 x 标记出来，而并不是真的把这个数 x 删掉。

开放寻址法的 C++ 核心代码（一般模板，不针对本题）：

//开放寻址法
const int N = 1e7 + 19;
struct Hash_table{
    const int null = 0x3f3f3f3f; //相当于一个空指针
    int h[N]; //哈希表
    void init()
    {
        memset(h, 0x3f, sizeof(h));
        return;
    }
    int find(int x) //在哈希表中查找x
    {
        int k = (x % N + N) % N; //x的哈希值
        while(h[k] != null && h[k] != x) //如果一直没找到x
        {
            k ++;
            if(k == N) k = 0; //如果找到了最后一个，就要从第一个开始，让k=0
        }
        return k; //返回x的位置（找到）或x应当存在的位置（未找到）
    }
    void insert(int x) //插入x
    {
        int k = find(x);
        h[k] = x;
        return;
    }
};

注意：在 C++ 中，函数名不能定义为 hash，因为 hash 是 C++ 中的保留字，如果定义为了 hash，容易编译错误。

针对本题的分析

其实这道题也就是个哈希表的模板题。他让你维护一个从 [0,2^{64}-1] 到 [0,2^{64}-1] 的映射 f，初始值函数值都为 0。给你 n 次询问，每次询问给定一个二元数组 (x,y)，你需要查找 f(x) 的值，然后把 y 赋值给 f(x)。其中，n \le 5 \times 10^6，0 \le x,y < 2 ^{64}。

它让你找 f(x) 的值，然后把 y 赋值给 f(x)，那显然得用开放寻址法处理冲突。这里面只需要把我刚才放的模板代码稍微修改一下即可，可以完美解决这个问题。

时间复杂度为 O(n)，可以通过本题。

不过请注意，本题的输入数据量可以达到 10^7，常数很大，需要注意读入的优化，比如可以直接用本题给你的快读，这个效率很高，适合处理较大的读入量。同时，因为数据量大，所以不要使用 unordered_map、gp_hash_table、cc_hash_table 等错误的哈希方式写代码，这些错误方式在 subtask4 容易被卡掉。

CODE

我发现我的代码跟某个题解的代码重复了，不过声明一下，我没有抄袭哈，这是我自己写的。

测试点所用最常时间：1.03s；最大内存：166.86MB。可以完美通过本题。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long LL;
namespace fast_IO
{
    char buf[1 << 23], *p1 = buf, *p2 = buf;
    char __getchar()
    {
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
    }
    template <typename T>
    T read()
    {
        T x = 0;
        char ch = __getchar();
        while(!isdigit(ch)) ch = __getchar();
        while(isdigit(ch)) {x = x * 10 + (ch ^ 48); ch = __getchar();}
        return x;
    }
}
const int N = 1e7 + 19;
struct Hash_table{
    LL h[N], kk[N]; 
    bool exist[N];
    void init() //其实这个函数要不要都行
    {
        memset(h, 0, sizeof(h));
        memset(kk, 0, sizeof(kk));
        memset(exist, false, sizeof(exist));
        return;
    }
    void insert(LL x, LL y)
    {
        int k = x % N; //因为输入的都是正数，所以就不用再 +N 了
        while(exist[k] == true)
        {
            if(kk[k] == x) break;
            k ++;
            if(k == N) k = 0;
        }
        kk[k] = x, h[k] = y;
        exist[k] = true;
        return;
    }
    LL find(LL x)
    {
        int k = x % N;
        while(exist[k] == true)
        {
            if(kk[k] == x) return h[k];
            k ++;
            if(k == N) k = 0;
        }
        return 0;
    }
};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n;
    n = fast_IO::read<int>();
    Hash_table hash_table;
    hash_table.init();
    LL sum = 0;
    for(int i = 1; i <= n; i ++)
    {
        LL x, y;
        x = fast_IO::read<LL>(), y = fast_IO::read<LL>();
        LL ans = i * hash_table.find(x);
        sum += ans;
        hash_table.insert(x, y);
    }
    cout << sum << "\n";
    return 0;
}