Algocademy Logo

Course Outline

Hash Maps in JavaScript


Hash Tables, better known as Hash Maps, are just collections of key-value pairs. In other words, they are pieces of data (values) mapped to unique identifiers called properties (keys).

Hash Maps were designed to give us a way of, given a key, associating a value with it for very quick lookups.

In JavaScript, an Object is implemented as a Hash Map behind the scenes. This is why adding and lookup of an Object's properties is so fast.

If you've worked with Objects in the past, you were working with Hash Maps without knowing it.

Creation:

You create an empty Hash Map just by creating an empty Object, like this:

let hashMap = {};

Creating an empty Hash Map takes O(1) time.

Initialization:

You can also add some key-value pairs in your Hash Map at creation:

let person = {
	'name': 'Andy',
	'age': 30,
	'hair color': 'brown'
};

Accessing values:

A value is retrieved from a Hash Map by specifying its corresponding key in square brackets ([]):

let person = {
	'name': 'Andy',
	'age': 30,
	'hair color': 'brown'
};

// Accessing values:
console.log(person['name']); // "Andy"
console.log(person['age']); // 30

// Accessing non-existing key:
console.log(person['job']); // undefined

As you can see, if you refer to a key that is not in the Hash Map, JavaScript returns undefined.

Accessing a value from a Hash Map takes O(1) time.

Adding an entry:

Adding an entry to an existing Hash Map is simply a matter of assigning a new key and value, via the assignment operator:

let person = {
	'name': 'Andy',
	'age': 30,
	'hair color': 'brown'
};

// Adding new entries:
person['job'] = 'Teacher';

let str = 'hobby';
person[str] = 'Fishing';

console.log(person);
/* The new Hash Map:
{
	'name': 'Andy',
	'age': 30,
	'hair color': 'brown',
	'job': 'Teacher',
	'hobby': 'Fishing'
	
} */

Adding a new entry to a Hash Map takes O(1) time.

Updating an entry:

If you want to update an entry, you can just assign a new value to an existing key:

let person = {
	'name': 'Andy',
	'age': 30,
	'hair color': 'brown'
};

// Updating entries:
person['name'] = 'Andrew';
person['age'] = 29;

console.log(person);
/* The new Hash Map:
{
	'name': 'Andrew',
	'age': 29,
	'hair color': 'brown'
} */

Updating an entry to a Hash Map takes O(1) time.

Deleting entries:

The delete operator allows you to remove a key from a Hash Map:

let person = {
	'name': 'Andy',
	'age': 30,
	'hair color': 'brown',
	'hobby': 'Fishing'
};

// Deleting entries:
delete person['name'];

let key = 'age';
delete person[key];

// Deleting a non-existent entry:
delete person['job']; // does nothing

console.log(person);
/* The new Hash Map:
{
	'hair color': 'brown',
	'hobby': 'Fishing'
} */

The Hash Map first checks if that key exists and if not, it does nothing and also doesn't raise an error, so it's safe to delete non-existing keys.

Deleting an entry from a Hash Map takes O(1) time.

Checking if a key exists:

You can check if a key exists in a Hash Map using the in operator:

let person = {
	'name': 'Andy',
	'age': 30,
	'hair color': 'brown',
	'hobby': 'Fishing'
};

let key = 'age';
console.log(key in person); // prints "true"

console.log('job' in person); // prints "false"

Checking if a key exists in a Hash Map takes O(1) time.

Iterating over the map keys:

If we want to iterate over keys of the dictionary, we can use the for loop along with the in operator:

let person = {
	'name': 'Andy',
	'age': 30,
	'hair color': 'brown',
	'hobby': 'Fishing'
};

for (let key in person) {
    console.log(key + " is " + person[key]);
}

// This will print the following:
// name is Andy
// age is 30
// hair color is brown
// hobby is Fishing

Iterating over a dictionary takes O(n) time.

Iterating over the dictionary values:

If we want to iterate over values of the map, we can use the for loop along with the of operator and the Object.values(map) function:

let person = {
	'name': 'Andy',
	'age': 30,
	'hair color': 'brown',
	'hobby': 'Fishing'
};

