- Key: 해시 테이블 접글을 위한 값
- Hash Function: Key를 Hash Value로 매핑하는 연산
- Hash Value: Hash Table의 인덱스
- Hash Table: Key-Value를 연관시켜 저장하는 데이터 구조
해시 충돌
- Hash Table의 같은 공간에 서로 다른 값을 저장하려는 경우, 서로 다른 Key가 해시 함수를 통해 생성된 Hash Value가 동일한 경우 해시 충돌이 있어날 수 있다.
- 해시 충돌 해결 방법으로는 크게
개방 주소법과분리 연결법이 있다.
개방 주소법 (Open Address)
- 테이블에서 비어있는 공간의 Hash를 찾아 데이터를 저장
- Hash와 Value는 1:1 관계를 유지
- 비어있는 공간 탐색 방법에 따라
선형 탐사법,제곱 탐사법,이중 해싱등으로 분류
1. 선형 탐사법 (Linear Probing)
- 충돌 발생 지점부터 이후의 빈 공간을 순서대로 탐사하는 방법
- 반복된 충돌 발생시 해당 지점 주변에 데이터가 몰리는 경우가 발생 (일차 군집화)
- 순차적으로 데이터가 존재하여 빈 공간을 탐사하는 시간이 오래걸릴 수 있음
2. 제곱 탐사법 (Quadratic Probing)
- 충돌 발생 지점부터 이후의 빈 공간을 n제곱 간격으로 탐사
- 일차 군집화 문제를 일부 보완
- 이차 군집화 문제가 발생할 수 있음
3. 이중 해싱 (Double Hashing)
- 해싱 함수를 이중으로 사용
- 해시 함수 1: 최초 해시를 구할 때 사용
- 해시 함수 2: 충돌 발생 시 탐사 이동 간격을 구할 때 사용
- 선형 탐사, 제곱 탐사에 비해 데이터가 골고루 분포
분리 연결법 (Separate Chaining)
- Hash Table을 연결 리스트로 구성
- 충돌 발생시 테이블 내의 다른 위치를 탐색하는 것이 아닌 연결 리스트를 이용하여 해당 테이블에 데이터를 연결
- 충돌시 연결된 모든 데이터를 순차적으로 탐색해야하기 때문에 효율이 떨어질 수 있음
연결 리스트의 각 노드들은 Key 값을 추가로 가지며 Key로 값을 가져올 때 해당 Key를 가지고 있는 노드를 찾는다.