CodingGyan

Java String hashCode

medium JVM, Memory and Performance

Problem

Java computes the hash code of a string s of length n as s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1], where s[i] is the character code, and all the arithmetic is done with 32-bit signed integers that wrap around on overflow. Print the hash code of the given word (it can be negative).

Constraints

  • 1 <= length <= 100
  • lowercase letters

Examples

Input

abc

Output

96354

Solutions

Best approachTime O(n)Space O(1)

Horner's rule computes the polynomial with one multiplication and one addition per character. Because the arithmetic wraps at 32 bits, long words give negative values.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Compute hashCode.
 * Input   : One word.
 * Output  : The hash code.
 * Approach: Horner's rule
 * Time    : O(n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static int solve(String s) {
        // Step 1: Horner's rule: h = h * 31 + next character. int arithmetic wraps around by itself, like the real hashCode.
        int h = 0;
        for (int i = 0; i < s.length(); i++) {
            h = 31 * h + s.charAt(i);
        }
        return h;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.hasNextLine() ? scanner.nextLine() : "";
        System.out.println(solve(s));
    }
}
Hints (2)
  1. Why does a long word give a negative hash?
  2. What is a wrapped int?

Try these next