Using Hashmaps in JavaScript: Mapping Keys to Values in Data Structures

What are Hashmaps?

Hashmaps are a data structure that store key-value pairs, where each key is unique and maps to a value. The key is used to index the value, allowing for fast retrieval of the associated value. Hashmaps use a hash function to compute an index for storing and retrieving values. The hash function takes the key as input and generates a unique hash code, which is then used to determine the index where the value will be stored in the array or bucket.

Hashmaps vs JavaScript Objects

JavaScript objects can also store key-value pairs, similar to hashmaps. However, hashmaps offer advantages over objects:

1. Key Types: Hashmaps allow any data type to be used as a key, including objects, arrays, and functions. JavaScript objects are limited to using only strings and symbols as keys.

   const hashmap = new Map();
   hashmap.set({ name: 'John' }, 25);
   hashmap.set([1, 2, 3], 'array');
   
   const obj = {};
   obj[{ name: 'John' }] = 25; // Invalid: Objects cannot be used as keys in objects

2. Order Maintenance: Hashmaps maintain the insertion order of elements, meaning that the order in which key-value pairs are added to the hashmap is preserved. JavaScript objects do not guarantee any order of their properties.

   const hashmap = new Map();
   hashmap.set('a', 1);
   hashmap.set('b', 2);
   hashmap.set('c', 3);
   console.log(Array.from(hashmap.keys())); // Output: ['a', 'b', 'c']
   
   const obj = { a: 1, b: 2, c: 3 };
   console.log(Object.keys(obj)); // Output: ['a', 'b', 'c'] (Not guaranteed)

3. Size Tracking: Hashmaps provide methods like size() to get the number of elements stored in the hashmap. With JavaScript objects, you would need to manually keep track of the number of properties or use Object.keys(obj).length to determine the size.

   const hashmap = new Map();
   hashmap.set('a', 1);
   hashmap.set('b', 2);
   console.log(hashmap.size); // Output: 2
   
   const obj = { a: 1, b: 2 };
   console.log(Object.keys(obj).length); // Output: 2

Time Complexity of Hashmap Operations

One of the main advantages of hashmaps is their time complexity for basic operations. Hashmaps provide constant time complexity, denoted as O(1), for the following operations:

1. Insertion: Adding a new key-value pair to the hashmap is an O(1) operation. The hash function is used to compute the index, and the key-value pair is stored at that index in the array or bucket.

2. Deletion: Removing a key-value pair from the hashmap is also an O(1) operation. The hash function is used to locate the index where the key-value pair is stored, and then it is removed from that index.

3. Lookup: Retrieving the value associated with a given key is an O(1) operation. The hash function is used to compute the index based on the key, and the value can be accessed at that index.

const cache = new Map();

function fetchData(key) {
  if (cache.has(key)) {
    return cache.get(key); // Retrieve data from cache (O(1) lookup)
  } else {
    const data = fetchFromAPI(key); // Fetch data from API
    cache.set(key, data); // Store data in cache (O(1) insertion)
    return data;
  }
}

Creating a Hashmap

To create a new hashmap, use the new Map() constructor. This creates an empty hashmap to store key-value pairs.

const myHashmap = new Map();

For example, to create a hashmap to store student data:

const studentMap = new Map();

Adding Key-Value Pairs

To add a new key-value pair to the hashmap, use the set() method. It takes two arguments: the key and the value.

myHashmap.set('name', 'John');
myHashmap.set('age', 25);

In the above example, we add two key-value pairs to the myHashmap: 'name' maps to 'John' and 'age' maps to 25.

Let's add some student data to our studentMap:

studentMap.set('1', { name: 'John', age: 20, major: 'Computer Science' });
studentMap.set('2', { name: 'Alice', age: 22, major: 'Mathematics' });
studentMap.set('3', { name: 'Bob', age: 21, major: 'Physics' });

Getting Values

To get the value for a given key, use the get() method. It takes the key as an argument and returns the value.

const name = myHashmap.get('name');
console.log(name); // Output: 'John'

In this example, we get the value for the key 'name' from the myHashmap, which is 'John'.

To get the data of a specific student from studentMap:

const student = studentMap.get('2');
console.log(student); // Output: { name: 'Alice', age: 22, major: 'Mathematics' }

Checking for Key Existence

To check if a key exists in the hashmap, use the has() method. It takes the key as an argument and returns a boolean value.

const hasAge = myHashmap.has('age');
console.log(hasAge); // Output: true

Here, we check if the key 'age' exists in the myHashmap using the has() method, which returns true.

Checking if a student with ID '4' exists in studentMap:

