并查集和哈希表的实现

文章目录

• 并查集和哈希表的实现
• • 1.并查集的功能
  • 2.并查集的基本原理
  • 3.并查集的实现
• 哈希表（hash）
• • 1.拉链法
  • 2.开放寻址法
  • • 方法流程
    • 代码演示
  • 3,字符串哈希

---

1.并查集的功能

1.将两个集合进行合并

2.询问两个元素是否在一个集合里面

2.并查集的基本原理

基本原理：每一个集合用一棵树来表示，树根的编号就是整个集合的编号，每一个点存储的都是其父节点，p[x]表示的就是x的父节点

要考虑的问题有三个
问题一：如何判断树根 if(p[x]==x)

问题二：如何求x的集合编号 while(p[x]!=x) x=p[x]

问题三：如何合并两个结合 p[x]是x的集合编号，p[y]是y的集合编号,p[x]=y;表示x的父节点是y

3.并查集的实现

并查集，查找两个元素，是否在一个集合里面，而且可以将两个集合合并

//首先要设置全员变量
using namespace std;

const int n = 100010;
int n,m;
int p[N];//p[N]来存储的是父节点

//寻找操作
int find (int x)
{
    if(p[x]!=x) p[x]=find (p[x]);
	return p[x];//如果x的父节点不是x的时候，就要将p[x]放在find函数里面去，用p[x]来接收，直到最后p[x]==x ，递归返回之后，这个结合的所有结点的父节点都是x
}
//相当于 返回x的祖宗结点，并且有路径压缩

//如果说我们输入”M“来表示将两个集合合并
int main()
{
    scanf("%d%d",&n,&m);
    //输入n个数字，进行m次操作
    for(int i = 1;i <= n; i++ ){
        p[i]=i;//首先让n个结点的父节点都是自己本身，因为初始的时候每一个结点就是一个集合
    }
    
    while(m--){
        char op[2];//输入操作的字符
        int a,b;//指定的两个结点
        scanf("%s%d%d",op,&a,&b);
        
		if(op[0]=='M'){
          p[find(a)]=find(b);//将两个集合合并，可以先找到a，b的祖宗结点，这样讲a祖宗结点的父节点设置为b的祖宗结点，这样两个集合合并
        }
        else {//op不是M的时候，就是要进行判定ab是否是在一个集合里面
            //如果是I 表示判断是否两个结点在一个集合里面
            if(find(a)==find(b)){
                printf("Yes\n");
            }else {
                printf("NO\n");
            }
        }
    }
    return 0;
}

哈希表（hash）

哈希表常用的两个方式来存储数据, 拉链法和开放寻址法

哈希表的原理就是将一个很大范围中的数字,放置在一个小范围的数组中存储起来.

可以实现的功能为1.存储 2.查找

比如-10⁹ ~10⁹ 存放在一个范围为0~10⁵ 的数组中存储起来

操作流程

1.先进行mod 取模,得到一个数字,存放在一个数组中

2.因为对于这些数据,会有冲突的时候,所以对于多个数据取模得到一个数值,使用拉链法,数组的每一个槽都可以对应一个链表形式的结构,通过这个结构,将取模相同的元素,放在这个槽对应的链表中,然后在查找的过程中近似实现O(1)的操作

我们mod的时候使用的数字应该是个质数,如果处理在0-100000范围内的数据,那么就要找到大于100000的最小质数

查找mod数值的方法为:

int getInteger(int n){//n传递为100000
	while(n++){
        for(int j=2;j*j<=n;j++){
            if(n%j==0){
                break;
            }
        }
    }
    return n;
}

1.拉链法

操作的流程,在c/c++中需要自行用数组来表示链表,在Java中可以使用LinkedList来表示链表

我们使用c++来举例

using namespace std;

const int n=100003;//我们提前找到了这个大于最大范围的最小质数
int h[N],e[N],ne[N],idx;
//h[N]用来存储模的数值
//e[N]用来形成链表,存储的数值
//ne[N]用来得到当前N下标对应的下一个数值
//idx表示链表的下标

//我们要实现的是,输入一个n,表示有n个操作,如果是输入"I x"表示插入数值x,如果是"Q x"实现查找x,查找到x 输出Yes 没有输出No
#include<string.h>
#include<stdio.h>
#include<iostream>

void insert(int x){
    int k=(x % N + N ) % N;//取模,x%N可能为负值,所以+N,然后再mod N
    //得到k就是要存储在槽中的数值h[N],就是找到位置
    e[idx]=x;//用当前下标idx存储数值为x
    ne[idx]=h[k];//然后idx的下一个坐标为h[k]的位置也就是说,头插
    h[k]=idx;//然后h[k]=idx h[k]就相当于头节点
    idx++;//添加一个元素idx++;
    
}

