【Java】哈希表 AcWing 840. 模拟散列表

用户10604450

发布于 2024-03-15 14:39:06

720

发布于 2024-03-15 14:39:06

文章被收录于专栏：练习两年半练习两年半

一、题目

二、思路

拉链法

开放寻址法采用hash函数找到在hash数组中对应的位置，如果该位置上有值，并且这个值不是寻址的值，则出现冲突碰撞，需要解决冲突方案，该算法采用链表的形式，一直往下拉

开放寻址法

开放寻址法采用hash函数找到在hash数组中对应的位置，如果该位置上有值，并且这个值不是寻址的值，则出现冲突碰撞，需要解决冲突方案，该算法采用简单的向右继续寻址来解决问题。

三、代码

拉链法

import java.util.Scanner;

public class Main {
    //N:操作数量 , h[N]:拉链数组 , e[N]:地址为N的数值 , ne[N]:地址为N的下一个节点地址，index:节点地址
    static int N=100003;   static int index=1;
    static int []h=new int[N];
    static int []e=new int[N]; static int []ne=new int[N];
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n= sc.nextInt();
        while (n-->0) {
            String s=sc.next();
            int c=sc.nextInt();
            if(s.equals("I")){
                insert(c);
            }else {
                if(query(c)){
                    System.out.println("Yes");
                }else System.out.println("No");
            }
        }
    }

    private static void insert(int x) {
      int n=(x%N+N)%N;   //+N余N是为了防止取余的结果为负数
      e[index]=x;
      ne[index]=h[n];
      h[n]=index++;
    }
    private static boolean query(int x) {
        int n=(x%N+N)%N;
        for(int i=h[n];i!=0;i=ne[i]){
            if(e[i]==x) return true;
        }
        return false;
    }
}

开放寻址法

import java.util.*;

public class Main{
    private static int N = 200003;
    //因为要用null标识节点空，所以类型为Integer
    private static Integer[] a = new Integer[N];
    public static int find(int x){
        int k = (x % N + N) % N;
        //别忘了第二个已存在的条件
        while(a[k] != null && a[k] != x){
            k++;
            if(k == N){
                k = 0;
            }
        }
        return k;
    }

    public static void main(String[] args){
        //先将所有位置设为null，标识为空
        Arrays.fill(a,null);
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        while(m-- > 0){
            String opt = scanner.next();
            int x = scanner.nextInt();
            if("I".equals(opt)){
                a[find(x)] = x;
            }else{
                //这是比较的是a[find(x)]
                System.out.println(a[find(x)] == null ? "No" : "Yes");
            }
        }
    }
}