여기서 정수 키가 있는 해시 테이블에 대해 설명합니다. 여기서 키 값 𝑥은 𝑈 ={0, 1, … , 𝑢 – 2, 𝑢 – 1}과 같은 우주 𝑈에서 가져옵니다. 해시 함수는 ℎ입니다. 이 해시 함수의 도메인은 𝑈입니다. 범위는 {0, 1, … , 𝑚 – 1} 및 𝑚 ≤ 𝑢 세트에 있습니다.
해시 함수 h는 모든 𝑥 ∈ 𝑆에 대해 ℎ(𝑥)가 고유한 경우 집합 𝑆 ⊆ 𝑈에 대한 완벽한 해시 함수라고 합니다. 𝑚 =|𝑆|인 경우 𝑆에 대한 완벽한 해시 함수 ℎ는 최소입니다. 따라서 ℎ는 S와 {0, 1, … , 𝑚 – 1} 사이의 전단사입니다. 분명히 최소의 완벽한 해시 함수는 길이가 n인 단일 배열에 S의 모든 요소를 저장할 수 있기 때문에 바람직합니다.
불행히도 m이 n보다 훨씬 크더라도 완벽한 해시 함수는 매우 드뭅니다. S의 각 요소가 {0, 1, … , 𝑚 – 1}의 임의 요소에 균일하고 독립적으로 매핑되는 경우 m이 n 2 보다 훨씬 작은 경우 생일 역설에 따라 그러면 해시 값이 동일한 S의 두 요소가 거의 확실하게 존재할 것입니다.