bool find(int x){
    int k=( x % N + N ) % N ;
	for(int i=h[k];i!=-1;i=ne[i]){
        //得到x的存储在槽终点 位置h[k],然后查询链表
        if(x==e[i]){
            return true;
        }
    }
    return false;
}

int main()
{
    int n;
    scanf("%d",&n);
    //表示输入n个操作
    memset(h,-1,sizeof(h));//对于h[N]数组进行赋值为-1
    
    while(n--){
        char op[2];
        int x;
        scanf("%s%d",op,&x);
        if(op=='I'){//插入存储数值x
            insert(x);
        }else {
            //进行查找x
            if(find(x)){
                printf("Yes\N");
            }else{
                printf("No\n");
            }
        }
    }
    return 0;
}

拉链法的主要内容是

1.得到k的数值,然后在h[k]数组上加上链表,使用e[idx]数组来存储数值x,用ne[idx]=h[k],h[k]=idx来实现头插,最后idx++;

//插入的算法
void insert(int x){
    int k=(x % N + N) % N;
    e[idx]==x;
    ne[idx]=h[k];
    h[k]=idx;
    idx++;
}

2.我们对于h[N]数组初始化的时候赋值为-1,但是在插入数据的时候,会头插,将idx的数值赋值给了h[N]数组

//查询的时候的代码
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;
}

拉链法主要是插入函数insert和find函数.

2.开放寻址法

开放寻址法的主要方式为: 开辟的数组的发小是输入数据范围的2,3倍

方法流程

1.先找到一个合适的质数

2.插入方法为,在存储数据的时候通过hash函数,得到k,然后存储

3.进行查找

代码演示

using namespace std;

const int N=100003;
int null=0x3f3f3f3f;//设定一个极大值
int h[N];//存储数值的数组

int find(int x){
    int k=(x % N + N) % N;
    while(h[k]!=null && h[k]!=x){
        //如果说是不为null不为x,表示没有存储过这个数值
        k++;//没找到就k++
        if(k==N)  k=0;//如果等于N,那就从头0开始
    }
    return k;//找到了就返回的k值
}

int main()
{
    int n;//表示n个操作数
    scanf("%d",&n);
    memset(h,0x3f,sizeof(h));
    //memset 作用是对于一个地址进行赋值,可以指定大小,指定数值
    //函数有三个参数
    //第一个是 输入地址,比如h表示数组地址,第二个参数是存放数值,这个是存放一个字节的数值,如果是int 数组,那就是4个0x3f
    //第三个参数是数组大小,也就是要赋值的范围
 
    while(n--){
        char op[2];
        int x;
        scanf("%s%d",op,&x);
     	int k= find(x);
        if(op[0]=='I'){
            h[k]=x;//进行插入数值x
        }else{
            //判断是否有x在数组里面
            if(h[k]!=null) printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}

3,字符串哈希

类似于kmp 但是可以实现查找字符串到O(1),基本上更好

字符串hash的用法步骤是:

1.使用p进制,类似于10进制这样,用h[0],h[1]….来存储前n个字符串的p计数

2.使得一串字符,得到一个数字 p进制,有个经验值为131或者是13331;如果是abcd 那就是(a *p[3]+b*p[2]+c*p[1]+d*p[0]) % Q Q也有经验值 为2⁶⁴ 因为用h数组存储哈希值，2⁶⁴ 可以用unsigned long long来表示,如果大于2⁶⁴ 会超出存储范围 ，自动模值

那就是直接 unsigned long long h[n]=a*p[3]+b*p[2]+c*p[1]+d*p[0] 即可

3.然后如果是想要得到 l 到 r 之间的字符串哈希,前段为高位,后端为低位,如果是r>1 那么就是让 h [ l-1 ] *p[ r- l +1 ] 然后h[r]-h[l-1]*p[r-l+1]

代码如下

using namespace std;

typedef unsigned long long ULL;
const int N=100010,p=131;

int n,m;
char str[N];
ULL h[N],p[N];

//题目要求  第一行输入n m str[N]  表示为 n为字符串长度 m为比较次数 str为字符串数组
//接下来m行  输入l1 r1 l2 r2  比较 l1到r1 l2到r2  这两段字符串是否相等

ULL get(int l,int r){
    return h[r]-h[l-1]*p1[r-l+1];
}
int main()
{
	scanf("%d%d%s", &n, &m, str + 1);
	//str数组从1开始 
	//
	p[0] = 1;
	//得到数字
	for (int i = 1; i <= n; i++)
	{
		p[i] = p1[i - 1] * p;
		h[i] = h[i - 1] * p + str[i];
	}

	while (m--)
	{
		int l1, r1, l2, r2;
		scanf("%d%d%d%d", &l1, &r1, &l2, &r2);

		if (get(l1, r1) == get(l2, r2))  						printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}