# Effective Kotlin Item 43: Respect the contract of hashCode

This is a chapter from the book Effective Kotlin. You can find it on LeanPub or Amazon.

Another method from `Any`

that we can override is `hashCode`

. First, let’s explain why we need it. The `hashCode`

function is used in a popular data structure called *hash table*, which is used in a variety of different collections or algorithms under the hood.

### Hash table

Let’s start with the problem hash table was invented to solve. Let’s say that we need a collection that quickly both adds and finds elements. An example of this type of collection is a set or map, neither of which allow for duplicates. So whenever we add an element, we first need to look for an equal element.

A collection based on an array or on linked elements is not fast enough for checking if it contains an element, because to check that, we need to compare this element with all elements on this list one after another. Imagine that you have an array with millions of pieces of text, and now you need to check if it contains a certain one. It will be really time-consuming to compare your text one after another with those millions.

A popular solution to this problem is a hash table. All you need is a function that will assign a number to each element. Such a function is called a hash function, and it must always return the same value for equal elements. Additionally, it is good if our hash function:

- Is fast.
- Returns different values for unequal elements, or at least has enough variation to limit collisions to a minimum.

Such a function categorizes elements into different buckets by assigning a number to each one. What is more, based on our requirement for the hash function, all elements equal to each other will always be placed in the same bucket. Those buckets are kept in a structure called hash table, which is an array with a size equal to the number of buckets. Every time we add an element, we use our hash function to calculate where it should be placed, and we add it there. Notice that this process is very fast because calculating the hash should be fast, and then we just use the result of the hash function as an index in the array to find our bucket. When we search for an element, we find its bucket the same way, and then we only need to check if it is equal to any element in this bucket. We don’t need to check any other bucket, because the hash function must return the same value for equal elements. This way, at a low cost, it divides the number of operations needed to find an element by the number of buckets. For instance, if we have 1,000,000 elements and 1,000 buckets, searching for duplicates only requires to compare about 1,000 elements on average, and the performance cost of this improvement is tiny.

To see a more concrete example, let’s say that we have the following strings, and a hash function that splits into 4 buckets:

Text | Hash code |
---|---|

"How much wood would a woodchuck chuck" | 3 |

"Peter Piper picked a peck of pickled peppers" | 2 |

"Betty bought a bit of butter" | 1 |

"She sells seashells by the seashore" | 2 |

Based on those numbers, we will have the following hash table built:

Index | Object to which hash table points |
---|---|

0 | [] |

1 | ["Betty bought a bit of butter"] |

2 | ["Peter Piper picked a peck of pickled peppers", "She sells seashells by the seashore" ] |

3 | ["How much wood would a woodchuck chuck"] |

Now, when we are checking if a new text is in this hash table, we are calculating its hash code. If it is equal to 0, then we know that it is not on this list. If it is either 1 or 3, we need to compare it with a single text. If it is 2, we need to compare it with two pieces of text.

This concept is very popular in technology. It is used in databases, in many internet protocols, and in standard library collections in many languages. In Kotlin/JVM both the default set (`LinkedHashSet`

) and the default map (`LinkedHashMap`

) both use it. To produce a hash code, we use the `hashCode`

function^{1}.

### Problem with mutability

Notice that a hash is calculated for an element only when this element is added. An element is not moved when it mutates, because the collection does not know it has changed. So after element is changed, it might be in an incorrect bucket. This is why both `LinkedHashSet`

and `LinkedHashMap`

key will not behave properly when an object mutates after it has been added:

This problem was already noted on *Item 1: Limit mutability*: Mutable objects are not to be used in data structures based on hashes or on any other data structure that organizes elements based on their mutable properties. We should not use mutable elements for sets or as keys for maps, or at least we should not mutate elements that are in such collections. This is also a great reason to use immutable objects in general.

### The contract of hashCode

Knowing what we need `hashCode`

for, it should be clear how we expect it to behave. The formal contract is as follows (Kotlin 1.3.11):

Whenever it is invoked on the same object more than once, the

`hashCode`

method must consistently return the same integer, provided no information used in`equals`

comparisons on the object is modified.If two objects are equal according to the

`equals`

method, then calling the`hashCode`

method on each of the two objects must produce the same integer result.

Notice that the first requirement is that we need `hashCode`

to be **consistent**. The second one is the one that developers often forget about, and that needs to be highlighted: ** hashCode always needs to be consistent with equals, and equal elements must have the same hash code.** If they don’t, elements will be lost in collections using a hash table under the hood:

This is why Kotlin suggests overriding `hashCode`

when you have a custom `equals`

implementation.

There is also a requirement that is not required, but very important if we want this function to be useful. `hashCode`

should spread elements as widely as possible. Different elements should have the highest possible probability of having different hash values.

Think about what happens when many elements are placed in the same bucket - there is no advantage in using a hash table! An extreme example would be making `hashCode`

always return the same number. Such a function would always place all elements into the same bucket. This is fulfilling the formal contract, but it is completely useless. There is no advantage to using a hash table when `hashCode`

always returns the same value. Just take a look at the examples below where you can see a properly implemented `hashCode`

, and one that always returns 0. For each `equals`

we added, a counter counts how many times it was used. You can see that when we operate on sets with values of both types, the second one, named `Terrible`

, requires many more comparisons:

### Implementing hashCode

We define `hashCode`

in Kotlin practically only when we define custom `equals`

. When we use the data modifier, it generates both `equals`

and a consistent `hashCode`

. When you do not have a custom `equals`

method, do not define a custom `hashCode`

, unless you are sure you know what you are doing, and you have a good reason. When you have a custom `equals`

, implement `hashCode`

that always returns the same value for equal elements.

If you implemented typical `equals`

that checks equality of significant properties, then a typical `hashCode`

should be calculated using the hash codes of those properties. How can we make a single hash code out of those many hash codes? A typical way is that we accumulate them all in a result, and every time we add the next one, we multiply the result by the number 31. It doesn’t need to be exactly 31, but its characteristics make it a good number for this purpose. It is used this way so often, that now we can treat it as a convention. Hash codes generated by the data modifier are consistent with this convention. Here is an example implementation of a typical `hashCode`

together with its `equals`

:

One helpful function on Kotlin/JVM is `Objects.hash`

, that calculates hash of multiple objects using the same algorithm as presented above:

There is no such function in the Kotlin stdlib, but if you need it on other platforms you can implement it yourself:

The reason why such a function is not in the stdlib is that we rarely need to implement `hashCode`

ourselves. For instance, in the `DateTime`

class presented above, instead of implementing `equals`

and `hashCode`

ourselves, we can just use `data`

modifier:

When you do implement `hashCode`

, remember that the most important rule is that it always needs to be consistent with `equals`

, and it should always return the same value for elements that are equal.

Often, after some transformations, as `hashCode`

returns `Int`

, that is 32-bit signed integer, meaning 4294967296 buckets, which is too much for a set that might contain only one element. To solve this problem, there is a transformation that makes this number much smaller. When it is needed, the algorithm makes the hash table bigger through a transformation and assigning all elements to new buckets.