EN/CH Mode

BRUCE_FE JS Interview Notes - Map and Set Data Structures

In-depth analysis of Map and Set data structures in JavaScript, comparing Map with Object, exploring WeakMap and WeakSet use cases, and common interview questions.

EN/CH Mode

Lazy to read articles? Then watch videos!

What are Map and Set?

Map and Set are two new data structures introduced in ES6:

•
Map is a collection of key-value pairs, similar to objects, but allows any type of value as a key
•
Set is a collection of values where each value is unique

Basic Usage of Map

// Create Map
const userMap = new Map();

// Set key-value pairs
userMap.set('name', 'Bruce');
userMap.set(123, 'ID');

// Get value
console.log(userMap.get('name')); // Bruce

// Check if key exists
console.log(userMap.has('name')); // true

// Delete key-value pair
userMap.delete('name');

Basic Usage of Set

// Create Set
const uniqueNumbers = new Set();

// Add values
uniqueNumbers.add(1);
uniqueNumbers.add(2);
uniqueNumbers.add(1); // Duplicate value won't be added

// Check if value exists
console.log(uniqueNumbers.has(1)); // true

// Delete value
uniqueNumbers.delete(1);

WeakMap and WeakSet

WeakMap and WeakSet are their 'weak reference' versions that automatically release memory when objects are no longer in use:

•
Only objects are allowed as keys/values
•
Don't prevent garbage collector from collecting their keys/values
•
No size property and listing methods

Game Application Example

// Using WeakMap to store level cache data
const gameCache = new WeakMap();

// Create level (each level is a DOM element)
function createLevel(levelNum) {
  const levelDiv = document.createElement('div');
  levelDiv.className = 'game-level';
  levelDiv.innerHTML = `<h2>Level ${levelNum}</h2>`;
  
  // Store level-related cache data
  gameCache.set(levelDiv, {
    score: 0,
    items: ['Gem', 'Coin', 'Weapon']
  });
  
  return levelDiv;
}

