ปัญหาของ Hash Function เดียว
สำหรับ Hash Function ใดๆ หากขนาดตาราง m น้อยกว่า Universe Size u มาก จะมี Subset ใหญ่ของ U ที่มี Hash Value เหมือนกัน
แนวทางแก้: Universal Hashing
ใช้เซตของ Hash Functions (ℌ) เลือกตัวที่ทำงานดีกับ S หากฟังก์ชันส่วนใหญ่ดีกับ S สามารถสุ่มเลือกได้
ℌ เป็น Universal ถ้า: สำหรับ x,y ∈ U จำนวน h ∈ ℌ ที่ h(x)=h(y) ≤ |ℌ|/m กล่าวคือ โอกาสชนกันระหว่าง x,y ที่แตกต่างกัน ≤ 1/m (เท่ากับการสุ่มอิสระ)
ประสิทธิภาพ
หากจัดเก็บ S ใน Hash Table ด้วย h ที่สุ่มจาก ℌ เวลาคาดหมายในการ Search และ Delete คือ O(1 + α)
