DEV Community

Cover image for Completed JavaScript Data Structure Course, and Here is What I Learned About Hash Table.
Maiko Miyazaki
Maiko Miyazaki

Posted on • Updated on

JavaScript Hashtable Completed JavaScript Data Structure Course, and Here is What I Learned About Hash Table.

In the last few articles, I wrote overviews of Linked List, Queue, Stack, Binary Search Tree, and Binary Heap that I learned while taking JavaScript Data Structures and Algorithms Course on Udemy. At the same time, I was in search of a better structure that will improve the time complexity for my Chrome Extension project.

Currently, I'm storing the main data as objects in an array like this:

// Result of console.log(MainData)
(4)[{...}, {...}, {...}, {...}]
0: {category: "Machine Learning", id: 4, definition: "the action of explaining the meaning of something", tag: ["noun"], word: "interpretation"}
1: {category: "Book1", id: 3, definition: "based on random choice or personal whim, rather than any reason or system.", tag: ["adj"], word: "arbitrary"}
2: {category: "Machine Learning", id: 2, definition: "the quality, condition, or fact of being exact and acurate", tag: ["noun"], word: "precision"}
3: {category: "Book2", id: 1, definition: "using or based on what one feels to be true even without conscious reasoning; instinctive", tag: ["adj"], word: "intuitive"}
Enter fullscreen mode Exit fullscreen mode

I'd like to implement features to delete/edit each data efficiently, but in this case, both of feature takes time complexity of O(n).

What I learned after Binary Heap was Hash Table. In this article, I'm going to think about if it can be suitable or not.

What is Hash Table?

Hash Table(also called Hash Map) is one of Hash-based structures. It looks similar to arrays -- we map index to values, but for Hash Table, we use keys instead of indexes.

array and hash table

Like Arrays, Hash Tables are built-in data structures for a lot of computer languages. In JavaScript, Object and Map provides a very efficient Hash Table structure.

For example, if we have a unique value like names in each data, we can use the name as its key. These features allow us to access a single item very quickly.

If it was a regular array, we needed to loop through each item to find an item. Thus, it takes time complexity of O(n).

let StudentResidence = [];

class Student {
    constructor(name, age, grade, licenceEnds) {
        this.name        = name;
        this.age         = age;
        this.grade       = grade;
        this.licenceEnds = licenceEnds;
    }
}

StudentResidence.push(new Student('Tara Joyce', 18, 'A', '11-06-2021'))
StudentResidence.push(new Student('Brian Brown', 19, 'A', '05-06-2020'))
StudentResidence.push(new Student('John Smith', 18, 'B', '07-06-2021'))

// To change Tara's age, we need to look up each item
for (let i=0; i<StudentResidence.length; i++) {
    if(StudentResidence[i].name === 'Tara Joyce') {
        StudentResidence[i].age = 19;
    }
}
Enter fullscreen mode Exit fullscreen mode

However, if it was stored in key-value pairs, no need to loop over the data.


let StudentResidence = {};

class Student {
    constructor(age, grade, licenceEnds) {
        this.age         = age;
        this.grade       = grade;
        this.licenceEnds = licenceEnds;
    }
}

StudentResidence['Tara Joyce']  = new Student(18, 'A', '11-06-2021');
StudentResidence['Brian Brown'] = new Student(19, 'A', '05-06-2020');
StudentResidence['John Smith']  = new Student(18, 'B', '07-06-2021');

// To change Tara's age, no need to look up each item
StudentResidence['Tara Joyce'].age = 19;

Enter fullscreen mode Exit fullscreen mode

We can also implement it with Map.

let StudentResidence = new Map();

class Student {
    constructor(age, grade, licenceEnds) {
        this.age         = age;
        this.grade       = grade;
        this.licenceEnds = licenceEnds;
    }
}

StudentResidence.set('Tara Joyce', new Student(18, 'A', '11-06-2021'));
StudentResidence.set('Brian Brown', new Student(19, 'A', '05-06-2020'));
StudentResidence.set('John Smith', new Student(18, 'B', '07-06-2021'));

// To change Tara's age, no need to look up each item
StudentResidence.get('Tara Joyce').age = 19

Enter fullscreen mode Exit fullscreen mode

These only take O(1) which is constant time.

Why it's that fast?

What happens behind the scene is that a Hash Table uses a hash function to compute an index from the key, and the index tells which array of buckets the value should be stored into. Therefore when we want to find where the value is stored, we can compute the index with the hash function and find out where the desired value is stored.

hash function picturised

Ideally, the hash function assigns each key to a unique bucket, but we need to consider the case when a hash function generates the same index for more than one key.

Dealing with collisions

There are many strategies to handle collisions, but we are going to look at two of the common ones here.

Method 1: Separate Chaining

With Separate Chaining, we store them at the same bucket nesting another sort of list inside. If it's implemented with Linked List or Array, lookup time will depend on the average number of keys per bucket.

hash function with separate chaining

Method 2: Linear Probing

Linear Probing is one of Open Addressing strategy, and with Open Addressing Strategy, we only allow one key-value set per bucket. When we find a collision, we search through the array until we find an unoccupied bucket.

hash function with linear probing

Should we implement our own hash function?

When we use JavaScript and trying to be fast and lightweight, firstly we should consider using regular Object or Map because it already handled efficiently. However, implementing our own hash table will help us understand what's going on behind the scene.

Implementation

Firstly, we define HashTable as an array.

