Đối với bất kỳ hàm băm nào, chúng ta có thể nói rằng nếu kích thước bảng m nhỏ hơn nhiều so với kích thước vũ trụ u, thì đối với bất kỳ hàm băm nào, có một tập con lớn của U có cùng kích thước giá trị băm.
Để giải quyết vấn đề này, chúng ta cần một tập hợp các hàm băm, từ đó chúng ta có thể chọn bất kỳ hàm nào hoạt động tốt cho S. Nếu hầu hết các hàm băm tốt hơn cho S, chúng ta có thể chọn hàm băm ngẫu nhiên
Giả sử ℌ là một tập các hàm băm. Chúng ta có thể nói ℌ là phổ biến nếu, với mỗi x, y ∈ U, số h ∈ ℌ, sao cho h (x) =h (y) nhiều nhất là | ℌ | / 𝑚. Nói cách khác, chúng ta có thể nói rằng với một hàm băm h, được chọn ngẫu nhiên từ ℌ, cơ hội xảy ra va chạm giữa các khóa khác nhau x và y, không nhiều hơn cơ hội 1 / m. của một va chạm nếu h (x) =h (y), được chọn ngẫu nhiên và độc lập từ tập {0, 1 ,. . ., m - 1}.
Nếu chúng ta lưu trữ S trong bảng băm bằng cách sử dụng hàm băm h, thì thời gian dự kiến để tìm kiếm và xóa là O (1 + α).