কম্পিউটার

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


এই বিভাগে আমরা দেখব অ্যাসিমেট্রিক হ্যাশিং কৌশল কী। এই কৌশলে, হ্যাশ টেবিলটিকে d সংখ্যক ব্লকে বিভক্ত করা হয়। প্রতিটি বিভাজনের দৈর্ঘ্য n/d। প্রোবের মান xi, 0 ≤ i ≤ d, $$\lbrace\frac{i*n}{d},...,\frac{(i+1)*n}{d-1} থেকে অভিন্নভাবে আঁকা হয়েছে \rbrace$$। মাল্টিপল চয়েস হ্যাশিংয়ের মতো, x সন্নিবেশ করার জন্য, অ্যালগরিদম A[x0 তালিকার দৈর্ঘ্য পরীক্ষা করে। ], A[x1 ], . ., A[xd – 1 ]। তারপর এই তালিকার সংক্ষিপ্ততম সাথে x যুক্ত করে। যদি একটি টাই থাকে, তাহলে এটি ক্ষুদ্রতম সূচক সহ তালিকায় x সন্নিবেশিত করে।

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

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

ফাংশন 𝜙𝑑 সোনালী অনুপাতের একটি সাধারণীকরণ, তাই $$\phi_{2}=\frac{(1+\sqrt{5})}{2}$$


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

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

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

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