ডেটা স্ট্রাকচরে ডাবল হ্যাশিং

এই বিভাগে আমরা ওপেন অ্যাড্রেসিং স্কিমে ডাবল হ্যাশিং কৌশল দেখব। একটি সাধারণ হ্যাশ ফাংশন h'(x) : U → {0, 1, …, m-1}। ওপেন অ্যাড্রেসিং স্কিমে, প্রকৃত হ্যাশ ফাংশন h(x) সাধারণ হ্যাশ ফাংশন h'(x) নেয় যখন স্থান খালি থাকে, অন্যথায় অন্য একটি হ্যাশ ফাংশন করেই খালি জায়গা পাওয়ার চেষ্টা করে।

$$h_{1}(x)=x\:mod\:m$$

$$h_{2}(x)=x\:mod\:m'$$

$$h(x,i)=(h^{1}(x)+ih^{2})\:mod\:m$$

i-এর মান = 0, 1, …, m-1। সুতরাং আমরা i = 0 থেকে শুরু করি এবং ফ্রি স্পেস পাওয়া পর্যন্ত বাড়াতে থাকি। সূচনায় i = 0 হলে, h(x, i) হল h'(x)-এর সমান।

উদাহরণ

ধরি আমাদের 20 আকারের একটি লিস্ট আছে (m = 20)। আমরা কিছু উপাদান লিনিয়ার প্রোবিং ফ্যাশনে রাখতে চাই। উপাদানগুলো হল {96, 48, 63, 29, 87, 77, 48, 65, 69, 94, 61}

$$h_{1}(x)=x\:mod\:20$$

$$h_{2}(x)=x\:mod\:13$$

x h(x, i) = (h1 (x) + ih2(x)) mod 20

হ্যাশ টেবিল