Hashing with Hash Functions

Do you remember those secret codes you used as a kid to create and decipher messages? For example, here’s a simple way to map letters to numbers:

A = 1
B = 2
C = 3
D = 4
E = 5

and so on. According to this code,

ACE converts to 135,
CAB converts to 312,
DAB converts to 412,

and

BAD converts to 214.

This process of taking characters and converting them to numbers is known as hashing. And the code that is used to convert those letters into particular numbers is called a hash function.

Many other hash functions exist besides this one. Another example of a hash function may be to take each letter’s corresponding number and return the sum of all the numbers. If we did that, BAD would become the number 7 following a two-step process:

Step 1: First, BAD converts to 214.

Step 2: We then take each of these digits and get their sum:

2 + 1 + 4 = 7

Another example of a hash function may be to return the product of all the letters’ corresponding numbers. This would convert the word BAD into the number 8:

Step 1: First, BAD converts to 214.

Step 2: We then take the product of these digits:

2 * 1 * 4 = 8

In our examples for the remainder of this chapter, we’re going to stick with this last version of the hash function. Real-world hash functions are more complex than this, but this multiplication hash function will keep our examples clear and simple.

The truth is that a hash function needs to meet only one criterion to be valid: a hash function must convert the same string to the same number every single time it’s applied. If the hash function can return inconsistent results for a given string, it’s not valid.

Examples of invalid hash functions include functions that use random numbers or the current time as part of their calculation. With these functions, BAD might convert to 12 one time and 106 another time.

With our multiplication hash function, however, BAD will always convert to 8. That’s because B is always 2, A is always 1, and D is always 4. And 2 * 1 * 4 is always 8. There’s no way around this.

Note that with this hash function, DAB will also convert into 8 just as BAD will. This will cause some issues that I’ll address later.

Armed with the concept of hash functions, we can now understand how a hash table works.