হ্যাশিং হল একটি টেক্সট বা সংখ্যার তালিকা থেকে একটি মান জেনারেট করার প্রক্রিয়া, যাকে হ্যাশ ফাংশন বলা হয় একটি গাণিতিক ফাংশন ব্যবহার করে। অনেক হ্যাশ ফাংশন আছে যেগুলো न्यুমেরিক বা অ্যালফানিউমেরিক কী ব্যবহার করে। নিচে বিভিন্ন হ্যাশ ফাংশন দেওয়া হলো:
হ্যাশ ফাংশন
নিচে কিছু হ্যাশ ফাংশন দেওয়া হলো:
ডিভিশন মেথড (Division Method)
হ্যাশ ফাংশন তৈরি করার সবচেয়ে সহজ পদ্ধতি। হ্যাশ ফাংশন নিচে বর্ণনা করা হলো:
h(k) = k mod n
এখানে, h(k) হল কী ভ্যালু k কে হ্যাশ টেবিলের আকার n দিয়ে ভাগ করে অবশিষ্টাংশ দিয়ে প্রাপ্ত হ্যাশ ভ্যালু। n কে প্রাইম নম্বর রাখা ভালো কারণ এটি নিশ্চিত করে যে কীগুলো আরও ইউনিফর্মলি ডিস্ট্রিবিউট হবে।
ডিভিশন মেথডের একটি উদাহরণ:
k=1276 n=10 h(1276) = 1276 mod 10 = 6
প্রাপ্ত হ্যাশ ভ্যালু ৬
ডিভিশন মেথডের একটি ডিসঅ্যাডভান্টেজ হল ক্রমাগত কী হ্যাশ টেবিলে ক্রমাগত হ্যাশ ভ্যালুতে ম্যাপ হয়। এর ফলে খারাপ পারফরম্যান্স হয়।
মাল্টিপ্লিকেশন মেথড (Multiplication Method)
মাল্টিপ্লিকেশন মেথডের জন্য হ্যাশ ফাংশন হল:
h(k) = floor( n( kA mod 1 ) )
এখানে, k হল কী এবং A ০ এবং ১ এর মধ্যে যেকোনো কনস্ট্যান্ট ভ্যালু হতে পারে। k এবং A উভয় গুণ করা হয় এবং তাদের ভাগ্নাংশ অংশ আলাদা করা হয়। এরপর এটি n দিয়ে গুণ করে হ্যাশ ভ্যালু পাওয়া যায়।
মাল্টিপ্লিকেশন মেথডের একটি উদাহরণ:
k=123 n=100 A=0.618033 h(123) = 100 (123 * 0.618033 mod 1) = 100 (76.018059 mod 1) = 100 (0.018059) = 1
প্রাপ্ত হ্যাশ ভ্যালু ১
মাল্টিপ্লিকেশন মেথডের একটি সুবিধা হল এটি A-এর যেকোনো মান দিয়ে কাজ করতে পারে, যদিও কিছু মান অন্যদের চেয়ে ভালো মনে হয়।
মিড স্কোয়ার মেথড (Mid Square Method)
মিড স্কোয়ার মেথড একটি খুব ভালো হ্যাশ ফাংশন। এতে কী-এর মান বর্গ করা হয় এবং তারপর মাঝপথের r ডিজিট বের করে হ্যাশ ভ্যালু হিসেবে নেওয়া হয়। r-এর মান হ্যাশ টেবিলের আকার অনুযায়ী নির্ধারিত করা যায়।
মিড স্কোয়ার মেথডের একটি উদাহরণ:
ধরি হ্যাশ টেবিলে ১০০টি মেমোরি লোকেশন আছে। তাই r=2 কারণ দুটি ডিজিট লাগে কীকে মেমোরি লোকেশনে ম্যাপ করতে।
k = 50 k*k = 2500 h(50) = 50 প্রাপ্ত হ্যাশ ভ্যালু ৫০
হ্যাশ টেবিল (Hash Tables)
হ্যাশ টেবিল একটি ডেটা স্ট্রাকচার যা কীকে ভ্যালুতে ম্যাপ করে। এটি হ্যাশ ফাংশন ব্যবহার করে ডেটা কী-এর ইনডেক্স ক্যালকুলেট করে এবং কীটি সেই ইনডেক্সে সংরক্ষিত হয়।
হ্যাশ টেবিলের একটি উদাহরণ:
হ্যাশ টেবিলে সংরক্ষণ করার জন্য কী সিকোয়েন্স:
35 50 11 79 76 85
ব্যবহৃত হ্যাশ ফাংশন h(k):
h(k) = k mod 10
লিনিয়ার প্রোবিং ব্যবহার করে, মানগুলো হ্যাশ টেবিলে নিচে সংরক্ষিত হয়:
