1. 해시 테이블 (Hash Table)
- 키 (Key), 값 (Value)을 대응시켜 저장하는 데이터 구조
- 키를 통해 해당 데이터에 빠르게 접근이 가능하다.
- 해시 맵, 해시 표라고도 한다.
- 해싱 (Hashing)
키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정
1.1 해시 테이블 구조
- 키 : 해시 테이블 접근을 위한 입력 값
- 해시 함수 : 키를 해시 값으로 매핑하는 연산 (키 -> 해시 값)
- 해시 값 : 해시 테이블의 인덱스
- 해시 테이블 : 키-값을 연관시켜 저장하는 데이터 구조
좋은 Hash Function은 Hash Value에 값을 골고루 분포되어 접근할 수 있게 만들어주는 것이다.
그렇지 않은 경우, 접근하는 쪽에 계속 접근하게 돼서해시충돌이 발생하게 된다.
2. 해시 충돌
- 해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 경우를 뜻한다.
- (즉, 서로 다른 키의 해시 함수를 통한 해시 값이 동일한 경우)
- 해시 충돌 해경 방법으로는 크게 개방주소법과 분리연결법이 있다.
해시 충돌 Case
- key2 에 대한 해시 값이 key1과 동일
- Hash Table 에는 이미 key1-data 가 들어있는 상황
3. 해시 충돌 해결 방법
3.1 개방 주소법 (Open Address)
- 충돌 시, 테이블에서 비어있는 공간의 Hash를 찾아 데이터를 저장한다.
- Hash 와 Value 가 1:1 관계를 유지한다.
- 비어있는 공간 탐색 방법에 따라 선형 탐사법, 제곱 탐사법, 이중 해싱으로 분류된다.
3.1.1 개방 주소법 - 선형 탐사법 (Linear Probing)
- 빈 공간을 순차적으로 탐사하는 방법
- 충돌 발생 지점부터 이후의 빈 공간을 순서대로 탐사한다.
- 일차 군집화 문제 발생
- 반복된 충돌 발생 시 해당 지점 주변에 데이터가 몰리는 경우가 발생한다.
선형 탐사법은 빈 공간을 순차적으로 탐사하며 값을 채우다 보니,
해당 충돌 지점 주변으로 데이터가 몰리는 경우가 발생할 수도 있다. (일차 군집화 문제 발생)
3.1.2 개방 주소법 - 제곱 탐사법 (Quadratic Probing)
- 빈 공간을 n 제곱만큼의 간격을 두고 탐사하는 방법
- 충돌 발생 지점부터 이후의 빈 공간을 n제곱 간격으로 탐사한다.
- 일차 군집화 문제 일부 보완
- 이차 군집화 문제 발생 가능성이 있다.
선형탐사법에 비해 상대적으로 해시테이블 데이터들을 골고루 분포시킬 수 있다.
3.1.3 개방 주소법 - 이중 해싱 (Double Hashing)
- 해싱 함수를 이중으로 사용
해시함수 1 : 최소 해시를 구할 때 사용
해시함수 2 : 충돌 발생 시, 탐사 이동 간격을 구할 때 사용
- 선형 탐사법, 제곱 탐사법에 비해 데이터가 골고루 분포된다.
3.2 분리 연결법 (Separate Chaining)
- 해시 테이블을 연결리스트로 구성
- 충돌 발생 시, 테이블 내의 다른 위치를 탐색하는 것이 아닌 연결리스트를 이용하여 해당 데이블에 데이터를 연결한다.
📚 해시 충돌 해결방법 정리
해시 충돌 해결방법에는 개방주소법과 분리연결법이 있다.
1. 개방 주소법 (선형 탐사법, 제곱 탐사법, 이중 해싱)
2. 분리 연결법
개방 주소법은 빈공간은 탐사해서 데이터를 채우기 때문에, Hash와 Value 가 1:1의 관계를 유지한다.
분리연결법은 하나의 키 값에 대해서 동일한 Hash 위치에 데이터가 연결되어 있기 때문에 1:1 관계를 유지하지 않는다.
분리연결법은 나중에, 원하는 값을 get 할 때는 개방주소법보다 상대적으로 오래 걸린다는 단점이 있다.
