해시
1. 해싱(Hashing)의 개념 및 필요성
해싱은 검색, 추가, 삭제를 효율적으로 수행할 수 있는 데이터 저장 및 관리 방법입니다.
기존 정렬 배열의 O(n) 복잡도를 해결하기 위해 등장했습니다.
| 용어 | 설명 |
|---|---|
| 해싱 | 키를 단순한 함수로 변환한 값을 배열 인덱스로 사용해 항목을 저장하는 것 |
| 해시값 | 키값을 특정 숫자로 나눈 나머지 값 (예: 35 % 13 = 9) |
| 해시 테이블 | 해시값을 인덱스로 하여 키값을 저장하는 배열 (각 요소: 버킷) |
| 해시 함수 | 키값을 해시값으로 변환하는 함수 |
삽입, 탐색, 삭제 연산을 평균 O(1)에 지원하여 데이터 처리 속도를 획기적으로 향상시킵니다.
2. 해시 함수의 중요성 및 종류
해시 함수는 키를 해시 테이블의 인덱스로 변환 하는 핵심 역할을 합니다. 이상적인 해시 함수는 키를 균등하게 분포 시키고, 연산이 빠릅니다.
| 종류 | 설명 |
|---|---|
| 중간 제곱 | 키를 제곱한 후 중간 부분을 해시값으로 사용 |
| 접기 | 여 러 자리 숫자를 일정한 크기로 나눠 합산 (예: 1234+5678+9012) |
| 곱셈 | 1보다 작은 실수 δ를 곱해 소수 부분×M 후 정수 부분 사용 |
| 나눗셈 | 키를 소수로 나눈 나머지를 해시값으로 사용 (가장 널리 쓰임) |
모든 해시 함수는 키의 값이 계산에 관여하며, 해시 테이블 크기에 따라 해시값이 결정됩니다.
3. 해시 테이블의 장단점 및 용도
| 구분 | 내용 |
|---|---|
| 장점 | - 데이터 저장/읽기 속도가 빠름 - 키 중복 확인이 용이함 |
| 단점 | - 충돌 발생 시 별도 해결 필요 - 많은 저장 공간 필요 |
| 용도 | - 저장/삭제/읽기 빈번, 검색이 많은 경우 - 캐시 구현 등 |
4. 해시 충돌(Collision) 및 해결 전략
성능이 좋은 해시 함수도 2개 이상의 항목이 같은 해시값을 가질 수 있습니다. 이를 충돌(collision) 또는 해시 충돌(hash collision) 이라고 하며, 해시값이 한쪽으로 치우치지 않도록 설계해도 충돌은 불가피합니다.
충돌 해결 방법은 크게 두 가지로 나뉩니다.
4.1. 닫힌 주소법(Closed Addressing) / 체인법(Chaining)
- 해시 테이블 외부 공간(연결 리스트 등)을 활용해 충돌을 해결
- 해시값이 같은 데이터는 연결 리스트로 사슬처럼 연결
- 각 버킷은 해당 해시값의 첫 노드를 참조
- 군집화 현상 없음, 구현 간결, 실제로 가장 많이 사용
| 연산 | 동작 방식 |
|---|---|
| 검색 | 해시값으로 버킷 선택, 연결 리스트를 선형 검색 |
| 추가 | 해시값으로 버킷 선택, 중복 없으면 리스트 맨 앞에 삽입 |
| 삭제 | 해시값으로 버킷 선택, 리스트에서 해당 노드 삭제 |
4.2. 오픈 주소법(Open Addressing)
- 충돌 발생 시 재해시(rehashing) 로 빈 버킷을 찾음
- 해시 테이블 전체를 열린 공간으로 보고, 충돌된 키를 빈 공간에 저장
- 닫힌 해시법(closed hashing) 이라고도 함
| 연산 | 동작 방식 |
|---|---|
| 삽입 | 충돌 시 재해시로 빈 버킷을 만날 때 까지 반복 |
| 삭제 | 단순 삭제 시 검색 실패 유발, '삭제 마침' 등 상태값으로 관리 |
| 검색 | 원하는 값 찾을 때까지 재해시 반복, '비어 있음' 만나면 실패 |
오픈 주소 방식의 종류 및 특징
- 선형 조사(Linear Probing): h(key) + j % M (j=0,1,2,...)
- 1차 군집화(primary clustering) 발생, 빈 요소 적을수록 심화
- 이차 조사(Quadratic Probing): h(key) + j² % M
- 2차 군집화(second clustering) 발생, 점프 크기 커져 탐색 실패 가능
- 랜덤 조사(Random Probing): 의사 난수로 다음 위치 결정
- 3차 군집화(tertiary clustering) 발생
- 이중 해싱(Double Hashing): 2개의 해시 함수 사용, (h(key) + j*d(key)) % M
- 군집화 완화, d(key)≠0, d(key)와 M이 서로 소수일 때 성능 우수
결론
해싱은 데이터를 효율적으로 저장, 검색, 삭제하기 위한 강력한 기법입니다.
해시 함수의 품질과 충돌 해결 전략(체인법, 오픈 주소법 등)은 해싱 시스템의 성능을 좌우합니다.
체인법은 군집화가 없고 구현이 간결해 널리 쓰이며,
오픈 주소법은 공간 활용성이 높지만 군집화 완화를 위한 고도화된 전략(이중 해싱 등)이 필요합니다.