Hash collision: "NO" means "YES" This Code Golf was inspired by the recent Daily WTF article You Can't Handle the True!, which features a string comparison written as:

String yes = "YES";
if ((delay.hashCode()) == yes.hashCode())


Imagine the trouble it would have caused for Steve's team if Java's String.hashCode method just happened to be implemented in a way that "YES".hashCode() == "NO".hashCode().  So, the challenge I propose here is:


  Write, in as few characters as possible, a hash function (I'll call it
  h) with a string parameter and integer return value, such that
  h("YES") is equal to h("NO").


Of course, this would be trivial to do with a function like def h(s): return 0, which makes a hash collision for every string.  To make this challenge more interesting, you must abide by the following additional rule:


  Of the other 18 277 possible strings consisting of three or fewer
  uppercase ASCII letters (^[A-Z]{0,3}$), there must be no hash
  collisions.


Clarification (pointed out by Heiko Oberdiek): The input string may contain characters other than A-Z, and your code must be able to hash arbitrary strings.  (You may, however, assume that the input is a character string rather than a null pointer or an object of some other data type.)  However, it does not matter what the return value is for strings that do not match ^[A-Z]{0,3}$, as long as it's an integer.

Furthermore, to obfuscate the intent of this function:


  Your code must not include any of the letters 'Y', 'E', 'S', 'N', or
  'O' (in either upper- or lowercase) within character or string
  literals.


Of course, this restriction doesn't apply to language keywords, so else, return, etc. are fine.
32-bit Python 2.x (19)

hash(w*9)%537105043


RSA uses a semiprime modulus, and that makes it secure, so using one with my hash algorithm should surely make it even better!1

This is a pure math function, works for all strings (hell, works for any hashable Python object), and doesn't contain any conditionals or special-casing! 32-bit Python can typically be called as python-32 on most systems that have both installed2.

I've tested this, and it returns 18,278 different values for the 18,279 3-letter-or-less uppercase strings. Assigning this to a function takes 11 more bytes:

h=lambda w:hash(w*9)%537105043


and h('YES') == h('NO') == 188338253.

64-bit Python 2.x (19)

hash(w*2)%105706823


Same deal as above.



To come up with these numbers, a little bit of modular math was used. I was looking for a function f and a modulus n such that hash(f('YES')) % n == hash(f('NO')) % n. This is equivalent to testing that n divides d = hash(f('YES')) - hash(f('NO')), i.e. we only have to check the factors of d for suitable values of n.

The ideal n is in the neighbourhood of 20000**2 to reduce the chance of a birthday paradox collision. Finding a suitable n turns out to be a bit of trial and error, playing with all the factors of d (there usually aren't many) and different choices for the function f. Notice though that the trial and error is only needed because I wanted to make n as small as possible (for golfing). If that wasn't a requirement, I could just choose d as my modulus, which is usually sufficiently large.

Note too that you can't pull this trick off using just f(s) = s (the identity function) because the rightmost character of the string has essentially a linear relationship (actually an XOR relationship) with the final hash (the other characters contribute in a much more nonlinear way). The repetition of the string therefore ensures that the differences between the strings are amplified to eliminate the effect of changing only the rightmost character.



1 This is patent nonsense.
2 Python string hashing depends on major version (2 vs 3) and bitness (32-bit vs 64-bit). It does not depend on platform AFAIK.