Learn Hash Maps and Hash Sets — Free DSA Tutorial

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;
}

Hash Maps and Hash Sets

Hash Map

Hash Set

Map Operations

Set Operations

Common Uses

Chapter Quiz — Complete all 5 topics to unlock

Login to run this code