해시 테이블에서 다른 키가 같은 버킷에 들어오면 어떻게 구분하나요?

해시값이 같다는 것은 같은 키라는 뜻이 아니라 같은 후보 위치를 얻었다는 뜻입니다. 해시 테이블은 버킷을 찾은 뒤 실제 키를 동등 비교해 원하는 항목인지 확인해야 합니다. 충돌 처리에는 버킷마다 여러 항목을 보관하는 체이닝과, 테이블 안에서 다른 위치를 계속 탐사하는 개방 주소법이 있으며, 부하율·삭제 빈도·메모리 지역성에 따라 선택하겠습니다.

충돌·삭제·부하율을 관리합니다

서로 다른 두 키가 같은 해시나 같은 버킷 인덱스를 가질 수 있습니다. 체이닝에서는 해당 버킷의 연결 구조나 배열을 순회하면서 키를 비교합니다. 개방 주소법에서는 선형·제곱·이중 해싱 등 정해진 탐사 순서로 빈 칸 또는 같은 키를 찾습니다. 따라서 해시 함수와 동등 비교는 같은 키라면 같은 해시를 내놓는 계약을 지켜야 하고, 해시만 비교해 값을 반환하면 충돌한 키가 덮어써집니다. 이처럼 해시를 빠른 후보 필터로만 사용하는 원칙을 동등성 검증(equality verification)이라고 설명할 수 있습니다.

개방 주소법의 삭제는 특히 조심해야 합니다. 중간 슬롯을 진짜 미사용 상태로 바꾸면 검색이 그 지점에서 멈춰 뒤쪽에 저장된 키를 찾지 못할 수 있습니다. 삭제 표시를 남겨 탐사 경로를 이어 가거나, 뒤 원소를 재배치하거나, 주기적으로 재구성해야 합니다. 삭제 표시가 많아지면 빈 칸이 있어도 탐사 길이가 늘어나므로 확장 또는 재해시 조건에 포함하겠습니다.

평균 비용의 전제를 측정합니다

체이닝은 부하가 높아질 때 버킷 내부 길이가 길어지고, 개방 주소법은 클러스터가 생기면 연속 슬롯을 많이 읽게 됩니다. 낮은 부하율과 좋은 해시 분포에서 평균 O(1)에 가까울 수 있지만 최악에는 모든 키가 한곳에 몰려 선형 탐색이 됩니다. 공개 입력으로 해시 충돌을 유도할 수 있는 서비스라면 무작위 시드, 해시 함수 선택, 요청 크기 제한을 검토하겠습니다.

테스트는 의도적인 충돌, 동일 키 갱신, 삭제 후 재검색, 빈·가득 찬 경계, 가변 키 수정을 포함합니다. 특히 테이블에 넣은 뒤 키 객체의 필드를 바꿔 해시 위치가 달라지면 항목이 남아 있어도 찾지 못할 수 있으므로 키는 불변으로 두거나 변경 시 삭제 후 재삽입해야 합니다. 비교 횟수·메모리 지역성·최대 탐사 길이를 관찰해 구현을 판단하겠습니다.

해시 테이블의 불변식은 해시가 후보 위치를 정하고 실제 키 비교가 동일성을 확정한다는 것입니다. 체이닝은 버킷 내부 목록이 길어질수록 비교와 포인터 추적이 늘고, 개방 주소법은 부하율이 높아질수록 빈 슬롯을 찾는 탐사와 클러스터링 비용이 커집니다. 개방 주소법의 중간 삭제 슬롯을 빈 칸으로 만들면 뒤에 있는 키를 찾기 전에 탐색이 멈추므로 tombstone이나 재배치가 필요합니다.

동일 키 갱신과 다른 키 충돌을 구분하고, 키 객체의 필드를 테이블에 넣은 뒤 바꾸면 해시 위치와 동등 비교가 달라져 항목을 잃은 것처럼 보일 수 있으므로 불변 키를 우선하겠습니다. 의도적인 충돌·삭제 후 재검색·높은 부하율을 시험하고, 체이닝의 할당 비용과 개방 주소법의 메모리 지역성·최대 탐사 길이를 함께 비교합니다.

삭제와 수명까지 충돌 정책에 포함합니다

개방 주소법의 tombstone은 검색을 끝내는 미사용 슬롯과 다르지만 삽입 시 재사용할 수 있습니다. 다만 같은 키가 뒤에 있는지 탐사를 계속해야 중복 삽입을 피할 수 있고, 표시가 많으면 검색 비용이 늘어납니다. 체이닝은 삭제 노드를 바로 반환할 수 있어도 조회 중인 스레드가 그 노드를 참조한다면 수명을 보호해야 합니다. 충돌 키·동일 키·삭제 키를 섞은 연산열에서 반환값과 항목 수를 기준 구현과 비교하고, 최대 탐사 길이와 버킷 길이를 함께 기록하겠습니다.

개방 주소법에서는 실제 원소 수/용량인 부하율과, 원소·tombstone을 합친 탐사상 점유율을 나눠 봅니다. 삭제가 많으면 원소 수가 적어도 탐색은 길어질 수 있습니다. 체이닝에서는 평균 버킷 길이와 최장 버킷 길이를 구분하겠습니다. 하나의 비율로 두 구현의 상태를 같게 판단하지 않습니다.