Hi, and welcome! Today, we'll explore Maps, a data structure that organizes data as key-value pairs, much like a treasure box with unique labels for each compartment. Imagine dozens of toys in a box. If each toy had a unique label (the key), you could directly select a toy (the value) using the label. No rummaging required — that's the power of Maps! Today, we'll understand Maps and learn how to implement them in JavaScript.

JavaScript implements Maps through the Map class. They hold data in key-value pairs. Let's create a Map, functioning as a catalog for a library:

JavaScript
Copy to clipboard
1const libraryCatalog = new Map([
2    ["book1", "A Tale of Two Cities"],
3    ["book2", "To Kill a Mockingbird"],
4    ["book3", "1984"]
5]);

In this Map, book1, book2, and book3 are keys, while the book titles serve as their respective values. It's important to remember that the keys should be of a type that supports hashing and equality comparison. Examples include String, Number, and Boolean. The values can be of any type.

You can retrieve a book's title using its key straightforwardly with the get() method:

JavaScript
Copy to clipboard
1const title1 = libraryCatalog.get("book1");
2console.log(title1); // Output: "A Tale of Two Cities"

But what happens if you try to access a key that isn't present in the Map? This would return undefined.

JavaScript
Copy to clipboard
1const titleNonexistent = libraryCatalog.get("book100");
2if (titleNonexistent !== undefined) {
3    console.log(titleNonexistent); 
4} else {
5    console.log("Key not found");
6}

As demonstrated, one method to verify the existence of a specific key in the Map is shown above. While this method is valid, it is usually not the most optimal approach. Alternatively, JavaScript provides the built-in has() function that returns a boolean value, offering a more standardized and concise way to check for the presence of a key:

JavaScript
Copy to clipboard
1const mapContains = libraryCatalog.has("book100");
2
3if(mapContains) {
4    console.log("Key found");
5} else {
6    console.log("Key not found");
7}

Whether you're adding a new book to the catalog or updating an existing book's title, you'll use the set() method. If the specified key exists in the Map, the assigned value replaces the existing one:

JavaScript
Copy to clipboard
1libraryCatalog.set("book1", "The Tell-Tale Heart");
2console.log("Updated book1: " + libraryCatalog.get("book1")); // Output: "Updated book1: The Tell-Tale Heart"

If the key doesn't exist in the Map yet, the operation creates a new key-value pair:

JavaScript
Copy to clipboard
1libraryCatalog.set("book4", "Pride and Prejudice");
2console.log("Added book4: " + libraryCatalog.get("book4")); // Output: "Added book4: Pride and Prejudice"

If you want to remove book1 from the Map, you can do so using libraryCatalog.delete("book1"). The delete() method returns true if the element existed and was removed, and it returns false if it did not exist:

JavaScript
Copy to clipboard
1console.log(libraryCatalog.delete("book1")); // Returns true
2console.log(libraryCatalog.delete("book1")); // Returns false as the element is already removed
3console.log(libraryCatalog.has("book1")); // Returns false

To iterate through your Map and access each entry's key and value, you can use the entries() method. This method returns an iterator object that yields key-value pairs for every element in the Map. By using a for...of loop, you can directly access both the key and value for each entry sequentially. With each iteration, you get an array-like structure containing the key and value. This approach makes it efficient to examine or manipulate all entries in the Map:

JavaScript
Copy to clipboard
1for (let [key, value] of libraryCatalog.entries()) {
2    console.log(key + " : " + value);
3}

In the loop for (let [key, value] of libraryCatalog.entries()), the [key, value] syntax destructures each array returned by the iterator into separate variables key and value. This destructuring makes it easy to access both the key and value of each entry directly within the loop body, eliminating the need for additional code to extract these elements. When run, this code may output:

Plain text
Copy to clipboard
1book1 : A Tale of Two Cities
2book2 : To Kill a Mockingbird
3book3 : 1984

You can also access just the keys or values of the Map:

JavaScript
Copy to clipboard
1for (let key of libraryCatalog.keys()) {
2    console.log(key);
3}
4// Output: "book1", "book2", "book3"
5
6for (let value of libraryCatalog.values()) {
7    console.log(value);
8}
9// Output: "A Tale of Two Cities", "To Kill a Mockingbird", "1984"

As mentioned, Maps can be visualized as arrays where any type of key can index values. Behind the scenes, however, a Map is still an array with numerical-based indexing facilitated by hash functions. A hash function converts a key into a unique numeric value (hashcode) that maps to an index in the underlying array, allowing for efficient direct access to values without a linear search.

Here's how it works: a hash function takes a key and produces a hashcode, a fixed-size numerical value representing the key. For example, hash("book1") might yield 123, placing it at index 123 in the underlying array. The implementation of the hash function is crucial. If the hash function is too simplistic or poorly designed, it can lead to frequent collisions, where multiple keys generate the same hashcode. For instance, a trivial hash function that always returns the same value would place all keys at the same index, we would have to search through the entire array, effectively turning the Map into a list and degrading performance to O(n). To avoid this, a good hash function should spread keys uniformly across the array, making use of mathematical techniques that distribute hashcodes as evenly as possible. This reduces the likelihood of collisions and ensures efficient access times for operations on the Map.

By reducing collisions, hash functions optimize data retrieval and storage. Even in cases where collisions occur, JavaScript's Map handles them internally to maintain efficient performance, ensuring quick access to values based on their keys.

Maps are popular because they save time! Thanks to hash functions, operations like adding, updating, and locating elements take average constant time, O(1), which means that the time to do these operations doesn't grow, even when the library size grows. For example, it is as fast to insert a new key at key count 4 as it is at key count 9000. This efficiency is what makes Maps an excellent choice for applications requiring rapid access to data.

In the average-case scenario, the hash function distributes keys uniformly across the Map. Thanks to this uniform distribution, the operations of adding, updating, or retrieving keys have a time complexity of O(1) because they involve a simple arithmetic operation and direct addressing. Under such conditions, Maps perform exceptionally well in diverse scenarios.

In the worst-case scenario, a poor hash function could cause too many collisions, making the Map resemble a linked list. When this happens, operations degrade to O(n) time complexity because they involve traversing a list of n elements. However, JavaScript's Map handles collisions internally to mitigate performance degradation. This built-in handling ensures that even in less ideal situations, performance remains reasonable.

Well done! You've mastered Maps, understood JavaScript's implementation of Maps through Map, learned their operations, and grasped the concept of time complexity. Now, you're ready to apply these concepts to solve real-world problems efficiently. Dive into the upcoming practice exercises to reinforce your learning. Happy coding!