যেকোন হ্যাশ ফাংশনের জন্য আমরা বলতে পারি যে টেবিলের আকার m যদি ইউনিভার্স সাইজ u থেকে অনেক ছোট হয়, তবে যে কোনো হ্যাশ ফাংশনের জন্য, সেখানে U-এর কিছু বড় উপসেট আছে যা একই রকম হ্যাশ মান।
এই সমস্যা থেকে পরিত্রাণ পেতে, আমাদের হ্যাশ ফাংশনগুলির একটি সেট প্রয়োজন, যেখান থেকে আমরা S-এর জন্য ভাল কাজ করে এমন যেকোনো একটি বেছে নিতে পারি৷ যদি বেশিরভাগ হ্যাশ ফাংশন S-এর জন্য ভাল হয়, আমরা র্যান্ডম হ্যাশ ফাংশন বেছে নিতে পারি
ধরুন ℌ হ্যাশ ফাংশনের একটি সেট। আমরা বলতে পারি ℌ সর্বজনীন যদি, প্রতিটি x, y ∈ U, h ∈ ℌ এর সংখ্যা, যেমন h(x) =h(y) সর্বাধিক |ℌ|/𝑚 হয়। অন্য কথায় আমরা বলতে পারি যে হ্যাশ ফাংশন h দিয়ে, যা এলোমেলোভাবে ℌ থেকে বেছে নেওয়া হয়েছে, স্বতন্ত্র কী x এবং y-এর মধ্যে সংঘর্ষের সম্ভাবনা 1/m এর চেয়ে বেশি নয়। একটি সংঘর্ষের যদি h(x) =h(y), সেট থেকে এলোমেলোভাবে এবং স্বাধীনভাবে বেছে নেওয়া হয় {0, 1, . . ., মি – 1}।
যদি আমরা হ্যাশ ফাংশন h ব্যবহার করে একটি হ্যাশ টেবিলে S সংরক্ষণ করি, তাহলে অনুসন্ধান এবং মুছে ফেলার জন্য প্রত্যাশিত সময় হল O(1 + α)।