class HashTable {
    constructor(size=53) {
        this.keyMap = new Array(size);
    }
    _hash(key) {

    }
    set(key, value) {

    }
    get(key) {

    }
}
Enter fullscreen mode Exit fullscreen mode

Hash Function

This hash function generates an index between 0 to 53 from a key.

_hash(key) {
    let total = 0;
    let WEIRD_PRIME = 31;
    for (let i = 0; i < Math.min(key.length, 100); i++) {
        let char = key[i];
        let value = char.charCodeAt(0) - 96;
        total = (total + WEIRD_PRIME * value) % this.keyMap.length;
    }
    return total;
}

Enter fullscreen mode Exit fullscreen mode

Insertion with Separate Chaining method

We create Array inside each bucket, so we will need to simply push the key-value pair into the array in the bucket.

set(key, value) {
    let index = this._hash(key);
    if (this.keyMap[index] === null) {
        this.keyMap[index] = [];
    } 
    this.keyMap[index].push([key, value]);
}
Enter fullscreen mode Exit fullscreen mode

Lookup

This only takes O(1) time for finding bucket, plus looping through the array inside the bucket.

get(key) {
    let target = this._hash(key);
    if (this.keyMap[target]) {
        for (let i = 0; i < this.keyMap.length; i++) {
            if (this.keyMap[target][i][0] === key) {
                return this.keyMap[target][i][1];
            }
        }
    }
    return undefined;
}
Enter fullscreen mode Exit fullscreen mode

Probably, Hash Table is What I was looking for!

So go back to the main topic -- What data structure will be suitable for the main data of my Chrome Extension project? The data is a list of vocabulary, and again, it looks like this:

// Result of console.log(main-data)
(4)[{...}, {...}, {...}, {...}]
0: {category: "Machine Learning", id: 4, definition: "the action of explaining the meaning of something", tag: ["noun"], word: "interpretation"}
1: {category: "Book1", id: 3, definition: "based on random choice or personal whim, rather than any reason or system.", tag: ["adj"], word: "arbitrary"}
2: {category: "Machine Learning", id: 2, definition: "the quality, condition, or fact of being exact and acurate", tag: ["noun"], word: "precision"}
3: {category: "Book2", id: 1, definition: "using or based on what one feels to be true even without conscious reasoning; instinctive", tag: ["adj"], word: "intuitive"}

Enter fullscreen mode Exit fullscreen mode

Only unique words are accepted so that we can implement words as the key. I can simply implement it as Object:

MainData = {}

class Word {
    constructor(tag, category, definition) {
        this.tag        = tag
        this.category   = category
        this.definition = definition
    }
}

const saveWord = (word, tag, category, definition) => {
    if (MainData[word] == null) {
        MainData[word] = new Word(tag, category, definition)
    } else {
        alert('This word already exists in the list.')
    }
}
Enter fullscreen mode Exit fullscreen mode

With this implementation, main data will look like this:

// Result of console.log(MainData)
arbitrary: { category: "Book1", meanings: "based on random choice or personal whim, rather than any reason or system.", tag: ["adj"]};
interpretation: { category: "Machine Learning", meanings: "the action of explaining the meaning of something", tag:["noun"]};
intuitive: { category: "Book2", meanings: "using or based on what one feels to be true even without conscious reasoning; instinctive", tag: ["adj"]};
precision: { category: "Machine Learning", meanings: "the quality, condition, or fact of being exact and acurate", tag: ["noun"]};

Enter fullscreen mode Exit fullscreen mode

And Deleting/Editing each object should take only O(1).

Conclusion

I've looked through several data structures until now, but Hash Table seems the most sensible for the main data so far. However, I need to keep reminding these words to myself:

Best Isn't Always Best. We need to be pragmatic about choosing appropriate algorithms -- the fastest one is not always the best for the job. (From The Pragmatic Programmer)

There are so many more data structures out there to learn, and also there's more to know about JavaScript Object and Map. Always think there's room to improve, so we won't lose the chance to make our crafts better.

Reference

JavaScript Data Structures and Algorithms Masterclass - Udemy
JavaScript Hashmap Equivalent - StackOverflow
5 WAYS TO USE A JAVASCRIPT HASHMAP - Sunfish Empire LLC
Objects and Hash Tables in Javascript - Medium
Hash table - Wikipedia
Are JS objects hash tables? - Quora
Learn to Code with JavaScript Hashes - Codelikethis.
The Pragmatic Programmer - goodreads.com

Top comments (5)

Collapse
 
okbrown profile image
Orlando Brown

I've always found that kind of implementation overkill. Until required.

Would hurt to create an obj={} assign values obj.key=val and return obj[key]?

Or obj = new Map(); set/get et al?

Collapse
 
maikomiyazaki profile image
Maiko Miyazaki

Thanks for your comment!

Yes, we can assign key-value pairs obj.key=val, and we get value back when return obj[key]. Using Map is also sensible too. ;)

We just need to be aware that when assigning keys with dot notation, and if we are passing the key through variable, the variable name will be actually assigned as the key(variable won't be recognized).

I'm going to update the article to include this thought! Thank you for your ideas! :)

Collapse
 
janbe30 profile image
Janeth Betancourt

This was a great post on hash tables! Very easy to understand :)

Collapse
 
janbe30 profile image
Janeth Betancourt

Here's a great article on Objects and Maps in ES6: medium.com/front-end-weekly/es6-ma...

Collapse
 
maikomiyazaki profile image
Maiko Miyazaki

Thanks, Janeth! That's a brilliant article, I appreciate that you mentioned it!