Implementing Sets and Maps in JavaScript: A Comprehensive Guide

5.4.2 Implementing Sets and Maps

In the world of data structures, sets and maps play a crucial role due to their unique properties and efficient operations. This section will delve into the implementation of sets and maps using hash tables in JavaScript, explore their operations, and discuss the advantages of using ES6 Set and Map classes for more robust implementations.

Understanding Sets and Maps

Before diving into the implementation, it’s essential to understand what sets and maps are:

• Sets are collections of unique elements. They do not allow duplicate entries, making them ideal for scenarios where uniqueness is a priority.
• Maps are collections of key-value pairs. They allow efficient retrieval, addition, and deletion of elements based on keys.

Implementing a Set in JavaScript

Let’s start by implementing a basic set using a hash table. A hash table is an efficient data structure that allows for fast data retrieval. Here’s how you can create a MySet class:

class MySet {
  constructor() {
    this.collection = {};
  }
  
  has(element) {
    return this.collection.hasOwnProperty(element);
  }
  
  add(element) {
    if (!this.has(element)) {
      this.collection[element] = true;
      return true;
    }
    return false;
  }
  
  remove(element) {
    if (this.has(element)) {
      delete this.collection[element];
      return true;
    }
    return false;
  }
  
  values() {
    return Object.keys(this.collection);
  }
  
  size() {
    return this.values().length;
  }
  
  union(otherSet) {
    let unionSet = new MySet();
    this.values().forEach(e => unionSet.add(e));
    otherSet.values().forEach(e => unionSet.add(e));
    return unionSet;
  }
  
  intersection(otherSet) {
    let intersectionSet = new MySet();
    this.values().forEach(e => {
      if (otherSet.has(e)) {
        intersectionSet.add(e);
      }
    });
    return intersectionSet;
  }
  
  difference(otherSet) {
    let differenceSet = new MySet();
    this.values().forEach(e => {
      if (!otherSet.has(e)) {
        differenceSet.add(e);
      }
    });
    return differenceSet;
  }
  
  subset(otherSet) {
    return this.values().every(value => otherSet.has(value));
  }
}

Key Operations Explained

• has(element): Checks if the element exists in the set.
• add(element): Adds an element to the set if it doesn’t already exist.
• remove(element): Removes an element from the set if it exists.
• values(): Returns an array of all elements in the set.
• size(): Returns the number of elements in the set.
• union(otherSet): Returns a new set containing all elements from both sets.
• intersection(otherSet): Returns a new set containing only elements present in both sets.
• difference(otherSet): Returns a new set containing elements present in the current set but not in the other set.
• subset(otherSet): Checks if the current set is a subset of another set.

Practical Examples of Set Operations

Let’s look at some practical examples to understand these operations better:

let setA = new MySet();
setA.add(1);
setA.add(2);
setA.add(3);

let setB = new MySet();
setB.add(2);
setB.add(3);
setB.add(4);

console.log(setA.union(setB).values()); // Output: [ '1', '2', '3', '4' ]
console.log(setA.intersection(setB).values()); // Output: [ '2', '3' ]
console.log(setA.difference(setB).values()); // Output: [ '1' ]
console.log(setA.subset(setB)); // Output: false

Implementing a Map in JavaScript

Maps are slightly more complex due to their key-value nature. Here’s a simple implementation of a map using a hash table:

class MyMap {
  constructor() {
    this.collection = {};
  }
  
  set(key, value) {
    this.collection[key] = value;
  }
  
  get(key) {
    return this.collection.hasOwnProperty(key) ? this.collection[key] : undefined;
  }
  
  has(key) {
    return this.collection.hasOwnProperty(key);
  }
  
  delete(key) {
    if (this.has(key)) {
      delete this.collection[key];
      return true;
    }
    return false;
  }
  
  keys() {
    return Object.keys(this.collection);
  }
  
  values() {
    return Object.values(this.collection);
  }
  
  size() {
    return this.keys().length;
  }
  
  clear() {
    this.collection = {};
  }
}

Key Operations Explained

• set(key, value): Adds a key-value pair to the map.
• get(key): Retrieves the value associated with the key.
• has(key): Checks if a key exists in the map.
• delete(key): Removes a key-value pair from the map.
• keys(): Returns an array of all keys in the map.
• values(): Returns an array of all values in the map.
• size(): Returns the number of key-value pairs in the map.
• clear(): Removes all key-value pairs from the map.

Using ES6 Set and Map Classes

JavaScript’s ES6 introduced built-in Set and Map classes, which provide more robust implementations with additional features:

ES6 Set

let es6Set = new Set();
es6Set.add(1);
es6Set.add(2);
es6Set.add(3);

console.log(es6Set.has(2)); // Output: true
console.log([...es6Set]); // Output: [ 1, 2, 3 ]

ES6 Map

let es6Map = new Map();
es6Map.set('key1', 'value1');
es6Map.set('key2', 'value2');

console.log(es6Map.get('key1')); // Output: 'value1'
console.log([...es6Map.keys()]); // Output: [ 'key1', 'key2' ]

Advantages of Using ES6 Set and Map

• Built-in Methods: ES6 Set and Map come with a variety of built-in methods that simplify operations.
• Iterators: They provide iterators for keys, values, and entries, making traversal easy.
• Performance: Optimized for performance, especially for large datasets.
• Order: Maintains the order of elements (insertion order for Map).

Best Practices and Common Pitfalls

• Avoid Duplicates in Sets: Sets automatically handle duplicates, but ensure your logic doesn’t rely on duplicate entries.
• Use Appropriate Data Structures: Choose Set or Map based on your needs—use Set for unique elements and Map for key-value pairs.
• Understand Key Types: In Map, keys can be of any type, including objects, which is not possible with plain objects.
• Performance Considerations: For large datasets, prefer ES6 Set and Map for better performance and memory management.

Experimenting with Map Implementations

To fully grasp the power of maps, experiment with various methods like forEach, clear, and checking for key existence:

es6Map.forEach((value, key) => {
  console.log(`${key}: ${value}`);
});

es6Map.clear();
console.log(es6Map.size); // Output: 0

Conclusion

Implementing sets and maps in JavaScript provides a solid foundation for understanding more complex data structures and algorithms. By leveraging hash tables, you can efficiently manage collections of unique elements and key-value pairs. The introduction of ES6 Set and Map classes further enhances your ability to work with these structures in a robust and performant manner.

Quiz Time!