হ্যাশ ফাংশন এবং কোলিশন হ্যান্ডলিং হল ডেটা স্ট্রাকচারগুলির একটি গুরুত্বপূর্ণ অংশ, যা মূলত হ্যাশ টেবিলের সঙ্গে সম্পর্কিত। হ্যাশ ফাংশন একটি ইনপুট ডেটাকে একটি নির্দিষ্ট আকারের হ্যাশ ভ্যালুতে রূপান্তর করে। কোলিশন তখন ঘটে যখন দুটি ভিন্ন ইনপুট একই হ্যাশ ভ্যালু প্রাপ্ত করে। কোলিশন হ্যান্ডলিং মেথডগুলি এই সমস্যাগুলি সমাধানের জন্য ব্যবহৃত হয়। নিচে বিভিন্ন হ্যাশ ফাংশন এবং কোলিশন হ্যান্ডলিং পদ্ধতির বিশদ আলোচনা করা হলো।
হ্যাশ ফাংশন
বিবরণ: হ্যাশ ফাংশন হল একটি অ্যালগরিদম যা ইনপুট ডেটার একটি নির্দিষ্ট আকারের হ্যাশ ভ্যালু তৈরি করে। এটি সাধারণত একটি সংখ্যা হিসাবে রিটার্ন করে যা একটি ইনপুট ডেটার প্রতিনিধিত্ব করে।
বৈশিষ্ট্য:
- নির্মাণশীলতা: হ্যাশ ফাংশন যতটা সম্ভব ইউনিক হ্যাশ ভ্যালু তৈরি করার চেষ্টা করে।
- দ্রুততা: দ্রুত এবং কার্যকরী হওয়া উচিত যাতে ডেটার দ্রুত অ্যাক্সেস নিশ্চিত হয়।
কোলিশন হ্যান্ডলিং মেথড
কোলিশন হ্যান্ডলিং পদ্ধতিগুলি মূলত দুটি বিভাগে ভাগ করা হয়: Chaining এবং Open Addressing।
১. Chaining
বিবরণ: Chaining কোলিশন হ্যান্ডলিংয়ের একটি পদ্ধতি যেখানে একই হ্যাশ ভ্যালু প্রাপ্ত এলিমেন্টগুলিকে একটি লিঙ্কড লিস্টে সংরক্ষণ করা হয়। এটি একটি অ্যালগরিদমে সব উপাদানগুলিকে সেই হ্যাশ ভ্যালুর সাথে যুক্ত করে।
উদাহরণ:
class HashTable:
def __init__(self):
self.table = [[] for _ in range(10)] # 10 টি লিঙ্কড লিস্ট
def hash_function(self, key):
return hash(key) % len(self.table)
def insert(self, key, value):
index = self.hash_function(key)
# যদি কোলিশন ঘটে, তবে কেবল লিস্টে যোগ করুন
for item in self.table[index]:
if item[0] == key:
item[1] = value
return
self.table[index].append([key, value]) # নতুন এলিমেন্ট যুক্ত করুন
def get(self, key):
index = self.hash_function(key)
for item in self.table[index]:
if item[0] == key:
return item[1]
return None # যদি না পাওয়া যায়
# ব্যবহার
ht = HashTable()
ht.insert("apple", 10)
ht.insert("banana", 20)
ht.insert("orange", 30)
ht.insert("apple", 15) # কোলিশন ঘটে
print(ht.get("apple")) # আউটপুট: 15
২. Open Addressing
বিবরণ: Open Addressing পদ্ধতিতে, কোলিশন ঘটলে পরবর্তী খালি স্থান (slot) খুঁজে বের করা হয়। এটি বিভিন্ন পদ্ধতিতে করতে পারে, যেমন লিনিয়ার প্রোবিং, কোয়াড্রাটিক প্রোবিং, এবং ডাবল হ্যাশিং।
- লিনিয়ার প্রোবিং: পরবর্তী স্লটে খালি স্থান খুঁজে বের করা।
- কোয়াড্রাটিক প্রোবিং: পরবর্তী স্লট খোঁজার সময় একটি বর্গমূলের ভিত্তিতে স্থানান্তর করা।
- ডাবল হ্যাশিং: একটি দ্বিতীয় হ্যাশ ফাংশন ব্যবহার করা।
উদাহরণ (লিনিয়ার প্রোবিং):
class OpenAddressingHashTable:
def __init__(self):
self.table = [None] * 10 # 10 টি স্থান
def hash_function(self, key):
return hash(key) % len(self.table)
def insert(self, key, value):
index = self.hash_function(key)
while self.table[index] is not None: # স্থান না পাওয়া পর্যন্ত খুঁজুন
index = (index + 1) % len(self.table)
self.table[index] = (key, value) # নতুন এলিমেন্ট যুক্ত করুন
def get(self, key):
index = self.hash_function(key)
while self.table[index] is not None:
if self.table[index][0] == key:
return self.table[index][1]
index = (index + 1) % len(self.table)
return None # যদি না পাওয়া যায়
# ব্যবহার
ht = OpenAddressingHashTable()
ht.insert("apple", 10)
ht.insert("banana", 20)
ht.insert("orange", 30)
ht.insert("apple", 15) # কোলিশন ঘটে
print(ht.get("apple")) # আউটপুট: 15
উপসংহার
হ্যাশ ফাংশন এবং কোলিশন হ্যান্ডলিং হল ডেটা স্ট্রাকচারের গুরুত্বপূর্ণ অংশ। Chaining এবং Open Addressing কোলিশন হ্যান্ডলিংয়ের দুটি মৌলিক পদ্ধতি। Chaining লিঙ্কড লিস্ট ব্যবহার করে কোলিশন মোকাবেলা করে, যেখানে Open Addressing খালি স্থান খুঁজে বের করে। এই দুটি পদ্ধতি নির্বাচনের ক্ষেত্রে তাদের নিজস্ব সুবিধা এবং অসুবিধা রয়েছে এবং সঠিক পদ্ধতি নির্বাচন ডেটা স্ট্রাকচারের কার্যকারিতা প্রভাবিত করতে পারে।
