Hash Maps और Hash Sets

एक hash map labeled drawers की एक dictionary जैसा है, जहां हर key बिल्कुल बताती है कि कौन सा drawer value रखता है, और एक hash set बस track रखता है कि कौन से labels मौजूद हैं।

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

एक hash map data को key-value pairs के रूप में store करता है, key पर एक hash function उपयोग करके यह decide करते हुए कि pair internally कहां store है, जो आपको इसकी key से एक value average O(1) time में ढूंढने देता है।

उदाहरण: 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

एक hash set बस values store करता है, कोई अलग keys नहीं, और इसका पूरा purpose यह गारंटी देना है कि इसमें रखी हर value unique है, duplicates तुरंत check करने के लिए एक hash map जैसा ही hashing mechanism उपयोग करते हुए।

उदाहरण: 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 insertion, lookup, एक मौजूदा key की value update करना, और removal support करते हैं, सब average O(1) time में, यही कारण है कि वे data को एक label से associate करने की ज़रूरत होने पर default choice हैं।

उदाहरण: 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 membership testing (क्या यह value पहले देखी गई है?) और uniqueness enforce करने के लिए ideal हैं, जैसे एक list से duplicate entries हटाना या track करना कि कौन से items पहले से visited हैं।

उदाहरण: 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 और sets DSA problems में लगातार दिखते हैं: frequencies count करना, duplicates detect करना, computed results cache करना, और related items group करना सभी हैं patterns जो सीधे hashing के ऊपर बने हैं।

उदाहरण: 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