â Blog

## Intro đ

Last time, we learned what a Hash Table is and why we want to use it.

Today, weâll learn how to write a simple Hash Function.

## Problem: WHY do we need a Hash Function?

To access a value in an array, we need its index.

But we want to use our Hash Table with a key instead of an index, e.g. `user.name` instead of `user[0]`.

To convert the index to a key, we need a helper function that does this task for us.

This is where the hash functions comes into play.

## What is a Hash Function? âśď¸

For our Hash Table, we need a function, that converts a key into an array index.

Letâs use the example from the last post.

I want to build something like this:

``````const user = {
name: 'miku86',
homeCountry: 'Germany',
age: 33,
}``````

Because we want to use an array under the hood, the implementation could look like this:

``const user = [33, 'miku86', 'Germany']``

So when we want to get the correct index of:

• `name`, we want to run `myHashFunction("name")` and get back `1`.
• `homeCountry`, we want to run `myHashFunction("homeCountry")` and get back `2`.
• `age`, we want to run `myHashFunction("age")` and get back `0`.

As you can see, there is no order in the array, the array index is solely bound to the key.

Letâs think about the hash functionâs constraints:

Deterministic: Anytime we input the same key, we should get back the same array index, otherwise we wonât find our value, because our data doesnât change its place in the array.

Fast: We need to use the hash function every time we read, create, update, delete data, therefore it should be fast and shouldnât be connected to the length of the existing data (`O(1)`).

Uniform Distribution: Think about an array of length 2. If we want to add 3 values to an array with 2 places to store data, we would have to store 2 values in 1 place (or lose data (we donât want to do that)). This would be a collision, meaning two values live at one place. Because collisions lead to additional computational work (we have to find the desired value), we want an uniform distribution of our array indexes.

## How do we build a Hash Function? đ

There are a lot of hash functions out there. Because we want to learn about the bigger concepts, our hash function will be far (really far) away from being good.

### Version 1: length of the key

Letâs be creative and think about a simple hash function, that could probably work, letâs take the length of our key.

The length of:

• `name` is 4
• `homeCountry` is 11
• `age` is

This works for this small example. But as you can guess, there is a high probability that this will lead to collisions very quickly. If we increase the amount of our key-value pairs to 100 instead of 3, we would end up with an array that has a lot of collisions between index ~3 and 10, because most (english) words are fairly short in length, so many keys would get the same hash.

### Version 2: sum of character codes of the key

Every character has a UTF-16 code. JavaScript has a function to get this value, `charCodeAt`.

Example: `name` has the charcodes:

• n: `110`
• a: `97`
• m: `109`
• e: `101`

If we sum these charcodes, we get `417`.

### Implementation of our simple (but not-so-good) hash function

• split the key into its characters: `name` => `n`,`a`, `m`, `e`
• convert every character into its character code: n: `110`, a: `97`, m: `109`, e: `101`
• sum all character codes: 110 + 97 + 109 + 101 => 417
``````const hash = key => {
// split the key into its characters
const chars = key.split('')

// convert every character into its character code
const charCodes = chars.map(char => char.charCodeAt())

// sum all character codes
const charCodeSum = charCodes.reduce((acc, cur) => acc + cur)

// return the sum
return charCodeSum
}``````

Result:

``````hash('name')
// 417``````

## Thoughts đ­

We created a simple hash function to grasp the concept.

The hash function takes a key as input and returns the array index where it should get saved.

As you can see, hash functions are a very complex topic. If you want to dive deeper into it, I invite you to read the `Further Reading` section.

## Next Part âĄď¸

We will learn how to handle collisions.

Donât miss interesting stuff, go to!