← Back to DSA Course | Chapter 7: Hashing | Lesson 3 of 5

Collision को Handle करना

एक collision दो kids को उसी chair पर बैठने को कहे जाने जैसा है। आपको एक plan चाहिए, जैसे एक और chair ढूंढना या एक list के साथ एक share करना।

In this page:

  1. What is a Collision
  2. Linear Probing
  3. Chaining
  4. Collision Effects
  5. Good Hashing
Syntax
markup 
# Chaining: each slot holds a list
table[hash(key) % size].append((key, value))

# Linear probing: try the next slot
i = hash(key) % size
while table[i] is not None:
    i = (i + 1) % size
table[i] = (key, value)

What is a Collision

एक collision तब होता है जब एक hash function दो अलग keys को hash table में उसी position पर map करता है, जो आमतौर पर unavoidable है क्योंकि possible keys की संख्या आमतौर पर table के size से कहीं बड़ी होती है।

उदाहरण: What is a Collision

#include <iostream>
using namespace std;
int hashFn(int key, int size) { return key % size; }
int main() {
	cout << "hash(12)=" << hashFn(12, 5) << " hash(7)=" << hashFn(7, 5) << " (same slot = collision)";
	return 0;
}
public class Main {
	static int hashFn(int key, int size) { return key % size; }
	public static void main(String[] args) {
		System.out.println("hash(12)=" + hashFn(12, 5) + " hash(7)=" + hashFn(7, 5) + " (same slot = collision)");
	}
}
def hash_fn(key, size):
    return key % size

print("hash(12)=", hash_fn(12, 5), "hash(7)=", hash_fn(7, 5), "(same slot = collision)")
#include <stdio.h>
int hashFn(int key, int size) { return key % size; }
int main() {
	printf("hash(12)=%d hash(7)=%d (same slot = collision)", hashFn(12, 5), hashFn(7, 5));
	return 0;
}

Linear Probing

Linear probing एक collision को table में अगली slot जांचकर handle करता है, और उसके बाद वाली, वगैरह, जब तक नई key रखने के लिए एक खाली position न मिल जाए।

उदाहरण: Linear Probing

#include <iostream>
using namespace std;
int main() {
	int table[5] = {-1, -1, -1, -1, -1};
	int keys[] = {12, 7, 17};
	for (int k : keys) {
		int idx = k % 5;
		while (table[idx] != -1) idx = (idx + 1) % 5;
		table[idx] = k;
	}
	for (int i = 0; i < 5; i++) cout << table[i] << " ";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] table = {-1, -1, -1, -1, -1};
		int[] keys = {12, 7, 17};
		for (int k : keys) {
			int idx = k % 5;
			while (table[idx] != -1) idx = (idx + 1) % 5;
			table[idx] = k;
		}
		for (int v : table) System.out.print(v + " ");
	}
}
table = [-1] * 5
keys = [12, 7, 17]
for k in keys:
    idx = k % 5
    while table[idx] != -1:
        idx = (idx + 1) % 5
    table[idx] = k
print(table)
#include <stdio.h>
int main() {
	int table[5] = {-1, -1, -1, -1, -1};
	int keys[] = {12, 7, 17};
	for (int i = 0; i < 3; i++) {
		int idx = keys[i] % 5;
		while (table[idx] != -1) idx = (idx + 1) % 5;
		table[idx] = keys[i];
	}
	for (int i = 0; i < 5; i++) printf("%d ", table[i]);
	return 0;
}

Chaining

Chaining एक collision को अलग तरीके से handle करता है: एक और slot ढूंढने के बजाय, हर table position उन सभी key-value pairs की एक छोटी list (एक bucket) रखता है जो वहां hash हुए, इसलिए colliding keys बस वही bucket share करती हैं।

उदाहरण: Chaining

#include <iostream>
#include <vector>
using namespace std;
int main() {
	vector<int> buckets[5];
	int keys[] = {12, 7, 17};
	for (int k : keys) buckets[k % 5].push_back(k);
	cout << "Bucket 2: ";
	for (int v : buckets[2]) cout << v << " ";
	return 0;
}
import java.util.*;
public class Main {
	public static void main(String[] args) {
		List<List<Integer>> buckets = new ArrayList<>();
		for (int i = 0; i < 5; i++) buckets.add(new ArrayList<>());
		for (int k : new int[]{12, 7, 17}) buckets.get(k % 5).add(k);
		System.out.println("Bucket 2: " + buckets.get(2));
	}
}
buckets = [[] for _ in range(5)]
for k in (12, 7, 17):
    buckets[k % 5].append(k)
