---

6.19.1 Hashing user-defined structures ¶

Additionally, there is a function hash(int[]) that can be helpful when constructing hash methods for user-defined structures: convert all the fields to integers (possibly by hashing them), put these integers into an array, and hash the array.

Let’s return to the example of the Person structure from Structures, adding an age field to make it more interesting. For this structure, there are two reasonable ways we might define a hash function for it. The first is to create a hash function based on all the fields of the structure:

struct Person {
  string firstname;
  string lastname;
  int age;
  int hash() {
    return hash(new int[] {firstname.hash(), lastname.hash(), age});
  }
  autounravel bool operator ==(Person a, Person b) {
    if (alias(a, null)) return alias(b, null);
    if (alias(b, null)) return false;
    return a.firstname == b.firstname &&
           a.lastname == b.lastname &&
           a.age == b.age;
  }
  autounravel bool operator !=(Person a, Person b) {
    return !(a == b);
  }
}

This approach is necessary if we are redefining the == operator. Two Persons are equal if they have the same first name, last name, and age.

The default == operator for user-defined structs considers two objects equal if they are the same object, meaning that changes to one will be reflected in the other. A hash method that plays well with the default == operator must remain the same even if the fields change. In this case, we can add a never-changing id field that uniquely identifies a Person object, and use that for hashing:

struct Person {
  string firstname;
  string lastname;
  int age;
  private static int lastID=-1;
  restricted int id = ++lastID;
  int hash() {
    return id.hash();
  }
}

The builtin hash functions are designed to remove undesirable regularity (with respect to modular arithmetic) when applied exactly once. This explains why the second example returns id.hash() instead of id, while age is not independently hashed in the first example. It may sometimes be most practical to feed the hash function’s output back into it, as in firstname and lastname above, but this does not increase the hash quality; in theory, if we could serialize a Person object to a string and then hash the string, the hash quality would be even higher.