10 탐색(Search)

1. 해싱(Hashing)

1.1. Definition

• Hashing
  • 임의의 크기를 가진 데이터를 고정된 크기의 해시값으로 변환하는 기술
  • 해시 함수를 사용하여 입력 데이터를 계산하고, 결과값을 해시 테이블에 저장하거나 조회한다.

1.2. Features

• Features

  • 장점: 빠른 탐색 속도 (평균 $O(1)$, 최악 $O(n)$)
  • 단점: 정렬 불가, 공간 낭비 가능성과 충돌(Collision) 문제

• Time Complexity

  • Best: $O(1)$
  • Average: $O(1)$
  • Worst: $O(n)$ (모든 키에 같은 해시 주소 매핑)

1.3. Applications

• Applications
  • 데이터 검색, 암호화, 데이터 무결성, 부하 분산, 캐싱, 블록체인
  • 암호학적 해시는 충돌과 역추적이 불가능하고 입력 변화에 민감한 것이 핵심이다.

2. 구조

• 구조: 키 → [해시 함수] → 해시 주소 → [해시 테이블](버킷×슬롯)

2.1. 해시 함수

• 좋은 해시 함수: 빠른 계산, 적은 충돌, 고르게 분포
• 종류: 제산(나누기→소수) 함수, 폴딩 함수, 중간 제곱 함수, 비트 추출 방법, 숫자 분석 방법

2.2. 충돌(Collision) 처리

• 충돌(collision)/동의어(synonym): 서로 다른 키가 같은 주소로 계산되는 상황
• 오버플로(overflow): 충돌이 슬롯 공간을 초과하는 상황

(1) 개방 주소법

• 개방 주소법(open addressing): 선형 조사, 이차 조사, 이중 해싱

  • 선형 조사(linear probing): h(k), h(k)+1, …

• + 클러스터링 완화

  • 이차 조사(quadratic probing): h(k)+1², +2²,…
  • 이중 해싱(double hashing): 두 번째 해시 함수 이용

(2) 체이닝(Chaining)

• 체이닝(Chaining)
  • 동일 해시 주소에 여러 데이터를 연결 리스트로 저장