---
title: "模拟散列表"
created: 2025-11-28
tags:
  - 算法
---

# 模拟散列表

## 题目 [模拟散列表](https://www.acwing.com/problem/content/842/)

![[image-edb87a6e.png]]

## 思路分析

![[image-65d671bf.png]]

## 代码实现

**开放寻址法**

```cpp
 /*

只用一个数组去存储映射后的关系

如果冲突了 就继续往后找 直到找到一个坑没被占

那这样的话 数组长度就应该比理想情况要大了 大多少 最好开两到三倍

对于这么一个结构来说 核心就是查找了

如果得到一个k 从h[k]开始去找

如果当前位置有数 并且就为x 那就找到了x

如果当前位置有数 但不是x 那就往后找

如果当前位置没数 那就x不存在（执行删除还是返回没找到看操作要求 核心就是一个find）

怎么表示该某位置没元素？ 全初始化成无穷大

*/

#include<bits/stdc++.h>

using namespace std;

const int N=200003;//开双倍

const int null=0x3f3f3f3f;//无穷大

int h[N];

//若存在 返回位置 若不存在 返回应该存的位置

int find(int x)

{

    int k=(x%N+N)%N;

    //坑上有人 且不是自己

    while(h[k]!=null && h[k]!=x)

    {

        k++;//往后找

        if(k==N)//如果找到末尾没找到 就回起点找

            k=0;

    }

    return k;

}

int main()

{

    int n;

    cin>>n;

    //初始化为无穷大

    memset(h,0x3f,sizeof h);

    while(n--)

    {

        char op[2];

        int x;

        scanf("%s%d",op,&x);

        int k=find(x);

        if(*op=='I')

            h[k]=x;

        else

        {

            if(h[k]!=null)

                puts("Yes");

            else

                puts("No");

        }

    }

    return 0;

}
```

**拉链法**

```cpp
/*

就是把一个数处理后 得到一个下标位置

但如果这个下标位置已经有元素了

那就把它链在后面

但是这里我们还是用数组模拟的链表

嗯 一个e放数据本身 一个ne放下一个位置的下标

在一维的每一个结点的后面都接两个数组

其实没必要

因为一维中存的不过是一个下标 作用就是单链表中的head

各个域中的head并不冲突 它只需要根据下标找到e数组中的第一个数

再链着ne找下一个数 直到所有

所以 完全可以把所有的数都存放在一个e、ne中

不同域去就相当于不同的head 去进行一个索引

嗯 把一个数组拆成多个链

把一维的每一个位置都当做head即可 不过是对一个数组有多个head访问罢了

那么既然是当head用

所以初始化就是要把所有的值都赋为-1表示空

memset(h,-1,sizeof h);

插入一个点 就是头插

e[idx]=x;

ne[idx]=h[k];

h[k]=idx++;

遍历也很简单 从头开始 i=h[k]

直到结束i!=-1 每次往后寻 i=ne[i]

for(int i=h[k];i!=-1;i=ne[i])

*/

#include<bits/stdc++.h>

using namespace std;

const int N=100003;

int h[N],e[N],ne[N];

int idx;

void insert(int x)

{

    int k=(x%N+N)%N;

    //找到了k位置

    //其实就是头插了

    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;

}

int main()

{

    int n;

    cin>>n;

    memset(h,-1,sizeof h);

    while(n--)

    {

        char op[2];

        int x;

        scanf("%s%d",op,&x);

        if(*op=='I')

            insert(x);

        else

        {

            if(find(x))

                puts("Yes");

            else

                puts("No");

        }

    }

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[哈希表|哈希表]] 🏠 [[00-听课板子]] ➡️ [[2-Learning/02-算法/02-听课板子/数据结构/哈希表/字符串哈希|字符串哈希]]