Skip to content

My try at implementing my own hashmap in Javascript. Feel free to take a look!

Notifications You must be signed in to change notification settings

GitWorkingTime/js-hashmap-implementation

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

5 Commits
 
 
 
 
 
 

Repository files navigation

Implements a hashmap using linked-lists to handle hash collisions in Javascript.

Explaination of a Hash map:

A hash map is a data structure similar to an array but functions differently. It's a data structure that deals with key-value pairs, and in javascript this can be an object.

Before inserting an entry into a hash map, it must be hashed, essentially given a signature that directs the key-value pair to a specific index in an array. There's lots of hashing algorithms out there, but essentially, it takes a key and converts into a number value known as a digest. We then take this hash code and modulo it by the array capacity which gives us the index. We can think of each element in the hashmap array as a bucket, just a storage variable. The hash code indicates its position in the hash map; it does NOT mean the same as the entry's key

Sometimes, we may get the same hash code for two different keys so this is known as a hash collision. This is where either a linked list or a binary search tree can come in.

Complementary Information (i.e Linked Lists):

A linked list is another data structure that is similar to an array but instead of indexing, we point to the next element.

┌─────┐     ┌─────┐     ┌───┐
│ ELEMENT │ -> │ ELEMENT │ -> │ NULL |
└─────┘     └─────┘     └───┘

Each element belong to a class called a 'Node' with two member variables, a 'value' and a 'next'. The 'next' member variable points to the next node in line of the linked list. How this is done depends on the programming language.
For C++, we could use pointers but for Javascript, it is a key-value pair in which the value is just the next object in line.

Why do we need to know this? This becomes important when we encounter hash collisions in a hashmap. We still put the new entry into the same bucket but this bucket now contains a linked list instead of just the entry itself.

About

My try at implementing my own hashmap in Javascript. Feel free to take a look!

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published