java - 不使用 Math.BigInteger 的高幂模

Question

我必须将这个公式转换成 java 代码:

如果我可以使用诸如 Math.BigInteger 之类的库，那会容易得多，但不幸的是，没有它我应该这样做。 stackoverflow 上的一些类似问题建议编写一个自己的 bignum 库，但我想在没有它的情况下进行。

目前，我的进度是在这一步:

int h(String s) {
  long value = 1;
  int mod = ht.length;

  for (int i=0; i < s.length()-1; i++) {
     h += s.charAt(i) * Math.pow(256,i);
  }
  return (int) h % mod;
}

我知道幂的值很快就会超出整数范围，所以我考虑编写一个自己的方法来计算该值的幂和模。我的数学知识还不够好，不知道何时使用模数以及如何简化事情。

提前致谢!

Answer 1

如果你从后面走，你根本不需要任何权力。在每一步简单地乘以 256 将产生相同的效果(后面的值“累积”更多的乘法，将它们提高到所需的幂)。例如(未测试)

int h(String s) {
  int res = 0;
  int n = ht.length;

  for (int i = s.length() - 1; i >= 0; i--) {
     // using a long here to prevent premature wrapping
     long t = res * 256L + s.charAt(i);
     res = (int)(t % n);
  }
  return (res + 1) % n;
}

另请注意，ht.length 不应为 2 的幂(因此您不能跳过循环中的模约减，如果 ht.length 是 2 的幂)，因为如果它是 2 的幂，那么哈希值(至多)取决于前 4 个字符，这显然很糟糕。