Algorithms – Hash Function Classification

Without trying to go into proofs, I'd say that such a beast does not exist for generic integers. Your problem would ultimately boil down to finding a hash function H with x>y → H(x) > H(y); with the constraint that the output of H is a finite set, and assuming that x∊ℕ (or in another set S with |S|>|image(H)|), there would necessarily be x₁>x₂∊ℕ with H(x₁)≤H(x₂).

If, however, you have both variables from a finite set, e.g. N-bit integer representations r(x). you could trivially define H(x₁,x₂)=r(x₁)||r(x₂) and satisfy your requirement.

If you want to build a hash table in Java, you should take advantage of the hashCode and equals methods which every object has, so there is no need to devise a custom hash function. Note that all Java “characters” are already numbers in the range 0x00 – 0xFFFF (they are UTF-16 code units, not ASCII characters or bytes).

Your idea of having the hash code be a Base-26 or Base-128 interpretation is a good idea for alphabetic-only/ASCII-only texts. But there are a few issues I can see:

• Strings do not only contain ASCII letters, but also symbols or spaces. Frequently, text will contain Unicode characters which have no ASCII equivalent.

• A hash code is an integer. To find a bucket, you'd do buckets.get(hashCode % buckets.size()). However, Java integers hold 32 bits, which offers enough bits for roughly 4.5 ASCII characters. Assuming your implementation left-shifts by seven bits and “or”s the new bits to the current hash code,

  int hashCode = 0;
  for (char c : str) {
      hashCode <<= 7;
      hashCode |= c & 0x7F;
  }
  

  then only the last 5 characters would be significant. This makes it extremely easy to create hash collisions: civilisation and train station.

  This can be avoided by a cleverer hash function where any bit will stay somehow significant. E.g the bits in the hash code could be rotated rather than shifted, and new bits could be “xor”ed to the existing value:

  int hashCode = 0;
  for (char c : str) {
      // rotate the bits
      hashCode = (hashCode << 1) | (hashCode >> (32 - 1));
      // xor new bits
      hashCode ^= c;
  }
  

  Java uses a slightly different hash function:

  for (char c : str) {
      hashCode = 31 * hashCode + c;
  }
  

  The multiplication with 31 makes sure that all bits are eventually used without making any bit irrelevant. Overflow is no problem due to the modulo operation when determining a bucket. The value of 31 is largely unimportant, but it being a prime number avoids hash collisions.