কম্পিউটার

ডেটা স্ট্রাকচারে গুন দ্বারা হ্যাশিং


এখানে আমরা গুণন পদ্ধতির সাথে হ্যাশিং সম্পর্কে আলোচনা করব। এর জন্য আমরা হ্যাশ ফাংশন −

ব্যবহার করি
ℎ(𝑥) = ⌊𝑚𝑥𝐴⌋ 𝑚𝑜𝑑 𝑚

এখানে A একটি বাস্তব-মূল্যবান ধ্রুবক। এই পদ্ধতির সুবিধা হল m এর মান এতটা সমালোচনামূলক নয়। আমরা m কে 2 এর শক্তি হিসাবেও নিতে পারি। যদিও A-এর যেকোনো মান হ্যাশ ফাংশন দেয়, তবে A-এর কিছু মান অন্যদের থেকে ভালো।

নুথের মতে, আমরা A এর জন্য সোনালী অনুপাত ব্যবহার করতে পারি, তাই A হবে

$$A=\frac{\sqrt5-1}{2}=0.61803398$$

অবশ্যই, A-এর জন্য যে মানই বেছে নেওয়া হোক না কেন। পায়রার হোল নীতিটি বোঝায় যে যদি u ≥ nm হয়, তাহলে একটি হ্যাশ মান থাকবে i এবং কিছু S ⊆ U আকারের n, যেমন h(x) =i সমস্ত x এর জন্য এস.

তাই আমরা বলতে পারি যে গুন দ্বারা সবচেয়ে খারাপ ক্ষেত্রে হ্যাশিং ভাগ দ্বারা হ্যাশিং এর মতই খারাপ।


  1. ডেটা স্ট্রাকচারে লিনিয়ার প্রোবিং

  2. ডেটা স্ট্রাকচারে চেইনিংয়ের সাথে হ্যাশিং

  3. ডেটা স্ট্রাকচারে আর-ট্রি

  4. অর্ধেক ডাটা স্ট্রাকচার