Hash Maps and Hash Sets

A hash map is like a dictionary of labeled drawers, where each key tells you exactly which drawer holds the value, and a hash set just keeps track of which labels exist.

In this page:

Hash Map
Hash Set
Map Operations
Set Operations
Common Uses

Syntax

markup

hash_map = {}
hash_map[key] = value
value = hash_map.get(key)
del hash_map[key]

hash_set = set()
hash_set.add(value)
exists = value in hash_set

Hash Map

A hash map stores data as key-value pairs, using a hash function on the key to decide where the pair is stored internally, which is what lets you look up a value by its key in average O(1) time.

Example: Hash Map

#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
	unordered_map<string, int> ages;
	ages["Alice"] = 30;
	ages["Bob"] = 25;
	cout << "Alice is " << ages["Alice"] << " years old";
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		HashMap<String, Integer> ages = new HashMap<>();
		ages.put("Alice", 30);
		ages.put("Bob", 25);
		System.out.println("Alice is " + ages.get("Alice") + " years old");
	}
}

ages = {"Alice": 30, "Bob": 25}
print("Alice is", ages["Alice"], "years old")

#include <stdio.h>
#include <string.h>
int main() {
	char *names[] = {"Alice", "Bob"};
	int ages[] = {30, 25};
	printf("Alice is %d years old", ages[0]);
	return 0;
}

Hash Set

A hash set stores just values, no separate keys, and its whole purpose is to guarantee that every value it contains is unique, using the same hashing mechanism as a hash map to check for duplicates instantly.

Example: Hash Set

#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
	unordered_set<int> s;
	s.insert(5); s.insert(3); s.insert(5);
	cout << "Set size: " << s.size();
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Set<Integer> s = new HashSet<>();
		s.add(5); s.add(3); s.add(5);
		System.out.println("Set size: " + s.size());
	}
}

s = set()
s.add(5)
s.add(3)
s.add(5)
print("Set size:", len(s))

#include <stdio.h>
int main() {
	int values[] = {5, 3, 5};
	int unique[10] = {0}, count = 0;
	for (int i = 0; i < 3; i++) {
		if (!unique[values[i]]) { unique[values[i]] = 1; count++; }
	}
	printf("Set size: %d", count);
	return 0;
}

Map Operations

Hash maps support insertion, lookup, updating an existing key's value, and removal, all in average O(1) time, which is why they're the default choice whenever you need to associate data with a label.

Example: Map Operations

#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
	unordered_map<string, int> m;
	m["x"] = 1;
	m["x"] = 2;
	cout << "Updated: " << m["x"] << endl;
	m.erase("x");
	cout << "Contains x? " << m.count("x");
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		HashMap<String, Integer> m = new HashMap<>();
		m.put("x", 1);
		m.put("x", 2);
		System.out.println("Updated: " + m.get("x"));
		m.remove("x");
		System.out.println("Contains x? " + m.containsKey("x"));
	}
}

m = {}
m["x"] = 1
m["x"] = 2
print("Updated:", m["x"])
del m["x"]
print("Contains x?", "x" in m)

#include <stdio.h>
int main() {
	int x = 1;
	x = 2;
	printf("Updated: %d\n", x);
	int exists = 0;
	printf("Contains x? %d", exists);
	return 0;
}

Set Operations

Hash sets are ideal for membership testing (has this value been seen before?) and enforcing uniqueness, such as removing duplicate entries from a list or tracking which items have already been visited.

Example: Set Operations

#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
	unordered_set<int> visited;
	int nodes[] = {1, 2, 3};
	for (int n : nodes) visited.insert(n);
	cout << "Has 2? " << visited.count(2) << ", Has 5? " << visited.count(5);
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Set<Integer> visited = new HashSet<>();
		for (int n : new int[]{1, 2, 3}) visited.add(n);
		System.out.println("Has 2? " + visited.contains(2) + ", Has 5? " + visited.contains(5));
	}
}

visited = set()
for n in (1, 2, 3):
    visited.add(n)
print("Has 2?", 2 in visited, ", Has 5?", 5 in visited)

#include <stdio.h>
int main() {
	int visited[10] = {0};
	int nodes[] = {1, 2, 3};
	for (int i = 0; i < 3; i++) visited[nodes[i]] = 1;
	printf("Has 2? %d, Has 5? %d", visited[2], visited[5]);
	return 0;
}

Common Uses

Hash maps and sets show up constantly in DSA problems: counting frequencies, detecting duplicates, caching computed results, and grouping related items are all patterns built directly on top of hashing.

Example: Common Uses

#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
	string words[] = {"a", "b", "a", "c", "a"};
	unordered_map<string, int> freq;
	for (string w : words) freq[w]++;
	cout << "a appears " << freq["a"] << " times";
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		String[] words = {"a", "b", "a", "c", "a"};
		HashMap<String, Integer> freq = new HashMap<>();
		for (String w : words) freq.merge(w, 1, Integer::sum);
		System.out.println("a appears " + freq.get("a") + " times");
	}
}

words = ["a", "b", "a", "c", "a"]
freq = {}
for w in words:
    freq[w] = freq.get(w, 0) + 1
print("a appears", freq["a"], "times")

#include <stdio.h>
int main() {
	char words[] = {'a', 'b', 'a', 'c', 'a'};
	int count = 0;
	for (int i = 0; i < 5; i++) if (words[i] == 'a') count++;
	printf("a appears %d times", count);
	return 0;
}

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Hashing Introduction Next Lesson → Collision Handling