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']
(1), 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.
Top comments (0)