JavaScript Data Structures: Hash Table: Hash Function
Tags: beginners, tutorial, javascript, webdev
Published: 2020-02-18 11:20:39

---
title: "JavaScript Data Structures: Hash Table: Hash Function"
description: "JavaScript Data Structures: Hash Table: Hash Function"
published: true
tags: ["Beginners", "Tutorial", "JavaScript", "Webdev"]
series: JavaScript Data Structures
---

## Intro 🌐

[Last time](https://dev.to/miku86/javascript-data-structures-hash-table-intro-3nce), 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:

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

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

```js
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](https://en.wikipedia.org/wiki/List_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`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/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

Our tasks:

- 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

```js
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:

```js
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](https://miku86.com/)!

---

## Further Reading 📖

- [Simple Wiki: Hash Function](https://simple.wikipedia.org/wiki/Hash_function)
- [Wikipedia: Hash Function](https://en.wikipedia.org/wiki/Hash_function)
- [Wikibooks: Hash Function](https://en.wikibooks.org/wiki/Data_Structures/Hash_Tables#Choosing_a_good_hash_function)
- [Wikipedia: List of Hash Functions](https://en.wikipedia.org/wiki/List_of_hash_functions)

---

## Questions ❔

- What's the easiest method to generate a collision with our hash function?
- How can we improve our hash function?
- What are the advantages of our implemented hash function?
- What are the disadvantages of our implemented hash function?