const hasStudent = studentMap.has('4');
console.log(hasStudent); // Output: false

Removing Key-Value Pairs

To remove a key-value pair from the hashmap, use the delete() method. It takes the key as an argument and removes the key-value pair from the hashmap.

myHashmap.delete('age');
console.log(myHashmap.has('age')); // Output: false

In this example, we remove the key-value pair with the key 'age' from the myHashmap using the delete() method. After removal, has('age') returns false.

Removing a student from studentMap:

studentMap.delete('1');
console.log(studentMap.has('1')); // Output: false

Getting the Hashmap Size

To get the number of key-value pairs in the hashmap, use the size property. It returns the size of the hashmap.

console.log(myHashmap.size); // Output: 1

Here, we access the size property of the myHashmap, which returns 1, indicating that there is one key-value pair in the hashmap.

Getting the number of students in studentMap:

console.log(studentMap.size); // Output: 2

Hashmap Operations Summary

These are the basic operations you can do on a hashmap using JavaScript's Map object. The Map object provides a way to work with key-value pairs and offers methods to manipulate and access the data in the hashmap.

The Map object keeps the order of key-value pairs, which means that when you iterate over the hashmap using methods like forEach() or the for...of loop, the key-value pairs will be accessed in the order they were added.

The forEach() Method

The forEach() method is built into the Map object. It lets you iterate over each key-value pair in the hashmap. It uses a callback function that runs for each pair.

The callback function gets three parameters:

1. value: The value of the current pair.
2. key: The key of the current pair.
3. map: The hashmap that forEach() was called on.

const shoppingCart = new Map();
shoppingCart.set('shirt', 25);
shoppingCart.set('pants', 50);
shoppingCart.set('shoes', 75);

let totalPrice = 0;

shoppingCart.forEach((price) => {
  totalPrice += price;
});

console.log(`Total Price: $${totalPrice}`);

Total Price: $150

The for...of Loop

You can also use a for...of loop to iterate over a hashmap. The for...of loop works with iterable objects like arrays, strings, and maps.

When you use for...of with a hashmap, each loop returns an array with the [key, value] pair. !!!

Visualizing Hashmap Iteration

Here's a diagram showing how iterating over a hashmap works:

The diagram shows the hashmap and iterating over each key-value pair. For each pair, we process it based on what we need to do, like calculations, comparisons, or other operations.

Both forEach() and for...of let you iterate over a hashmap's key-value pairs in JavaScript. Which one you use depends on your specific needs. forEach() is good when you want to do something for each pair, while for...of is useful when you need both the keys and values in each loop.

Keep in mind that the order of iteration in a hashmap is based on the order the pairs were added. JavaScript's Map object keeps this order.

Iterating over hashmaps is common when working with key-value pairs, and JavaScript has these methods to make it easier and faster. For more information on Map objects and iteration, check out the MDN Web Docs.

What are Collisions?

In a hashmap, collisions happen when two or more keys hash to the same index. This means that multiple key-value pairs need to be stored at the same position in the array or bucket. If not handled well, collisions can lead to data overwriting or slow retrieval of values.

Here's an example of a collision in a hashmap:

In this example, both the keys 'John' and 'Alice' hash to the same index (Index 0), causing a collision.

If collisions are not fixed, these issues can happen:

1. Data Overwriting: If a new key-value pair hashes to the same index as an existing pair, the existing pair might be overwritten, causing data loss.

2. Slow Retrieval: When collisions occur, finding values becomes slower as the hashmap needs to do more steps to find the right value among the collided pairs.

To fix these issues, hashmaps use collision handling techniques.

Ways to Handle Collisions

There are two main ways to handle collisions in hashmaps:

1. Separate Chaining

• Each index of the hashmap's array or bucket stores a linked list of key-value pairs.
• When a collision occurs, the new key-value pair is added to the linked list at that index.
• Finding a value means going through the linked list at the hashed index to find the wanted key-value pair.

2. Open Addressing

• Open addressing does not use linked lists to handle collisions. Instead, it looks for the next free index in the array when a collision occurs.
• There are different ways to find the next index, such as linear probing, quadratic probing, and double hashing.
• When a collision happens, the hashmap uses the probing way to find the next empty slot in the array to store the key-value pair.

Best Practices for Using Hashmaps

1. Choose a good hash function that reduces collisions and spreads keys evenly.
2. Think about the expected number of elements and wanted performance when choosing the starting size of the hashmap.
3. Be aware of how collisions can affect the speed of hashmap operations, especially with many collisions.
4. Use separate chaining or open addressing based on what your application needs, considering things like memory usage and retrieval speed.