> So it exponentiates 31 by one less than the length of the string and multiples that with the first character's ascii, then exponentiates 31 by two less than the length of the string and multiples that with the second character's ascii, and so on and so forth, and sums the whole mess. And I'm supposed to know this.
It's not such a "mess" if you see that it just evaluates the string as a polynomial.
> Now, in his defense, computing the dot product of the string with a random prime vector is a well known Universal Multiplicative Hash Function, but forgive me, father, for I did not pay much attention to this invaluable nugget in my Algorithms 101.
Well, I didn't pay much attention in such a class either, but isn't that just intuitively obvious? Dot-product a vector `x` with a vector `p` of (unique) primes, and well, you've got yourself a number unique to `x`.
The question was explain the exact approach Java uses to hash strings, not come up with a way to hash string or explain why does this particular approach work for hashing strings.
Much like hashes themselves going one direction is much harder than the other.
Meanwhile, my actual Google interviewer asked me how I might do it. He then explained why my Gödel numbering scheme was bad, showed me how Java does it, was seemingly satisfied enough and offered me a job on his team.
Google has a bad rep, but it is possible to sort it out.
It's not such a "mess" if you see that it just evaluates the string as a polynomial.