해시 테이블(Hash Table)
선형 자료구조중 하나로, 키값으로 빠르게 데이터를 접근할 때 사용하는 자료구조이다.
대부분의 선형 자료구조의 데이터 탐색 시간 복잡도가 O(n) 이라면 해시 테이블은 거의 O(1)이라 할 수 있다.
구조
- 키(Key): 해시 테이블 접근을 위한 값
- 해시 함수(Hash function): 키를 해시 값으로 매핑하는 연산
- 해시 값(Hash Value): 해시 테이블의 인덱스
- 해시 테이블(Hash Table): 키-값을 연관시켜 저장하는 데이터 구조
해시 충돌
서로 다른 키들이 해시 함수를 통해 해시 값이 동일하게 나온 경우, 해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 오류(충돌)이 발생하게 된다.
이를 해결 하는 방법으로는 크게 개방 주소법와 분리 연결법이 있다.
개방 주소법(Open Address)
충돌 시, 테이블에 비어 있는 공간의 해시(=인덱스)를 찾아 데이터를 저장한다.
- 해시와 값이 1:1 관계를 유지
- 비어 있는 공간 탐색 방법에 따라 분류
- 선형 탐사법
- 제곱 탐사법
- 이중 해싱
- 어떤 방법을 사용하라도 값이 몰리는
군집화문제가 발생
선형 탐사법(Linear Probing)
충돌 발생 지점 부터 이후의 빈 공간을 순서대로 탐사하는 방법
제곱 탐사법(Quadratic Probing)
충돌 발생 지점 부터 이후의 빈 공간을 n^2 간격으로 탐사하는 방법
이중 해싱(Double Hasing)
해싱 함수를 이중으로 사용하는 방법으로, 최초 해시 함수로 충돌이 발생하면 두 번째 해시 함수를 이용한다. 두번 째 해시 함수를 이용 시 테이블 크기보다 작은 소수를 이용한다.
// 예시
int hash2 = 1 + hash1 % primeNumber;분리 연결법(Separate Chaining)
동일한 공간에 저장되어야 하기 때문에 공간에 체인을 통해 값을 연속적으로 저장한다.
- 해시와 값이 1:n 관계
- 해시 값이 중복될 수록 탐색 시간이 길어진다.
O(n) - 링크드리스트 자료구조를 많이 사용한다.
배고파