Với mọi hàm băm, nếu kích thước bảng m nhỏ hơn rất nhiều so với kích thước vũ trụ u, thì tồn tại tập con lớn của U có cùng giá trị băm.
Để giải quyết, cần tập hợp các hàm băm, chọn một hàm phù hợp với S. Nếu hầu hết hàm băm đều tốt cho S, chọn ngẫu nhiên.
Giả sử ℌ là tập hợp hàm băm. ℌ gọi là universal nếu ∀x,y∈U, số h∈ℌ sao cho h(x)=h(y) ≤ |ℌ|/m. Tức là với h chọn ngẫu nhiên từ ℌ, xác suất va chạm giữa x≠y không quá 1/m (giống như h(x),h(y) độc lập ngẫu nhiên trong {0,…,m-1}).
Nếu lưu S trong bảng băm dùng h, thời gian tìm/xóa kỳ vọng là O(1 + α).