Java – no math High power modulus of BigInteger

I have to turn this formula into Java code:

If I can use something like math A library like BigInteger would be easier, but unfortunately I should have done it without it Some similar problems on stack overflow suggest writing your own bignum library, but I want to do so without it

Now, my progress is at this step:

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;
}

I know that the power value becomes very fast in the integer range, so I want to write my own method to calculate the power and modulus of the value My mathematical knowledge is not enough to know when to use modulus and how to implement it easily

Thank you in advance!

Solution

If you walk from the back, you don't need any power at all Simply multiplying by 256 at each step will produce the same effect (the subsequent values "accumulate" more multiplications and raise them to the required power) For example (untested)

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;
}

Also note that HT Length should not be a power of 2 (so you can't skip the modulus reduction in the loop. If ht.length is a power of 2, you can do so), because if it is a power of 2, the hash depends on (at most) the first four characters, which is obviously bad