---
title: "해시 충돌 해결: 같은 위치를 원하는 키들을 다루는 법"
author: "Lee"
published_at: "2026-10-11T02:25:04.904Z"
updated_at: "2026-09-30T09:27:56.263Z"
tags: ["컴퓨터공학","자료구조"]
canonical_url: "https://ariser.io/@writer_a1cd615ab19e/%ED%95%B4%EC%8B%9C-%EC%B6%A9%EB%8F%8C-%ED%95%B4%EA%B2%B0-%EA%B0%99%EC%9D%80-%EC%9C%84%EC%B9%98%EB%A5%BC-%EC%9B%90%ED%95%98%EB%8A%94-%ED%82%A4%EB%93%A4%EC%9D%84-%EB%8B%A4%EB%A3%A8%EB%8A%94-%EB%B2%95"
ai_assisted: false
---

# 해시 충돌 해결: 같은 위치를 원하는 키들을 다루는 법

[원문](https://ariser.io/@writer_a1cd615ab19e/%ED%95%B4%EC%8B%9C-%EC%B6%A9%EB%8F%8C-%ED%95%B4%EA%B2%B0-%EA%B0%99%EC%9D%80-%EC%9C%84%EC%B9%98%EB%A5%BC-%EC%9B%90%ED%95%98%EB%8A%94-%ED%82%A4%EB%93%A4%EC%9D%84-%EB%8B%A4%EB%A3%A8%EB%8A%94-%EB%B2%95)

해시 충돌은 서로 다른 키가 같은 해시값 또는 같은 버킷 인덱스를 얻는 현상이다. 유한한 저장 위치에 더 많은 키를 배치하면 충돌은 불가피하다. 좋은 자료구조는 충돌을 없다고 가정하지 않고, 발생해도 키를 찾을 수 있는 규칙을 정한다.

![같은 버킷으로 해시된 A와 B를 체이닝 또는 선형 탐사로 저장하는 비교](/api/v1/media/befc0db8-1f9f-400d-9533-99d9543c18bd)

*충돌한 항목을 별도 연결 구조에 두거나 다른 빈 슬롯을 탐색한다.*

### 체이닝과 개방 주소법

체이닝은 각 버킷에 목록이나 별도 구조를 둔다. 같은 버킷으로 온 키는 그 안에서 실제 키를 비교한다. 버킷 수보다 항목 수가 많아도 저장할 수 있지만 노드 할당과 참조 이동 비용이 발생한다.

개방 주소법은 항목을 테이블 배열 안에 저장한다. 처음 위치가 차 있으면 탐사 순서에 따라 다른 위치를 살핀다. 선형 탐사는 h, h+1, h+2,…를 모듈러 연산으로 방문한다. 이차 탐사나 이중 해싱은 더 다른 이동 규칙을 쓴다. 삽입과 조회가 같은 탐사열을 따라야 한다.

크기 7 테이블에서 키 A와 B가 모두 2번으로 가면 A를 2에, B를 3에 둘 수 있다. B를 조회할 때 2의 키가 다르므로 3까지 계속한다. 한 버킷만 확인하면 이미 저장된 B가 없다고 잘못 판단한다.

### 삭제가 빈칸만 만들면 안 되는 이유

A를 지운 자리를 완전히 빈 상태로 바꾸면 B의 검색은 2에서 멈출 수 있다. 과거에 사용했지만 현재 삭제되었다는 표식인 tombstone을 두어 탐사를 계속하게 한다. 아래 코드는 이 구별의 의미만 드러낸다.

```python
def find_slot(table, key, initial_index):
    capacity = len(table)
    for distance in range(capacity):
        index = (initial_index + distance) % capacity
        entry = table[index]
        if entry is NEVER_USED:
            return None
        if entry is DELETED:
            continue
        if entry.key == key:
            return index
    return None
```

NEVER_USED와 DELETED는 서로 다른 특별한 표식이다. tombstone이 누적되면 비어 보여도 탐사 거리가 길어질 수 있으므로 다시 배치할 필요가 있다. 삭제 항목을 다루는 다른 방식도 있지만 탐사 경로의 의미를 유지해야 한다.

선형 탐사는 연속 메모리를 읽어 캐시에 유리한 반면 긴 덩어리가 생기는 일차 클러스터링이 발생한다. 개방 주소법은 적재율이 1에 가까워질수록 빈칸 찾기가 급격히 어려워진다. 이차 탐사도 테이블 크기와 이동 규칙이 잘못 맞으면 모든 칸을 방문하지 못한다.

충돌 처리와 좋은 해시 함수는 서로 보완한다. 충돌 해결이 있어도 한쪽으로 몰리는 함수는 느리고, 좋은 함수여도 올바른 삭제·조회 규칙이 없으면 틀린다. 평균 O(1)은 분포와 적재율 조건을 포함한 성능 주장이라는 점까지 함께 이해해야 한다.

탐사 중 모든 칸을 확인했을 때 종료하는 상한도 필요하다. 빈칸이 있다는 보장 없이 끝없이 순환하면 가득 찬 테이블의 검색과 삽입이 멈추지 않는다.

### 참고 자료

- [MIT OpenCourseWare · Introduction to Algorithms](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/)
- [Princeton · Algorithms, 4th edition · Hash Tables](https://algs4.cs.princeton.edu/34hash/)