算法竞赛100天第四天 —— 设计哈希表(散列表)

简介: 算法竞赛100天第四天 —— 设计哈希表(散列表)

一、什么是散列表

又称哈希表,将一个比较大的值域映射到一个小的范围,比如0∼1000000000,映射到0∼100000范围内。原因是原来的值域是比较稀疏的,稠密的。

类似于离散化离散化保序,而哈希表不保序离散化是一种极其特殊的HashHash方式

一般的操作有:

  • 插入
  • 查找
  • 删除(算法竞赛一般不用)

下面我们来先看一道题目:

维护一个集合,支持如下几种操作:
I x,插入一个数 x;
Q x,询问数 x 是否在集合中出现过;
现在要进行 N 次操作,对于每个询问操作输出对应的结果。
输入格式
第一行包含整数 N,表示操作数量。
接下来 N 行,每行包含一个操作指令,操作指令为 I x,Q x 中的一种。
输出格式
对于每个询问指令 Q x,输出一个询问结果,如果 x 在集合中出现过,则输出 Yes,否则输出 No。
每个结果占一行。
数据范围
1≤N≤105
−10^9≤x≤10^9
输入样例:
5
I 1
I 2
I 3
Q 2
Q 5
输出样例:
Yes
No

二、拉链法

#include <bits/stdc++.h>//C++万能头文件
using namespace std;
const int N = 100003; //这个数字是根据FindGreaterPrime.cpp获取到的
//槽(坑)
int h[N];//h[i]=x 表示键值为i的头结点指向的结点标号
//拉链法
int e[N];   //e[i]=x表示编号为i的结点对应的真实值
int ne[N];  //ne[i]=x表示编号为i的结点连接的子节点编号为x
int idx;    //结点符号
// 键值相同的元素构成一个单链表,h[i]是键值为i的单链表的头结点;insert函数采用的是头插法
//单链表插入
void insert(int x) {
    //如果x是负数,那么x%N就是一个负数,我们不想要一个负数,就加上一个N,
    //然后再模N就行了。
    int k = (x % N + N) % N;
    //头插法
    //1、添加一个新数据
    //2、原来k的头接到新增加数据idx的后面
    //3、把idx设置为k的头
    //4、idx++方便下一次插入
    e[idx] = x, ne[idx] = h[k], h[k] = idx++;
}
//查询操作
bool find(int x) {
    //同样的Hash函数
    int k = (x % N + N) % N;
    //查找链表,看看有没有x
    for (int i = h[k]; i != -1; i = ne[i])
        if (e[i] == x) return true;
    return false;
}
int main() {
    //优化输入
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    //批量设置h数组内容为-1,清空槽,这是链表终点的初始值
    memset(h, -1, sizeof h);
    while (n--) {
        string op;
        int x;
        cin >> op >> x;
        //插入x
        if (op == "I") insert(x);
        else {
            //检查是不是存在
            if (find(x)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

三、开放寻址法

#include <bits/stdc++.h>
using namespace std;
//如果题目说是100000,那就需要找一个两倍大一点的质数(而且这个质数最好是靠近)
//这个数字是根据FindGreaterPrime.cpp获取到的
const int N = 200003;
//正无穷
const int INF = 0x3f3f3f3f;
//因为题目的数据范围是1e9,而0x3f3f3f3f大于1e9,所以可以用来做特殊值判断
//开放寻址法
int h[N];
//核心操作
//找坑位:有两种方式会停止下来,一是找到了这个值,二是找到了坑位,用时再注意分辩
//如果存在,返回x存储的位置
//如果不存在,返回x应该存储的位置
//如果返回的位置上真实的值==x就是找到了,!=x就是找不到
int find(int x) {
    int k = (x % N + N) % N;
    while (h[k] != INF && h[k] != x) {
        k++;
        if (k == N) k = 0;//如果找到了最后一个位置,那么就回到0
    }
    return k;
}
int main() {
    //输入优化
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    //全部初始化为正无穷,判断是不是使用过此位置
    memset(h, 0x3f, sizeof h);
    while (n--) {
        string op;
        int x;
        cin >> op >> x;
        int k = find(x);
        if (op == "I")h[k] = x;
        else {
            if (h[k] != INF) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}
相关文章
|
算法
带你读《图解算法小抄》六、哈希表(2)
带你读《图解算法小抄》六、哈希表(2)
|
2月前
|
算法 Java 数据库
数据结构与算法学习十五:哈希表
这篇文章详细介绍了哈希表的概念、应用实例、实现思路,并提供了使用Java实现的哈希表代码。
57 0
数据结构与算法学习十五:哈希表
|
7月前
|
存储 算法 Java
【算法系列篇】哈希表
【算法系列篇】哈希表
|
6月前
|
存储 算法 数据可视化
【漫画算法】哈希表:古代皇帝的秘密魔法书
【漫画算法】哈希表:古代皇帝的秘密魔法书
|
6月前
|
存储 算法 Java
面试高频算法题汇总「图文解析 + 教学视频 + 范例代码」之 二分 + 哈希表 + 堆 + 优先队列 合集
面试高频算法题汇总「图文解析 + 教学视频 + 范例代码」之 二分 + 哈希表 + 堆 + 优先队列 合集
|
6月前
|
存储 算法
数据结构和算法——散列表的性能分析(开放地址法的查找性能、期望探测次数与装填因子的关系、分离链接法的查找性能)
数据结构和算法——散列表的性能分析(开放地址法的查找性能、期望探测次数与装填因子的关系、分离链接法的查找性能)
121 0
|
6月前
|
存储 算法
数据结构和算法——了解哈希表(哈希查找、散列的基本思想)
数据结构和算法——了解哈希表(哈希查找、散列的基本思想)
47 0
|
7月前
|
算法 C++
c++算法学习笔记 (20) 哈希表
c++算法学习笔记 (20) 哈希表
|
7月前
|
存储 算法 安全
数据结构与算法 哈希表
数据结构与算法 哈希表
33 0
|
7月前
|
存储 算法 Java
算法系列--哈希表
算法系列--哈希表
39 0