HashTable

线性探测法

class ArrayHashTable {
  final static int N = Tools.getPrimeNumber(100000), tag = Integer.paraseInt("3f3f3f3f", 16);
  final static int[] h = new int[N];
  
  private static int insert(int x) {
    int k = (x % N + N) & N;
    while (h[k] != tag && h[k] != x) {
      k++;
      if (k == N) k = 0;
    }
    return k;
  }
  
  private static void init() {
    Arrays.fill(h, tag);
  }
}

链地址法

class LinkedHashTable {
  final static int N = Tools.getPrimeNumber(100000);
  static int idx = 0;
  final static int[] h = new int[N], e = new int[N], ne = new int[N];
  
  private static void insert(int x) {
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx++;
  }
  
  private static boolean 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;
  }
}

获取质数

class Tools {
  public static int getPrimeNumber(int x) {
    for (int i = x;; i++) {
      boolean flag = true;
      for (int j = 2; j * j <= x; j++) {
        if (i % j == 0) {
          flag = true;
          break;
        }
        if (flag) return i;
      }
    }
  }
}

String Hashing

主要记录思想

缺点是我现在没办法实现 unsigned long long 的数据类型

所以 N 只能用 -1 ，也就是 0xFFFFFFFFFFFFFFFF

class StringHashing {
  final static long N = -1, P = 13331;
  final static long[] p = new int[N], h = new long[N];
  
  private static long query(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
  }
  
  public static void main(String[] args) {
    Scanner cin = new Scanner(System.in);
    char[] str = new char[s.length + 1];
    String s = cin.next();
    
    System.arraycopy(s.toCharArray(), 0, str, 1, s.length());
    
    p[0] = 1;
    for (int i = 1; i <= str.length; i++) {
      p[i] = p[i - 1] * P;
      h[i] = h[i - 1] * P + str[i];
    }
    
    int l1 = cin.nextInt(), r1 = cin.nextInt(), l2 = cin.nextInt(), r2 = cin.nextInt();
    if (query(l1, r1) == query(l2, r2)) System.out.println("Yes");
    else System.out.println("No");
  }
}

• 参考来源
  • ACWing - 算法基础课