같은 번호와 같은 자료
가상의 간단한 함수가 정수를 8로 나눈 나머지를 해시로 쓴다면 10과 18은 모두 2를 얻는다. 두 정수는 다르지만 해시값은 같다. 이것이 충돌의 기본 모습이다. 실제 해시 함수는 더 복잡해도 제한된 출력 범위에 많은 입력을 대응시키면 충돌 가능성을 고려해야 한다.
자료구조가 추가로 하는 일
해시값은 후보를 찾는 데 사용할 수 있지만 해당 후보가 정말 같은 키인지는 동등성 규칙으로 확인할 수 있어야 한다. 같은 해시를 얻었다는 이유로 모든 항목을 하나로 합치면 다른 자료를 잃는다. 충돌을 저장하고 구분하는 방법은 구현에 따라 다르다. 해시 함수의 역할과 자료구조의 충돌 처리 역할을 나누어 이해한다.
동등한 키의 계약
Python처럼 사용자 정의 객체의 해시와 동등성에 규칙을 두는 환경에서는 동등하다고 판단한 키가 같은 해시를 갖도록 맞춰야 한다. 반대 방향인 같은 해시면 반드시 동등해야 한다는 조건은 아니다. 대소문자를 무시하는 동등성을 만들면서 해시에는 대소문자를 그대로 반영하는 식의 불일치를 주의한다. 두 규칙이 같은 의미를 표현해야 한다.
키가 바뀌는 문제
해시 기반 자료구조에 넣은 뒤 동등성이나 해시에 영향을 주는 값을 바꾸면 이후 조회가 기대대로 되지 않을 수 있다. 삽입 당시의 배치와 나중의 탐색 기준이 달라지기 때문이다. 키로 사용할 값의 수명을 정하고 변경 가능성을 검토한다. 객체의 모든 변경이 문제인 것은 아니며 키 판정에 관여하는 부분이 중요하다.
용도별 보장 구분
일반 자료구조의 해시와 암호학적 해시는 요구가 다르다. 조회를 빠르게 하는 데 적절한 함수라는 사실만으로 위변조 판정이나 공격 저항성까지 보장되지 않는다. 반대로 해시가 같다고 원본까지 확실히 같다고 취급하면 충돌을 배제한 가정을 하게 된다. 필요한 확실성에 맞게 원본 비교와 다른 검증 절차를 선택한다.