3 ms·
And then the author writes: > Now, in his defense, computing the dot product of the string with a random prime vector is a well known Universal Multiplicative
by radicality 11y ago
And then the author writes:
> 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`.
- dagw 11y agoThe 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.
- CHY872 11y agoMeanwhile, 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.
- dagw 11y agoThat sounds eminently reasonable.