Hashing परिचय

Hashing एक magic coat check जैसा है जो आपका नाम एक hook number में बदल देता है ताकि आप तुरंत ढूंढ सकें आपका coat कहां लटका है।

In this page:

What is Hashing
Hash Function
Hash Table
Hashing Benefits
Hashing Uses

Syntax

markup

index = hash(key) % table_size
table[index] = value

What is Hashing

Hashing एक key, जैसे एक string या एक number, को एक table में एक specific position में map करने की एक technique है, ताकि उस key से associated data लगभग तुरंत store और ढूंढा जा सके।

उदाहरण: What is Hashing

#include <iostream>
#include <string>
using namespace std;
int hashFn(string key, int size) {
	int sum = 0;
	for (char c : key) sum += c;
	return sum % size;
}
int main() {
	cout << "Index for 'cat': " << hashFn("cat", 10);
	return 0;
}

public class Main {
	static int hashFn(String key, int size) {
		int sum = 0;
		for (char c : key.toCharArray()) sum += c;
		return sum % size;
	}
	public static void main(String[] args) {
		System.out.println("Index for 'cat': " + hashFn("cat", 10));
	}
}

def hash_fn(key, size):
    return sum(ord(c) for c in key) % size

print("Index for 'cat':", hash_fn("cat", 10))

#include <stdio.h>
#include <string.h>
int hashFn(char *key, int size) {
	int sum = 0;
	for (int i = 0; i < strlen(key); i++) sum += key[i];
	return sum % size;
}
int main() {
	printf("Index for 'cat': %d", hashFn("cat", 10));
	return 0;
}

Hash Function

एक hash function एक key को input के रूप में लेता है और एक integer index को output के रूप में produce करता है, और एक अच्छा hash function अलग-अलग keys को available table positions में evenly फैलाता है collisions को minimize करने के लिए।

उदाहरण: Hash Function

#include <iostream>
#include <string>
using namespace std;
int hashFn(string key, int size) {
	int sum = 0;
	for (char c : key) sum += c;
	return sum % size;
}
int main() {
	string keys[] = {"cat", "dog", "bird"};
	for (string k : keys) cout << k << " -> " << hashFn(k, 7) << endl;
	return 0;
}

public class Main {
	static int hashFn(String key, int size) {
		int sum = 0;
		for (char c : key.toCharArray()) sum += c;
		return sum % size;
	}
	public static void main(String[] args) {
		String[] keys = {"cat", "dog", "bird"};
		for (String k : keys) System.out.println(k + " -> " + hashFn(k, 7));
	}
}

def hash_fn(key, size):
    return sum(ord(c) for c in key) % size

for k in ("cat", "dog", "bird"):
    print(k, "->", hash_fn(k, 7))

#include <stdio.h>
#include <string.h>
int hashFn(char *key, int size) {
	int sum = 0;
	for (int i = 0; i < strlen(key); i++) sum += key[i];
	return sum % size;
}
int main() {
	char *keys[] = {"cat", "dog", "bird"};
	for (int i = 0; i < 3; i++) printf("%s -> %d\n", keys[i], hashFn(keys[i], 7));
	return 0;
}

Hash Table

एक hash table वह data structure है जो असल में values को उन positions पर store करता है जिन पर उनकी keys hash होती हैं, एक array को एक hash function के साथ combine करते हुए इसे सिर्फ numbers के बजाय arbitrary keys उपयोग करके fast, index-जैसा access देने के लिए।

उदाहरण: Hash Table

#include <iostream>
#include <string>
using namespace std;
int main() {
	string table[10] = {};
	int idx = 3;
	table[idx] = "apple";
	cout << "Stored at index " << idx << ": " << table[idx];
	return 0;
}

public class Main {
	public static void main(String[] args) {
		String[] table = new String[10];
		int idx = 3;
		table[idx] = "apple";
		System.out.println("Stored at index " + idx + ": " + table[idx]);
	}
}

table = [None] * 10
idx = 3
table[idx] = "apple"
print("Stored at index", idx, ":", table[idx])

#include <stdio.h>
int main() {
	char *table[10] = {0};
	int idx = 3;
	table[idx] = "apple";
	printf("Stored at index %d: %s", idx, table[idx]);
	return 0;
}

Hashing Benefits

चूंकि एक hash function data में search करने के बजाय सीधे एक index compute करता है, hashing average-case O(1) lookup, insertion, और deletion देता है, एक plain list को चाहिए O(n) search से नाटकीय रूप से तेज़।

उदाहरण: Hashing Benefits

#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
	unordered_map<string, int> m;
	m["apple"] = 5;
	cout << "Direct hash lookup: " << m["apple"] << " (no scanning needed)";
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		HashMap<String, Integer> m = new HashMap<>();
		m.put("apple", 5);
		System.out.println("Direct hash lookup: " + m.get("apple") + " (no scanning needed)");
	}
}

m = {"apple": 5}
print("Direct hash lookup:", m["apple"], "(no scanning needed)")

#include <stdio.h>
int main() {
	printf("Direct hash lookup: 5 (no scanning needed)");
	return 0;
}

Hashing Uses

Hashing सीधे hash maps और hash sets के पीछे है, और computing में हर जगह indirectly दिखता है, caches, databases, password storage, और बड़े datasets में duplicates efficiently detect करना सहित।

उदाहरण: Hashing Uses

#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
	int arr[] = {1, 2, 3, 2, 4, 1};
	unordered_set<int> seen;
	for (int x : arr) {
		if (seen.count(x)) cout << "Duplicate found: " << x << endl;
		seen.insert(x);
	}
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		int[] arr = {1, 2, 3, 2, 4, 1};
		Set<Integer> seen = new HashSet<>();
		for (int x : arr) {
			if (seen.contains(x)) System.out.println("Duplicate found: " + x);
			seen.add(x);
		}
	}
}

arr = [1, 2, 3, 2, 4, 1]
seen = set()
for x in arr:
    if x in seen:
        print("Duplicate found:", x)
    seen.add(x)

#include <stdio.h>
int main() {
	int arr[] = {1, 2, 3, 2, 4, 1};
	int seen[10] = {0};
	for (int i = 0; i < 6; i++) {
		if (seen[arr[i]]) printf("Duplicate found: %d\n", arr[i]);
		seen[arr[i]] = 1;
	}
	return 0;
}

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Priority Queue Next Lesson → Hash Maps and Hash Sets