모든 해시 함수에 대해 테이블 크기 m이 유니버스 크기 u보다 훨씬 작으면 해시 함수 h에 대해 동일한 값을 갖는 U의 일부 큰 하위 집합이 있다고 말할 수 있습니다. 해시 값.
이 문제를 없애기 위해 우리는 해시 함수 세트가 필요합니다. 여기서 S에 대해 잘 작동하는 것을 선택할 수 있습니다. 대부분의 해시 함수가 S에 더 좋다면 임의의 해시 함수를 선택할 수 있습니다.
ℌ가 해시 함수의 집합이라고 가정합니다. 각 x, y ∈ U에 대해 h(x) =h(y)가 최대 |ℌ|/𝑚인 경우 h ∈ ℌ의 수가 ℌ이라고 할 수 있습니다. 다시 말해서 ℌ에서 무작위로 선택된 해시 함수 h를 사용하면 고유한 키 x와 y 사이의 충돌 확률이 확률 1/m보다 크지 않다고 말할 수 있습니다. 충돌의 h(x) =h(y)인 경우 집합 {0, 1, . . ., m – 1}.
해시 함수 h를 사용하여 해시 테이블에 S를 저장하면 검색 및 삭제 예상 시간은 O(1 + α)입니다.