হ্যাশ ফাংশন এবং হ্যাশ টেবিল

হ্যাশিং হল হ্যাশ ফাংশন নামে পরিচিত একটি গাণিতিক ফাংশন ব্যবহার করে একটি পাঠ্য বা সংখ্যার তালিকা থেকে একটি মান তৈরি করার প্রক্রিয়া৷ অনেক হ্যাশ ফাংশন রয়েছে যা সংখ্যাসূচক সংখ্যাসূচক বা আলফানিউমেরিক কী ব্যবহার করে৷ বিভিন্ন হ্যাশ ফাংশন নিচে দেওয়া হল:

হ্যাশ ফাংশন

নিচের কয়েকটি হ্যাশ ফাংশন −

বিভাগ পদ্ধতি

এটি একটি হ্যাশ ফাংশন তৈরি করার সবচেয়ে সহজ পদ্ধতি। হ্যাশ ফাংশনকে −

h(k) = k mod n

এখানে, h(k) হল হ্যাশ ভ্যালু কে কী ভ্যালু k কে হ্যাশ টেবিল n এর সাইজ দিয়ে ভাগ করে অবশিষ্টাংশ ব্যবহার করে প্রাপ্ত। এটি সবচেয়ে ভাল যে n একটি মৌলিক সংখ্যা কারণ এটি নিশ্চিত করে যে কীগুলি আরও অভিন্নতার সাথে বিতরণ করা হয়েছে৷

বিভাগ পদ্ধতির একটি উদাহরণ নিম্নরূপ -

k=1276
n=10
h(1276) = 1276 mod 10
= 6

প্রাপ্ত হ্যাশ মান হল 6

বিভাগ পদ্ধতি আইডির একটি অসুবিধা যা হ্যাশ টেবিলের পরপর হ্যাশ মানের সাথে ধারাবাহিক কী ম্যাপ করে। এটি একটি খারাপ কর্মক্ষমতা বাড়ে।

গুণ পদ্ধতি

গুণন পদ্ধতির জন্য ব্যবহৃত হ্যাশ ফাংশন হল −

h(k) = floor( n( kA mod 1 ) )

এখানে, k হল কী এবং A 0 এবং 1 এর মধ্যে যেকোনো ধ্রুবক মান হতে পারে। 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

প্রাপ্ত হ্যাশ মান হল 1

গুণন পদ্ধতির একটি সুবিধা হল যে এটি A-এর যেকোনো মানের সাথে কাজ করতে পারে, যদিও কিছু মান অন্যদের থেকে ভালো বলে মনে করা হয়।

মিড স্কোয়ার পদ্ধতি

মধ্য বর্গক্ষেত্র পদ্ধতি একটি খুব ভাল হ্যাশ ফাংশন. এতে কীটির মান বর্গ করা এবং তারপর হ্যাশ মান হিসাবে মধ্যবর্তী r সংখ্যাগুলি বের করা জড়িত। হ্যাশ টেবিলের আকার অনুযায়ী r এর মান নির্ধারণ করা যেতে পারে।

মিড স্কোয়ার পদ্ধতির একটি উদাহরণ নিম্নরূপ -

ধরুন হ্যাশ টেবিলে 100টি মেমরি অবস্থান রয়েছে। তাই r=2 কারণ মেমরি অবস্থানের কী ম্যাপ করার জন্য দুটি সংখ্যা প্রয়োজন।

k = 50
k*k = 2500
h(50) = 50

The hash value obtained is 50

হ্যাশ টেবিল

একটি হ্যাশ টেবিল হল একটি ডেটা স্ট্রাকচার যা মানগুলির কী ম্যাপ করে। এটি একটি হ্যাশ ফাংশন ব্যবহার করে ডেটা কীর জন্য সূচক গণনা করে এবং কীটি সূচীতে সংরক্ষণ করা হয়।

একটি হ্যাশ টেবিলের একটি উদাহরণ নিম্নরূপ -

হ্যাশ টেবিলে যে মূল ক্রমটি সংরক্ষণ করা প্রয়োজন তা হল −

35 50 11 79 76 85

হ্যাশ ফাংশন h(k) ব্যবহৃত হয়:

h(k) = k mod 10

লিনিয়ার প্রোবিং ব্যবহার করে, মানগুলি হ্যাশ টেবিলে −