কম্পিউটার টিউটোরিয়াল

ডেটা স্ট্রাকচরে অ্যাসিমেট্রিক হ্যাশিং


এই বিভাগে আমরা দেখব অ্যাসিমেট্রিক হ্যাশিং কৌশল কী। এই কৌশলে হ্যাশ টেবিল d সংখ্যক ব্লকে ভাগ করা হয়। প্রতিটি ভাগের দৈর্ঘ্য n/d। প্রোব ভ্যালু xi, 0 ≤ i ≤ d, একইভাবে $$\left\{\frac{i*n}{d},...,\frac{(i+1)*n}{d-1}\right\}$$ থেকে আहरণ করা হয়। মাল্টিপল চয়েস হ্যাশিংয়ের মতো, x ইন্সার্ট করতে, অ্যালগরিদম A[x0], A[x1], ..., A[xd-1] লিস্টগুলোর দৈর্ঘ্য চেক করে। তারপর x কে সবচেয়ে ছোট লিস্টে যুক্ত করে। যদি টাই হয়, তবে সেটি সবচেয়ে ছোট ইনডেক্স वाले লিস্টে ইন্সার্ট করে।

Vocking অনুযায়ী, অ্যাসিমেট্রিক হ্যাশিং-এর জন্য সবচেয়ে লম্বা লিস্টের প্রত্যাশিত দৈর্ঘ্য:

$$E[W]\leq\frac{\ln\ln n}{d\ln\phi_{2}}+O(1)$$

ফাংশন φd হল স্বর্ণ অনুপাতের জেনারেলাইজেশন, তাই $$\phi_{2}=\frac{(1+\sqrt{5})}{2}$$


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

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

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

  4. হাফ-এজ ডেটা স্ট্রাকচার