AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

哈希表笔记

作者: 作者的头像   solego ,  2019-07-18 11:37:02 ,  所有人可见 ,  阅读 1759


14


13

哈希表是一种非常带劲的存储方法,它将一定个数内的数据以一种降低数据规模的方式存储着,哈希表的主要操作就是添加数据和查找数据,当然你也可以用标记来标记数据是否被删除(实际上,它只是被你标记删除了,并未被实际删除并释放内存)


上模板题让我们直观感受下:
Acwing840 传送门 : https://www.acwing.com/problem/content/842/

这题就让我们实现了哈希表的存储和查找:

比较好用的两种方法: 拉链法和 开放寻址法

1.拉链法

一个节点上存储着 取模后位置相同的数据,由于存储位置相同,为避免矛盾,采用拉链法将其以拉链形式展开存储

首先创建存储位置的数组,这个数组的每个元素作为拉链的头结点,即每个元素都作为一个单链表的头结点,之后按照数据的模后存储位置存储单链表的数据即可

如图所示:哈希表.png

觉得图的大小不合适的同学可以右击打开图片链接


2. 开放寻址法

为了避免查找时的寻找次数过多,一般数组大小为题目所给数据范围的2~3倍,且数组大小尽量设置为质数减少冲突。

主要思路就是如果数据取模后的位置未被占用,那么就直接将该数据存储着该位置,如果已被占用,则往后寻找直至找到一个未被占用的位置。

这里直接上代码:

Acwing840

#include<stdio.h>
#include<string.h>

const int null = 0x3f3f3f3f;
const int N = 200003; //开为题目数据范围的2倍

int h[N]; //存储的值


void init(){
    memset(h, 0x3f, sizeof(h));
}

//插入值和查找值只需一个函数
int find(int x){
    int k = ((x % N) + N) % N;
    while(h[k] != null && h[k] != x){ //当这个位置被占用了,且x未被存储
        k++;
        if(k == N) k = 0; //如果到了最后一个位置,就返回初位置再开始寻找
    }
    return k;
}

int main(){

    init();

    int n;
    scanf("%d", &n);

    while(n--){
        char op[2];
        int x;
        scanf("%s%d", op, &x);

        if(op[0] == 'I'){            
            int k = find(x);
            h[k] = x;
        }   

        else if(op[0] == 'Q'){
            if(h[find(x)] == null) puts("No"); 
            else puts("Yes");
        }
    }

    return 0;
}

2 评论


用户头像
yxc   2019-07-19 08:33      2    踩      回复

赞!


用户头像
无为自在   2022-02-11 11:23         踩      回复

$yxc$楼下!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息