Starting Hash Tables

Arrays are one of the most commonly used data structures in code. But what if we wanted to create a hash table from an array? Hashes have different names according to what language you’re coding in, but they all essentially refer to the same idea. Dictionaries in Python, Hashes in Ruby and objects in Javascript. You have a key-value pair, which makes searching through hash tables, if you know the key, O(1).

Think of a library. If you know the title of the book, you can go to the isle containing all the books starting with the first letter of your title, walk down and find your book, assuming all the books are in alphabetical order. This takes relatively less time, so it’s O(1), meaning you almost immediately find your book. This is much easier than knowing the title of the book, but all the books are put on the shelf randomly, which means you have to go through however many books there are, say N number of books, and look through each book one by one. This would take O(N) time.

A hash table is sort of like using an organized library. I found a tutorial to code along to to make a hash table in Javascript.

https://dev.to/miku86/javascript-data-structures-hash-table-intro-3nce

// Source: https://dev.to/miku86/javascript-data-structures-hash-table-intro-3nce
// In terminal, run with
// $ node --experimental-modules HashTable.js
// This allows you to import modules in ES6 format/syntax
// Looks for the closest parent `package.json` file
// Make sure the closest package.json file contains the key-value pair:
/**
* {
*   "type": "module"
* }
*/
class HashTable {
constructor() {
this.data = [];
this.size = 0;
}
// Create a hash table by adding up all the UTF-16 values of each letter in the string
hash = (key) => {
const chars = key.split('');
const charCodes = chars.map(char => char.charCodeAt());
const charCodeSum = charCodes.reduce((acc, cur) => acc + cur);
return charCodeSum;
}
// Add a key-value pair
set(key, value) {
// Hash the key
const hash = this.hash(key);
if (!this.data[hash]) {
this.data[hash] = [];
}
this.data[hash].push([key, value]);
this.size++;
}
}
//  console.log("hash('name): ", hash('name'));
// 417
const newHashTable = new HashTable();
console.log("newHashTable: ", newHashTable);
// console.log("newHashTable.hash('name'): ", newHashTable.hash('name'));
newHashTable.set("name", "miku86");
console.log(newHashTable.data);
newHashTable.set("mean", false);
console.log(newHashTable.data);
newHashTable.set("age", 33);
console.log(newHashTable.data);

I’m part way through the tutorial, and have a constructor for the class, a hash(key) method and a set(key, value) method.

I find doing these tutorials is the best way for me to learn about what is really happening under the hood.

I’m creating hashes by converting each letter in the hash(key) key parameter to UTF-16 code, and then adding those codes together to get a sum. The sum is the key in my hash table. Of course, there may be collisions or two keys that have the same sum. For instance, “name” and “mean”. In this case, I store the entire key-value pair in an array and push it into the slot on my hash table. 🔐 🔑

That’s all I’m up to for now, and I will continue implementing this!