Strong (non-secure) hash functions

Having defined the related notions of strong and secure hash functions, we'll look at an example of a hash function that we would designate strong but not secure. In other words, collisions cropping up by chance are negligible in everyday use, but we could easily calculate or find items (even if by trial and error) that would have collisions if we deliberately wanted to.

Typical uses of a strong, non-secure, hash function would be where:

• we assume that the hash code represents the actual item in some way, for example:
  • in a hash table, we store just the hash code and value, without the actual key used to create the hash code;
  • in looking for duplicates, we just store a set of hash codes; if an item's hash code is in the set, we treat it as though the actual item was there;
• a false match, while unlikely, wouldn't be critical;
• we still want the convenience of fairly short hash codes.

A strong hash function will tend to have these properties:

• it will be moderately fast to calculate, but compared to the simplest hash codes, will trade some CPU and memory access for better hash quality;
• it will be wide enough to handle about as many objects as we're likely to store in a collection (up to, say, tens or hundreds of millions) with negligible chance of a collision;
• it will be a "medium-to-good quality" hash that is likely to produce a fairly random mix of bits for its input, and which isn't prone to weaknesses from specific combinations of input bytes/values¹;
• it will be of a width that is fast to operate on.

In practice, these constraints nearly always point towards a 64-bit hash function. The width clearly needs to be "several bits more than 32". Other widths around 64 would be equally or even more adequate, but all modern processors have support for 64-bit arithmetic.

An example 64-bit hash function

As an example, we'll look a Java implementation of the 64-bit hash function suggested in Numerical Recipes (3rd Edition). The essential idea is as follows:

• generate an initial table of 256 random longs, each of which will have roughly half its bit set in random positions;
• use the "multiply and add" approach (in fact, we XOR rather than add), but:
  • multiply by a long found to give good results in LCG generators;
  • rather than adding in "raw" bytes, use those bytes as an index into the table of random numbers.

The authors suggest initialising the table with an XORShift generator, seeded with what is (presumably) a value that they found to give good results. (XORShift generators have a slight weakness that they can go through sequences with few bits set; I assume that the authors found this starting value to give numbers that avoided that property.) In Java, using their start value and XORShift parameters, we could code this as follows:

public class StrongHash {
  private static final long[] byteTable;
  
  static {
    byteTable = new long[256];
    long h = 0x544B2FBACAAF1684L;
    for (int i = 0; i < 256; i++) {
      for (int j = 0; j < 31; j++) {
        h = (h >>> 7) ^ h;
        h = (h << 11) ^ h;
        h = (h >>> 10) ^ h;
      }
      byteTable[i] = h;
    }
  }

Now, to calculate the hash code of some byte sequence, we proceed as mentioned:

private static final long HSTART = 0xBB40E64DA205B064L;
private static final long HMULT = 7664345821815920749L;

public static long hashCodeOf(byte[] bytes) {
  long h = HSTART;
  final long hmult = HMULT;
  final long[] ht = byteTable;
  for (int i = 0; i < bytes.length; i++) {
    h = (h * hmult) ^ ht[bytes[i] & 0xff];
  }
  return h;
}

Recall that ANDing with 255 (0xff hex) converts a (signed) Java byte into an unsigned value in the range 0-255, which we can then use as an index into the array of random numbers.

To produce a hash of other objects using this method, we have a couple of options:

• if the object has a toString() method, we can use String.getBytes() to get a byte array representation of the object for hashing;
• otherwise, we can use a ByteBuffer to help us convert the state variables of the object into a byte array.

1. For example, a hash function that simply "multiplies and adds" successive values directly (such as that used by the Java String class, or those auto-generated by IDEs such as Eclipse) is prone to accumulating zeroes in its lower bits when successive bytes have zeroes in those bits (as an example, look at what happens when you call hashCode() on strings consisting of sequences of spaces).