不使用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个字符,显然很糟糕.