for (let val of Object.values(person) {
    console.log(val);
}

// This will print the following:
// Andy
// 30
// brown
// Fishing

Iterating over a dictionary takes O(n) time.

Iterating using both the key and the value for simplicity:

If we want to iterate over both keys and values of the map, we can use the for loop along with the of operator and the Object.entries(map) method:

let person = {
	'name': 'Andy',
	'age': 30,
	'hair color': 'brown',
	'hobby': 'Fishing'
}

for (let [key, val] of Object.entries(person)) {
    console.log(key + ' is ' +  val);
}

// This will print the following:
// name is Andy
// age is 30
// hair color is brown
// hobby is Fishing

Notice the order is not the same as initiated. Dictionary keeps the data in random order

Iterating over a dictionary takes O(n) time.

Assignment
Follow the Coding Tutorial and let's play with some Hash Maps.

Hint
Look at the examples above if you get stuck.

Introduction

In this lesson, we will explore the concept of Hash Maps in JavaScript. Hash Maps, also known as Hash Tables, are a fundamental data structure in programming. They allow us to store and retrieve data efficiently using key-value pairs. Understanding Hash Maps is crucial for solving various programming problems, especially those involving quick lookups and data organization.

Hash Maps are widely used in scenarios where fast data retrieval is essential, such as caching, database indexing, and implementing associative arrays. By mastering Hash Maps, you can significantly improve the performance of your applications.

Understanding the Basics

Before diving into the details, let's understand the fundamental concepts of Hash Maps:

  • Key-Value Pairs: Hash Maps store data as key-value pairs, where each key is unique, and it maps to a specific value.
  • Hash Function: A hash function is used to compute an index (hash code) for each key, which determines where the key-value pair is stored in the Hash Map.
  • Collision Handling: When two keys hash to the same index, a collision occurs. Hash Maps use techniques like chaining or open addressing to handle collisions.

Understanding these basics is essential before moving on to more complex aspects of Hash Maps.

Main Concepts

Let's delve into the key concepts and techniques involved in Hash Maps:

  • Creation: Creating an empty Hash Map is straightforward. In JavaScript, you can create an empty object to represent a Hash Map.
    • let hashMap = {};
  • Initialization: You can initialize a Hash Map with key-value pairs during creation.
    • let person = {
  'name': 'Andy',
  'age': 30,
  'hair color': 'brown'
};
  • Accessing Values: Retrieve values from a Hash Map using their corresponding keys.
    • let person = {
  'name': 'Andy',
  'age': 30,
  'hair color': 'brown'
};

console.log(person['name']); // "Andy"
console.log(person['age']); // 30
  • Adding Entries: Add new key-value pairs to an existing Hash Map.
    • let person = {
  'name': 'Andy',
  'age': 30,
  'hair color': 'brown'
};

person['job'] = 'Teacher';
person['hobby'] = 'Fishing';
  • Updating Entries: Update the value of an existing key in the Hash Map.
    • let person = {
  'name': 'Andy',
  'age': 30,
  'hair color': 'brown'
};

person['name'] = 'Andrew';
person['age'] = 29;
  • Deleting Entries: Remove a key-value pair from the Hash Map using the delete operator.
    • let person = {
  'name': 'Andy',
  'age': 30,
  'hair color': 'brown',
  'hobby': 'Fishing'
};

delete person['name'];
delete person['age'];
  • Checking Key Existence: Check if a key exists in the Hash Map using the in operator.
    • let person = {
  'name': 'Andy',
  'age': 30,
  'hair color': 'brown',
  'hobby': 'Fishing'
};

console.log('age' in person); // true
console.log('job' in person); // false
  • Iterating Over Keys: Use a for...in loop to iterate over the keys of the Hash Map.
    • let person = {
  'name': 'Andy',
  'age': 30,
  'hair color': 'brown',
  'hobby': 'Fishing'
};

for (let key in person) {
  console.log(key + " is " + person[key]);
}
  • Iterating Over Values: Use a for...of loop with Object.values() to iterate over the values of the Hash Map.
    • let person = {
  'name': 'Andy',
  'age': 30,
  'hair color': 'brown',
  'hobby': 'Fishing'
};

for (let val of Object.values(person)) {
  console.log(val);
}
  • Iterating Over Entries: Use a for...of loop with Object.entries() to iterate over both keys and values of the Hash Map.
    • let person = {
  'name': 'Andy',
  'age': 30,
  'hair color': 'brown',
  'hobby': 'Fishing'
};

for (let [key, val] of Object.entries(person)) {
  console.log(key + ' is ' + val);
}

Examples and Use Cases

Let's explore some examples and real-world use cases of Hash Maps:

  • Example 1: Counting Word Frequency
    • let text = "hello world hello";
let wordCount = {};

let words = text.split(" ");
for (let word of words) {
  if (word in wordCount) {
    wordCount[word]++;
  } else {
    wordCount[word] = 1;
  }
}

console.log(wordCount); // { hello: 2, world: 1 }
  • Example 2: Storing User Preferences
    • let userPreferences = {
  theme: 'dark',
  language: 'en',
  notifications: true
};

console.log(userPreferences['theme']); // "dark"
  • Example 3: Implementing a Simple Cache
    • let cache = {};

function getData(key) {
  if (key in cache) {
    return cache[key];
  } else {
    let data = fetchDataFromServer(key); // Assume this function fetches data from a server
    cache[key] = data;
    return data;
  }
}

Common Pitfalls and Best Practices

When working with Hash Maps, it's important to be aware of common pitfalls and follow best practices:

  • Common Pitfalls:
    • Using non-string keys: In JavaScript, object keys are always strings. Be cautious when using other data types as keys.
    • Overwriting existing keys: Ensure that you are not unintentionally overwriting existing keys when adding new entries.
  • Best Practices:
    • Use meaningful keys: Choose descriptive and meaningful keys to improve code readability.
    • Check for key existence: Always check if a key exists before accessing or modifying its value.
    • Keep Hash Maps small: Avoid storing large amounts of data in a single Hash Map to maintain performance.

Advanced Techniques

Once you are comfortable with the basics, you can explore advanced techniques related to Hash Maps:

  • Custom Hash Functions: Implement custom hash functions to optimize the distribution of keys and reduce collisions.
  • WeakMaps: Use WeakMap for memory-efficient key-value storage where keys are objects and can be garbage-collected.
  • Combining Data Structures: Combine Hash Maps with other data structures like arrays or sets to solve complex problems efficiently.

Code Implementation

Here are some well-commented code snippets demonstrating the correct use of Hash Maps:

// Creating an empty Hash Map
let hashMap = {};

// Initializing a Hash Map with key-value pairs
let person = {
  'name': '