java - Rabin-Karp 哈希码太大

Question

rolling hash Rabin-Karp算法中hashcode值过大如何处理？我使用模运算来避免负数，但是当哈希码超过我的模数(N = 83559671)时会出现问题。我将我的基数设置为素数(计算哈希码的数字)以及模数(非常大)，但它不适用于长字符串。任何人都可以看到问题吗？

这是我的代码。

   public static void main(String [] args){

       int P = 13;         // base
       long M = 83559671;
       long iHash = 0;    
       String word = "abcbadccaaaabbbb";
       int WINDOW = 9;

       for(int i = 0; i < WINDOW; i++){
            iHash = int_mod(int_mod(iHash*P, M) + word[i], M);
       }

       for(int i = WINDOW; i < word.length; i++){
            iHash = int_mod(iHash - word[i-WINDOW] * get_pow(P, WINDOW-1, M), M);
            iHash = int_mod(iHash * P, M);
            iHash = int_mod(iHash + word[i], M);
       }

   }
   public static long get_pow(int p, int t, long M){
        long a = 1;
        for(int i = 0 ; i < t; i++){
              a = int_mod(a * p, M);
        }
        return a;
   }

   public static long int_mod(long a, long b){
        return (a % b+ b) % b;
   }

问题是当我有任何长度超过 8 的字符串时，字符串的哈希码超过模数 83559671，这导致我在进行比较时得到错误的答案。任何较短的字符串都可以正常工作。

Answer 1

您根本不需要计算模数。这是一个演示:

public class Foo {
  private static int hash(String s) {
    int hash = 0;
    for (int i = 0; i < s.length(); i++) {
      hash *= 31;
      hash += s.charAt(i);
    }
    return hash;
  }

  public static void main(String[] args) {
    String s1 = "abcdefghij";
    String s2 = s1.substring(1) + "k";
    int pow = 1;
    for (int i = 0; i < s1.length(); i++) {
      pow *= 31;
    }
    System.out.printf("hash(%s) = %d%n", s1, hash(s1));
    System.out.printf("hash(%s) = %d%n31 * hash(%s) - (31^%d * %s) + %s = %s%n",
        s2,
        hash(s2),
        s1,
        s1.length(),
        s1.charAt(0),
        s2.charAt(s2.length() - 1),
        31 * hash(s1) - (pow * s1.charAt(0)) + s2.charAt(s2.length() - 1));
  }
}

这(正确地)打印出:

hash(abcdefghij) = -634317659
hash(bcdefghijk) = 21611845
31 * hash(abcdefghij) - (31^10 * a) + k = 21611845