This article was originally posted on my blog Hashtables for newbies

HashTables

Before we make a hashtable, let's talk about its components arrays, functions, and hashing. read them even if you know!

Components

Arrays?

const colors = ['red','blue','orange']

if we console.log(colors[0]) the console displays the head which is red, we wrote the elements by this order and know what each index points to which color. This easy and explicit.

Functions?

Functions are cool boxes, you pass it a value and tell it how to generate a result from it.

Have you ever wrote this in linear algebra class f(x) = x+5? in programming you can write it in same way const f = x => x+5, if we pass it a 3 the function returns 8 no fancy here.

Hashing?

Hashing is kinda blackbox in tech talks, in other words it's a bunch of steps you're doing to convert a something to a unique hash or value, it's a oneway you can't go back. In programming we write those bunch of steps (hash Algorithm) in a function called hash function.

Objects?

A key-value represented, like arrays but in array you get the value by index, in objects you get the value by its special key.

const white = {code: '#fff', type: 'color'}

If we want the code of white we simply write white['code']⁽¹⁾, easy and fast huh?

What is the hashtable?

In a simple sentence, Hashtable is data-structure to help you using an ordinary array as a key-value array!

Let's exploring How?

We have a colors array like this:

const  colors  = [{color:  'white', code:  '#fff'},
{color:  'orange', code:  '#fc3'}];

and The problem is we have to find the code of the color orange?!
without Hashtable the first naive solution is iterating the whole array and if color is orange display the code! slow, right?

colors.map(color  =>
  {
    if (color['color'] ===  'orange')
    console.log(color['code']);
  }
);

Let's take another approach, converting it into a key-value array.
convert the last array to this array:

const  colors  = ['#fff','#fc3'];

and if we write colors['orange'] the console displays #fc3!
To do this we have to hash the word white and orange to be equal index in size which is >= zero and less than the array size.

const  colors  = [];

const  hashFunction  =  key  => {
  const  letters  =  key.split('');
  const  hashValue  =  letters.reduce((acc, cur) =>
  acc  +  cur.charCodeAt(0), 0)
  % (!colors.length  ?  1  :  colors.length+1); 

  // in the line above, we made a '%' to range the
  // value to be between zero (included) and the length of
  // the list

  return  hashValue;
} 
colors[hashFunction('orange')] =  '#fc3';
colors[hashFunction('white')] =  '#fff';

console.log(colors[hashFunction('orange')]); // '#fc3'

Wow! that's Great! but if we have two colors return the same index we call it Collision, what should we do?!
In the actual implementations for the hashtable, the hash function must avoid the collision with two constraints:

• The index must be unique for each word.
• The index must be >= zero and < list length.

Notes:

(1) Write it white['code'] don't white[code] whatever you wrote code in the object to avoid conflicts between ordinary variables.