java – 不使用Math.BigInteger的高功率模数

发布时间：2020-12-15 04:48:37 所属栏目：Java 来源：网络整理

导读：我必须把这个公式变成 java代码：如果我可以使用像Math.BigInteger这样的库会更容易,但遗憾的是我应该在没有它的情况下这样做. stackoverflow上的一些类似问题建议编写一个自己的bignum库,但我想在没有它的情况下这样做. 现在,我的进展是在这一步： int h(S

我必须把这个公式变成 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;
}

我知道功率值在整数范围内变得非常快,所以我想到编写一个自己的方法来计算值的幂和模数.我的数学知识还不足以知道何时使用模数以及如何轻松实现.

提前致谢！

解决方法

如果你从后面走,你根本不需要任何权力.在每一步简单地乘以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的幂,那么hash取决于(最多)前4个字符,这显然很糟糕.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!