> For the complete documentation index, see [llms.txt](https://byulseop-til.gitbook.io/sinheeseop_til/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://byulseop-til.gitbook.io/sinheeseop_til/cs-computer-science/algorithm/hash/openaddressing.md).

# OpenAddressing

**개방 주소법**은 해시 충돌(Collision)이 발생했을 때, 해시 테이블의 **남은 공간(Open Address)** 을 찾아서 데이터를 저장하는 방식이다.

체이닝(Chaining)이 충돌 난 자리에 아파트를 쌓아 올리는(LinkedList) 방식이라면, 개방 주소법은 **"내 자리가 찼네? 그럼 옆 빈자리에 대야지"** 라고 하는 **주차장** 과 비슷하다.

## 핵심 의문: "다른 곳에 넣었는데 어떻게 다시 찾나?"

개방 주소법의 가장 큰 의문점은 이것이다.

> *"원래 1번 방에 넣어야 하는데 꽉 차서 3번 방에 넣었다. 나중에 1번 방으로 찾으러 가면 없지 않나?"*

이 문제를 해결하는 대원칙은 다음과 같다.

> **"저장할 때 걸어갔던 길을, 찾을 때 똑같이 걸어간다."**

즉, 데이터를 넣을 때 `1번 확인(X) -> 2번 확인(X) -> 3번 저장(O)` 했다면, 데이터를 찾을 때도 `1번 확인(아니네?) -> 2번 확인(아니네?) -> 3번 확인(찾았다!)` 순서로 탐색한다.

## 1. 탐색(Probing) 전략 3가지

빈자리를 찾는 규칙(보폭)에 따라 종류가 나뉜다.

### ① 선형 탐사 (Linear Probing)

* **규칙**: 충돌 시 **바로 옆 칸(+1)** 을 확인한다. 안 되면 그 옆(+2), 그 옆(+3)...
* **장점**: 단순하고 CPU 캐시 효율(Cache Hit)이 가장 좋다. (데이터가 붙어있으니까)
* **단점**: **군집화(Clustering)**. 한 번 충돌이 나면 그 주변에 데이터가 떡 뭉쳐서, 나중에 빈자리 찾기가 점점 힘들어진다.

### ② 제곱 탐사 (Quadratic Probing)

* **규칙**: 보폭을 제곱수(`1^2, 2^2, 3^2...`)로 넓힌다. (+1, +4, +9...)
* **목적**: 선형 탐사의 '데이터 뭉침 현상'을 줄이기 위해 멀리멀리 점프한다.

### ③ 이중 해싱 (Double Hashing)

* **규칙**: 해시 함수를 2개 쓴다.
  * `Hash1`: 원래 가야 할 인덱스
  * `Hash2`: 충돌 났을 때 점프할 보폭
* **특징**: 보폭 자체가 불규칙하게 바뀌므로 데이터가 골고루 퍼진다.

## 2. 동작 프로세스 (저장, 검색, 삭제)

가장 흔한 **선형 탐사(Linear Probing)** 를 기준으로 설명한다. (해시 함수 결과: `Apple` -> 1번 인덱스라고 가정)

### \[상황 1] 저장 (Insert)

1. `Apple`을 넣으려는데 1번이 차 있다. (충돌!)
2. 옆 칸(2번)을 본다. 차 있다.
3. 옆 칸(3번)을 본다. 비어 있다.
4. **3번에 저장.**

### \[상황 2] 검색 (Search)

1. `Apple`을 찾으러 1번에 갔다. (다른 값이 있다. 충돌 상황임을 인지)
2. "아, 딴 데 뒀나 보네" 하고 옆 칸(2번)을 본다. (다른 값이 있다)
3. 옆 칸(3번)을 본다. `Apple`이 있다! **검색 성공.**

> **Q. 만약 3번도 아니고 4번도 비어있다면?** 탐색하다가 **빈방(Null)** 을 만나면 "아, 이 데이터는 없구나"라고 판단하고 탐색을 종료한다.

### \[상황 3] 삭제의 문제점 (Delete & Tombstone)

이게 제일 골치 아프다. **중간에 있는 데이터를 삭제하면 탐색 경로가 끊긴다.**

* **문제 상황**: 2번 인덱스의 데이터를 삭제해서 `Null`로 만들었다고 치자.
* **이후 `Apple`(3번) 검색 시**:
  1. 1번 확인 (아님) -> 다음
  2. 2번 확인 (**Null이네?**)
  3. **"어? 빈방이네? 그럼 Apple은 없나 보다"** 하고 3번을 보지도 않고 검색 종료. (검색 실패)
* **해결책: 묘비(Tombstone) 세우기**
  * 2번을 삭제할 때 진짜 비우지 않고 \*\*"삭제됨(Deleted)"\*\*이라는 팻말을 꽂는다.
  * **검색 시**: "삭제됨" 팻말을 보면 "여기 원래 뭐 있었으니 멈추지 말고 계속 가보자" 하고 넘어간다.
  * **저장 시**: "삭제됨" 팻말을 보면 "어차피 지운 거니 여기 덮어쓰자" 하고 데이터를 넣는다.

## 3. 요약 비교

| 구분        | 체이닝 (Chaining)      | 개방 주소법 (Open Addressing)   |
| --------- | ------------------- | -------------------------- |
| **충돌 처리** | 연결 리스트에 추가 (아파트 쌓기) | 빈자리 찾아 삼만리 (주차장 돌기)        |
| **메모리**   | 추가 포인터 필요 (Link)    | 추가 메모리 없음 (배열 내 해결)        |
| **속도**    | 충돌 많으면 느려짐 (리스트 탐색) | 데이터 뭉치면 느려짐 (탐색 길어짐)       |
| **삭제**    | 쉬움 (노드 삭제)          | **어려움 (Tombstone 관리 필요)**  |
| **대표 언어** | **Java** (안정성 중시)   | **Python, C++** (캐시 효율 중시) |