किसी भी हैश फ़ंक्शन के लिए हम कह सकते हैं कि यदि टेबल आकार m, यूनिवर्स आकार u से बहुत छोटा है, तो किसी भी हैश फ़ंक्शन h के लिए, U का कुछ बड़ा उपसमुच्चय होता है जिसका हैश मान समान होता है।
इस समस्या से छुटकारा पाने के लिए, हमें हैश फ़ंक्शन का एक समुच्चय चाहिए, जिसमें से हम कोई भी एक चुन सकें जो S के लिए अच्छा काम करे। यदि अधिकांश हैश फ़ंक्शन S के लिए बेहतर हैं, तो हम यादृच्छिक हैश फ़ंक्शन चुन सकते हैं।
मान लीजिए ℌ हैश फ़ंक्शन का एक समुच्चय है। हम कह सकते हैं कि ℌ सार्वभौमिक (universal) है यदि, प्रत्येक x, y ∈ U के लिए, h ∈ ℌ की संख्या, जैसे कि h(x) = h(y), अधिकतम |ℌ|/m है। दूसरे शब्दों में हम कह सकते हैं कि एक हैश फ़ंक्शन h के साथ, जिसे ℌ से यादृच्छिक रूप से चुना गया है, अलग-अलग कुंजियों x और y के बीच टकराव की संभावना, 1/m में टकराव की संभावना से अधिक नहीं है, यदि h(x) = h(y), को सेट {0, 1, …, m – 1} से यादृच्छिक और स्वतंत्र रूप से चुना गया हो।
यदि हम हैश फ़ंक्शन h का उपयोग करके हैश टेबल में S संग्रहीत करते हैं, तो खोज और हटाने के लिए अपेक्षित समय O(1 + α) है।
