Map Basics

A hash map (also called dictionary, hash table, or object) stores key-value pairs with O(1) average-case lookup, insertion, and deletion.

Core Operations

• Set/Put: Store a key-value pair - O(1) average
• Get: Retrieve value by key - O(1) average
• Delete/Remove: Remove a key-value pair - O(1) average
• Has/Contains: Check if key exists - O(1) average

When to Use Maps

Maps are ideal when you need to:

• Associate values with keys
• Count frequencies
• Cache computed results
• Build indices for fast lookup
• Group items by property

Python Dictionary

# Creating dictionaries
scores = {'Alice': 95, 'Bob': 87, 'Charlie': 92}
empty_dict = {}
dict_from_pairs = dict([('a', 1), ('b', 2)])

# Adding/updating
scores['David'] = 88
scores['Alice'] = 98  # Update

# Accessing
print(scores['Alice'])        # 98
print(scores.get('Eve'))      # None (safe access)
print(scores.get('Eve', 0))   # 0 (with default)

# Removing
del scores['Bob']
removed = scores.pop('Charlie', None)  # Safe remove

# Checking membership
if 'Alice' in scores:
    print(f"Alice's score: {scores['Alice']}")

# Iterating
for name, score in scores.items():
    print(f"{name}: {score}")

# Keys and values
print(scores.keys())    # dict_keys(['Alice', 'David'])
print(scores.values())  # dict_values([98, 88])

JavaScript Map

// Creating maps
const scores = new Map([
  ['Alice', 95],
  ['Bob', 87],
  ['Charlie', 92],
]);

// Adding/updating
scores.set('David', 88);
scores.set('Alice', 98); // Update

// Accessing
console.log(scores.get('Alice')); // 98
console.log(scores.get('Eve')); // undefined

// Removing
scores.delete('Bob');

// Checking membership
if (scores.has('Alice')) {
  console.log(`Alice's score: ${scores.get('Alice')}`);
}

// Iterating
for (const [name, score] of scores) {
  console.log(`${name}: ${score}`);
}

// Keys and values
console.log([...scores.keys()]); // ['Alice', 'Charlie', 'David']
console.log([...scores.values()]); // [98, 92, 88]

// Size
console.log(scores.size); // 3

JavaScript Object (Alternative)

// Objects as maps (common in JS)
const scores = {
  Alice: 95,
  Bob: 87,
  Charlie: 92,
};

// Adding/updating
scores.David = 88;
scores['Alice'] = 98;

// Accessing
console.log(scores.Alice); // 98
console.log(scores['Bob']); // 87

// Checking membership
if ('Alice' in scores) {
  console.log(`Alice's score: ${scores.Alice}`);
}

// Iterating
for (const name in scores) {
  console.log(`${name}: ${scores[name]}`);
}

// Keys and values
console.log(Object.keys(scores)); // ['Alice', 'Bob', 'Charlie', 'David']
console.log(Object.values(scores)); // [98, 87, 92, 88]

Common Patterns

Counting Frequencies

def count_frequencies(items):
    freq = {}
    for item in items:
        freq[item] = freq.get(item, 0) + 1
    return freq

# Or use Counter from collections
from collections import Counter
freq = Counter([1, 2, 2, 3, 3, 3])
print(freq)  # Counter({3: 3, 2: 2, 1: 1})

Grouping Items

def group_by_length(words):
    groups = {}
    for word in words:
        length = len(word)
        if length not in groups:
            groups[length] = []
        groups[length].append(word)
    return groups

# Using defaultdict
from collections import defaultdict

def group_by_length_v2(words):
    groups = defaultdict(list)
    for word in words:
        groups[len(word)].append(word)
    return dict(groups)

words = ["a", "to", "at", "tea", "eat"]
print(group_by_length(words))
# {1: ['a'], 2: ['to', 'at'], 3: ['tea', 'eat']}

Caching Results

def fibonacci_cached(n, cache={}):
    if n in cache:
        return cache[n]

    if n <= 1:
        return n

    cache[n] = fibonacci_cached(n-1, cache) + fibonacci_cached(n-2, cache)
    return cache[n]

print(fibonacci_cached(50))  # Fast with caching!

defaultdict vs dict

from collections import defaultdict

# Regular dict
regular = {}
# regular['key'] += 1  # KeyError!

# defaultdict
counter = defaultdict(int)  # Default value: 0
counter['key'] += 1  # Works! Creates 0 first

grouped = defaultdict(list)  # Default value: []
grouped['key'].append('value')  # Works!

Time Complexity

*Worst case with hash collisions, rare in practice.

Key Insight

Maps are the workhorse data structure for many problems. When you need to remember something by a key, think map!