স্ট্যাটিক পারফেক্ট হ্যাশিং

পারফেক্ট হ্যাশিং এর সংজ্ঞা

নিখুঁত হ্যাশিংকে হ্যাশিংয়ের একটি মডেল হিসাবে সংজ্ঞায়িত করা হয় যেখানে n উপাদানগুলির যেকোন সেট সমান আকারের একটি হ্যাশ টেবিলে সংরক্ষণ করা যেতে পারে এবং ধ্রুবক সময়ে সঞ্চালিত লুকআপ থাকতে পারে। এটি বিশেষভাবে ফ্রেডম্যান, কমলোস এবং সেমেরেডি (1984) দ্বারা উদ্ভাবিত এবং আলোচিত হয়েছিল এবং তাই "এফকেএস হ্যাশিং" নামে ডাকনাম করা হয়েছে৷

স্ট্যাটিক হ্যাশিং এর সংজ্ঞা

স্ট্যাটিক হ্যাশিং হ্যাশিং সমস্যার আরেকটি রূপকে সংজ্ঞায়িত করে যা ব্যবহারকারীদের একটি চূড়ান্ত অভিধান সেটে লুকআপ সম্পন্ন করার অনুমতি দেয় (যার মানে অভিধানের সমস্ত বস্তু চূড়ান্ত এবং পরিবর্তন হয় না)।

আবেদন

যেহেতু স্ট্যাটিক হ্যাশিং এর জন্য ডাটাবেস, এর অবজেক্ট এবং রেফারেন্স একই থাকে তার অ্যাপ্লিকেশন সীমিত। যে ডেটাবেসগুলিতে তথ্য রয়েছে যা বিরল পরিবর্তন অনুভব করে সেগুলিও যোগ্য কারণ এটি শুধুমাত্র বিরল অনুষ্ঠানে পুরো ডাটাবেসের সম্পূর্ণ রিহ্যাশের প্রয়োজন হবে। এই হ্যাশিং স্কিমের বিভিন্ন উদাহরণের মধ্যে রয়েছে নির্দিষ্ট ভাষার শব্দের সেট এবং সংজ্ঞা, একটি প্রতিষ্ঠানের কর্মীদের জন্য উল্লেখযোগ্য ডেটার সেট ইত্যাদি।

বাস্তবায়ন

স্ট্যাটিক ক্ষেত্রে, আমাদের মোট p এন্ট্রি সহ একটি সেট প্রদান করা হয়, প্রতিটি একটি অনন্য কী এর সাথে যুক্ত, সময়ের আগে। Fredman, Komlós এবং Szemerédi s =2(p-1) বালতি সহ একটি প্রথম-স্তরের হ্যাশ টেবিল নির্বাচন করুন৷ নির্মাণের জন্য, p এন্ট্রিগুলিকে টপ-লেভেল হ্যাশিং ফাংশন দ্বারা q বালতিতে আলাদা করা হয়, যেখানে q =2(p-1)। তারপর r এন্ট্রি সহ প্রতিটি বালতির জন্য, r2 স্লট সহ একটি দ্বিতীয়-স্তরের টেবিল বরাদ্দ করা হয়, এবং এর হ্যাশ ফাংশনটি একটি সর্বজনীন হ্যাশ ফাংশন সেট থেকে এলোমেলোভাবে বেছে নেওয়া হয় যাতে এটি সংঘর্ষ-মুক্ত হয় এবং হ্যাশ টেবিলের সাথে সংরক্ষিত হয়। যদি এলোমেলোভাবে নির্বাচিত হ্যাশ ফাংশন সংঘর্ষের সাথে একটি টেবিল তৈরি করে, একটি সংঘর্ষ-মুক্ত টেবিলের নিশ্চয়তা না দেওয়া পর্যন্ত একটি নতুন হ্যাশ ফাংশন এলোমেলোভাবে বেছে নেওয়া হয়। শেষ পর্যন্ত, সংঘর্ষ-মুক্ত হ্যাশের সাথে, আর এন্ট্রিগুলি দ্বিতীয়-স্তরের টেবিলে হ্যাশ করা হয়৷