// Switch to next level
function goToNextLevel() {
  // Remove current level DOM element
  const oldLevel = document.querySelector('.game-level');
  oldLevel.remove();
  
  // Create new level
  const newLevel = createLevel(2);
  document.body.appendChild(newLevel);
  
  // Cache data for old level will be automatically collected
  // If using Map instead of WeakMap, even if level DOM is removed
  // cache data would still occupy memory, game would slow down or crash

Internal Principles of Map and Set: Hash Table Implementation

Both Map and Set are implemented using Hash Tables internally:

1. Hash Function Principle

•
Convert keys (or values) to numeric indices (hash codes)
•
Special hash algorithms for primitive types
•
For object types, generally based on memory address

2. Set.add() Duplicate Value Handling

•
Calculate hash code of the value
•
Check if there's already a value at that hash code position
•
Ignore if same, add if different

// Example of Set handling duplicate values
const set = new Set();

set.add('a');         // Store
set.add('a');         // Already exists, ignore
console.log(set.size); // 1

// Object comparison
const obj1 = {};
const obj2 = {};
set.add(obj1);        // Store
set.add(obj2);        // Different object, store
console.log(set.size); // 2

Differences between Map and Object

Feature	Map	Object
Key Type	Any value	Only string or Symbol
Key Order	Preserves insertion order	No order guarantee
Size	Direct access	Manual calculation
Performance	Better for frequent additions/deletions	May be faster for lookups

Value Comparison Logic in Set

Set uses the 'Same-value-zero' algorithm to compare value uniqueness:

•
A hybrid of Object.is() and ===
•
Treats NaN as equal to itself (like Object.is)
•
But treats +0 and -0 as equal (like ===)
•
Object comparison is based on reference

const set = new Set();

// NaN is considered equal in Set
set.add(NaN);
set.add(NaN); // Won't add
console.log(set.size); // 1

// +0 and -0 are considered equal in Set
set.add(+0);
set.add(-0); // Won't add
console.log(set.size); // Still 1

// Object comparison is based on reference
const obj1 = {id: 1};
const obj2 = {id: 1};
set.add(obj1);
set.add(obj2); // Will add, different references
console.log(set.size); // 2

set.add(obj1); // Won't add, same reference
console.log(set.size); // Still 2

🔥 Common Interview Questions

（1）How to use Set to remove duplicate elements from an array?

Answer:

// Basic usage
const array = [1, 2, 3, 3, 4, 4, 5];
const uniqueArray = [...new Set(array)];
console.log(uniqueArray); // [1, 2, 3, 4, 5]

// Object array deduplication
const users = [
  { id: 1, name: 'Bruce' },
  { id: 1, name: 'Bruce' },
  { id: 2, name: 'Tony' }
];

const uniqueUsers = Array.from(
  new Map(users.map(user => [user.id, user])).values()
);
console.log(uniqueUsers); // Only two objects

This leverages Set's property of not allowing duplicate elements, converting the array to a Set and back to an array, making it the most concise and efficient deduplication method.

（2）Main differences between Map and Object? When to choose Map?

Answer:The main differences between Map and Object are:

// 1. Map can use any type as key
const map = new Map();
const func = function() {};
map.set(func, 'Function as key');
console.log(map.get(func)); // 'Function as key'

// 2. Map preserves insertion order
map.set('first', 1);
map.set('second', 2);

for (let [key, value] of map) {
  console.log(key, value); // Outputs in insertion order
}

Scenarios suitable for using Map:

•
When non-string keys are needed
•
When frequent addition and deletion of properties is needed
•
When key-value pair order is important

（3）Differences between WeakMap and Map? When should we use WeakMap?

Answer:

// Using WeakMap to store DOM node related data
const nodeData = new WeakMap();

// Add data to DOM nodes, won't affect garbage collection
document.querySelectorAll('button').forEach(node => {
  nodeData.set(node, { clickCount: 0 });
});

// When nodes are removed, related data is automatically collected
document.body.innerHTML = '';
// No need to manually clean up nodeData

Scenarios for using WeakMap:

•
When associating additional data with DOM elements
•
When implementing private variables or state
•
When memory leaks need to be avoided

（4）Explain the principle of HashTable and how Map is implemented?

Answer:

// Visual explanation of HashTable
/*
  HashTable principle diagram:
  
  Key-value pairs: { "name": "Bruce", "age": 30, "city": "Taipei", "code": "TW" }
  
  Hash Function                Storage Buckets
  ┌─────────┐                 ┌───────────────────┐
  │ hash()  │──── 0 ─────────► [                 ]
  └─────────┘                 │                   │
                              └───────────────────┘
                              ┌───────────────────┐
  "name" → hash() → 1         │  ┌───────────┐    │
                              │  │"name":"Bruce"│  │
                              │  └───────────┘    │
                              └───────────────────┘
                              ┌───────────────────┐
  "city" → hash() → 2         │  ┌───────────┐    │
                              │  │"city":"Taipei"│ │
                              │  └───────────┘    │
                              └───────────────────┘
                              ┌───────────────────────────────┐
  "age" → hash() → 3          │  ┌───────────┐  ┌───────────┐ │
  "code" → hash() → 3         │  │"age": 30  │  │"code":"TW" │ │ ← Collision!
  "job" → hash() → 3          │  └───────────┘  └───────────┘ │    Bucket array grows
                              └───────────────────────────────┘
*/

// Simplified HashTable implementation
class SimpleHashTable {
  constructor() {
    this.buckets = Array(4).fill().map(() => []);
  }
  
  hash(key) {
    return String(key).length % this.buckets.length;
  }
  
  set(key, value) {
    const index = this.hash(key);
    const bucket = this.buckets[index];
    
    const item = bucket.find(item => item.key === key);
    if (item) {
      item.value = value;
    } else {
      bucket.push({ key, value });
    }
  }
  
  get(key) {
    const index = this.hash(key);
    const bucket = this.buckets[index];
    const item = bucket.find(item => item.key === key);
    return item ? item.value : undefined;
  }
}

// Usage example (showing collisions)
const table = new SimpleHashTable();

// 'name' and 'code' both hash to index 0
table.set('name', 'Bruce');
table.set('code', 'TW');

// 'age' and 'job' both hash to index 3
table.set('age', 30);
table.set('job', 'Dev');

// View bucket contents
console.log('Bucket 0:', table.buckets[0]);
// Output: [
//   { key: 'name', value: 'Bruce' },
//   { key: 'code', value: 'TW' }
// ]

console.log('Bucket 3:', table.buckets[3]);
// Output: [
//   { key: 'age', value: 30 },
//   { key: 'job', value: 'Dev' }
// ]

The actual Map implementation is more complex, including dynamic size adjustment, efficient hash functions, and optimized collision handling. When there are too many collisions, lookup efficiency degrades from O(1) to O(n), so modern implementations balance bucket count with content. Map and Set's main operations typically maintain near O(1) time complexity, which is why they are widely used.

（5）How does Set handle duplicate values? What's the internal mechanism?

Answer:Set checks if a value already exists when adding it, using Same-value-zero comparison:

// Set handling primitive type duplicate values
const set = new Set();

// Number type
set.add(1);
set.add(1);     // Won't add
console.log(set.size); // 1

// NaN comparison
set.add(NaN);
set.add(NaN);   // Won't add
console.log(set.size); // 2

// Object comparison
const obj1 = { id: 1 };
const obj2 = { id: 1 };
set.add(obj1);
set.add(obj2); // Will add, different references
console.log(set.size); // 3

set.add(obj1); // Won't add, same reference
console.log(set.size); // 3