db hash collision

---

1. 버킷(Bucket)이란?

• 해시 테이블에서 해시 함수로 계산된 값을 저장하는 저장소 단위입니다.
• 각 버킷은 하나의 키-값 쌍을 저장할 수도 있고, **여러 개의 데이터를 저장하는 공간(리스트, 포인터 등)**이 될 수도 있습니다.
• 예를 들어, 해시(key) % N = 3이면 3번 버킷에 저장.

---

2. 충돌(Collision)이란?

• 서로 다른 두 키가 같은 해시값을 가질 때 발생하는 현상입니다.

  • 예: hash("apple") % 5 = 2, hash("grape") % 5 = 2 → 둘 다 버킷 2에 저장되려 함

---

3. 충돌 처리 방식

충돌이 일어났을 때 데이터를 어떻게 저장할지에 따라 다음 두 가지 대표적인 방식이 있습니다:

(1) 체이닝(Chaining)

• 각 버킷이 연결 리스트나 배열을 가짐

• 충돌된 데이터는 해당 버킷의 리스트에 "체인처럼 연결"

  예시:

  버킷 2: [apple] -> [grape] -> [banana]

• 장점:

  • 구현이 간단
  • 테이블이 꽉 차도 삽입 가능

• 단점:

  • 포인터 관리 비용
  • 메모리 지역성이 떨어짐 → 성능 저하 가능

---

(2) 오픈 어드레싱(Open Addressing)

• 버킷에 빈 공간이 없으면 다른 빈 버킷을 찾아가 저장

• 대표적인 방식: 선형 탐사(Linear Probing), 이차 탐사(Quadratic), 더블 해싱(Double Hashing)

  예시 (선형 탐사):

  hash("apple") % 5 = 2 → 버킷 2 비어있으면 apple 저장
  hash("grape") % 5 = 2 → 버킷 2 차있음 → 버킷 3 확인 → 저장

• 장점:

  • 메모리 사용 효율이 좋음 (버킷 외 구조 없음)
  • 캐시 친화적

• 단점:

  • 삭제 어려움
  • 충돌 많으면 성능 급감 (클러스터링 현상)

---

요약 표:

구분	체이닝(Chaining)	오픈 어드레싱(Open Addressing)
구조	각 버킷이 리스트 가짐	모든 항목을 해시 테이블 내에 저장
충돌 시	같은 버킷에 연결	빈 버킷 찾아 이동
삭제	간단함	복잡함 (마커 필요)
메모리	외부 구조 필요	메모리 효율적
성능	포인터 탐색 → 느릴 수 있음	캐시 친화적이나 충돌 시 급격히 저하

---