print("Bucket 2:", buckets[2])
#include <stdio.h>
int main() {
	int bucket2[5], count = 0;
	int keys[] = {12, 7, 17};
	for (int i = 0; i < 3; i++) if (keys[i] % 5 == 2) bucket2[count++] = keys[i];
	printf("Bucket 2: ");
	for (int i = 0; i < count; i++) printf("%d ", bucket2[i]);
	return 0;
}

Collision Effects

जब बहुत सारी keys उसी slots या buckets में collide होती हैं, lookups ideal O(1) से O(n) की ओर degrade होते हैं, क्योंकि table को सही एक तुरंत ढूंढने के बजाय कई candidates जांचने पड़ते हैं।

उदाहरण: Collision Effects

#include <iostream>
using namespace std;
int main() {
	int bucketSize = 4;
	cout << "Bucket has " << bucketSize << " keys -- lookup now checks all " << bucketSize << ", degrading toward O(n)";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int bucketSize = 4;
		System.out.println("Bucket has " + bucketSize + " keys -- lookup now checks all " + bucketSize + ", degrading toward O(n)");
	}
}
bucket_size = 4
print("Bucket has", bucket_size, "keys -- lookup now checks all", bucket_size, ", degrading toward O(n)")
#include <stdio.h>
int main() {
	int bucketSize = 4;
	printf("Bucket has %d keys -- lookup now checks all %d, degrading toward O(n)", bucketSize, bucketSize);
	return 0;
}

Good Hashing

एक अच्छा hash function collisions के खिलाफ असली defense है: इसे keys को पूरे table में जितना संभव हो evenly फैलाना चाहिए, जो buckets को छोटा और linear-probing chains को उनकी starting slot के करीब रखता है।

उदाहरण: Good Hashing

#include <iostream>
using namespace std;
int poorHash(int key) { return key % 2; }
int goodHash(int key) { return (key * 2654435761u) % 10; }
int main() {
	cout << "poor(4)=" << poorHash(4) << " poor(6)=" << poorHash(6) << " (collide)\n";
	cout << "good(4)=" << goodHash(4) << " good(6)=" << goodHash(6) << " (spread out)";
	return 0;
}
public class Main {
	static int poorHash(int key) { return key % 2; }
	static int goodHash(int key) { return (int)((key * 2654435761L) % 10); }
	public static void main(String[] args) {
		System.out.println("poor(4)=" + poorHash(4) + " poor(6)=" + poorHash(6) + " (collide)");
		System.out.println("good(4)=" + goodHash(4) + " good(6)=" + goodHash(6) + " (spread out)");
	}
}
def poor_hash(key):
    return key % 2

def good_hash(key):
    return (key * 2654435761) % 10

print("poor(4)=", poor_hash(4), "poor(6)=", poor_hash(6), "(collide)")
print("good(4)=", good_hash(4), "good(6)=", good_hash(6), "(spread out)")
#include <stdio.h>
int poorHash(int key) { return key % 2; }
int goodHash(int key) { return (key * 2654435761u) % 10; }
int main() {
	printf("poor(4)=%d poor(6)=%d (collide)\n", poorHash(4), poorHash(6));
	printf("good(4)=%d good(6)=%d (spread out)", goodHash(4), goodHash(6));
	return 0;
}
Related Topics

Hash Maps और Hash Sets · Two Sum समस्या · Hashing परिचय · Frequency Counting कैसे करें

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. % size से wrap किए बिना Linear probing, इसलिए search table के आखिर से आगे निकल जाती है।
  2. Table के full होने और probing को कभी एक खाली slot न मिलने पर हमेशा के लिए loop करना।
  3. एक open-addressing table में एक item को बस इसकी slot खाली करके delete करना, जो बाद की searches को तोड़ता है जो इससे होकर गुज़रीं।
🔒

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Hash Maps and Hash Sets Next Lesson → Two Sum Problem

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.