Integers, characters and enumerations

Since the value of a hash function should be an integer, it is very easy to just let value be its own hash code, if it’s an integer.

$$\mathbf{h}(x) = x$$

This function is clearly deterministic and preserves equality, and it is very efficient too. But how about the distribution – is it uniform?

This depends on how the keys are distributed in the data, and this depends on the application we have in mind. As an example, assume that we only have even-numbered keys in our data – then only half of all possible hash codes will be used.

A more realistic example is if we want to search for people using their length. Person lengths are not uniformly distributed, but instead they have a normal distribution. This means that the hash codes will also be normal distributed, and there will be many collisions for lengths that are closer to the average length.

However, despite the possibly skewed distribution, it is still quite common to use a number as its own hash code. The reason for this is that it is so simple and efficient to do so.

Note that this simple strategy works for all kinds of atomic values, such as Unicode characters or enumeration types. All these are anyway encoded as integers internally by the compiler.

Floating point numbers

There is an international standard for encoding floating point numbers, called IEEE 754, which almost all modern processors use. The details of the encoding are not important, what matters to us is that it encodes every floating point number in a fixed number of bytes.

One very easy and common hash function for floating point numbers is to simply use it as it is, but interpret the byte sequence as an integer. This means that the floating point value 42.0 will not have the hash code 42, but instead something completely different. However, this is not a problem in our case since the only thing we need to know is that it respects the requirements of a hash function. Just as above, it is clearly both efficient, deterministic and preserves equality, and the distribution is most definitely not worse than the integer distribution.

Strings

But how can we handle more complex values, such as strings? A string is a sequence of characters, of arbitrary length, so how can we calculate a good hash code for a given string?

• How about taking the hash code of the first character in the string? No, that’s not a good idea because you will get an awful distribution – all strings starting with “a” will get the same hash code, such as “abacus”, “ape”, and “aperture”.

• So, perhaps we can take the sum of the first, the middle and the last characters? That’s better but still not very good – common strings such as “state”, “summarise” and “signature” will get the same hash code.

In both these cases the hash function will have a very skewed distribution, and the main reason is that they don’t take every single character into account. So an important rule of thumb is to use every part of a complex object when calculating the hash code. But how should these hash codes be combined? One way is to just sum all of them:

function hashCode(string):
    code = 0
    for each char in string:
        code = code + hashCode(char)
    return code

This is much better than the previous suggestions, but still not very good. Each character in the string will influence the final hash code, but it does not take their internal order into account. Therefore all the following strings will get the same hash code: “alter”, “later”, and “alert”.

Horner’s method for strings, lists and other sequences

So we want our hash function to take all character in a string into account, but also their position in the string. One common way is to treat the sequence of characters, $s=c_0c_1\ldots c_n$ as a polynomial over some constant $p$, like this:

$$\mathbf{h}(c_0c_1c_2\ldots c_n) = c_0 + c_1p + c_2p^2 + c_3p^3 + \cdots + c_np^n$$

This kind of polynomial can be calculated efficiently using Horner’s method, as a nested multiplication:

$$\mathbf{h}(c_0c_1c_2\ldots c_n) = c_0 + p\left(c_1 + p\left(c_2 + p\left(c_3 + \cdots + p(c_{n-1} + pc_n)\cdots\right)\right)\right)$$

Which in turn is just a fancier way of writing a simple loop over all characters, and accumulating the hash code:

function hashCode(string):
    code = 0
    for each char in string:
        code = p*code + hashCode(char)
    return code

To get the best distribution, we should use a not-too-small prime number for $p$. (The standard hash function for strings in Java is exactly like this, where they use $p=31$.)

Note that Horner’s method can be used for all kinds of sequences, such as lists or tuples.

Complex values

So how can we handle complex values, such as general datatypes or objects? E.g., how do we define a hash function for the following datatype for person names:

datatype Person:
    firstName: String
    middleName: String
    lastName: String

We can use the same strategy as we did for strings – simply treat the three elements as a sequence and apply Horner’s method:

datatype Person:
    ...
    hashCode():
        code = 0
        for part in (firstName, middleName, lastName):
            code = p*code + part.hashCode()
        return code

However, sometimes we don’t want to use all instance variables when calculating the hash code. Assume that we want to be able to search for just the last name, i.e., to find all persons having the same last name. Then we can build a hash table of persons, where the hash codes are only calculated from the last names. If we want to also be able to search for first names, we have to build another hash table – where the hash codes are calculated from the first names.