1. Hash Table, 해시 테이블이란?
해시테이블 혹은 해시 맵이라고 부르며 연관배열 구조를 이용하여 키(key)에 결과 값(value)을 저장하는 자료구조이다.
연관배열 구조 = 키와 값이 1:1로 연관되어져 있는 구조.
키를 저장할 때 해시 함수라는 함수를 통해 특정 숫자값의 인덱스로 변환되며, 여기에 값을 매칭하여 저장소에 저장함.
해시 테이블은 고정된 크기의 자료구조를 가지고 있고, 이후 필요에 의해 메모리 크기를 늘릴 수 있으나, 최소한의 크기를 유지함.
객체가 나오기 전에 배열을 순서가 아니라 의미를 기준으로 키, 값의 쌍으로 저장하기 위해서 쓰이기 시작했다고 함.
2. 구조를 도식화하면,
그러나 키에 따른 해시 함수에 따른 해시값이 같게 도출 될 수 있고, 이런 경우를 충돌(collision)이라고 한다. 그럴 경우의 도식은 아래와 같다.
무한한 값을 유한한 값으로 표현하면서 서로 다른 두 개의 유한한 값이 동일한 출력값을 가지게 된다.
충돌이 나타나면 다음과 같은 방법으로 해결한다.
2-1. Chaining
첫번째 그림에서의 버켓 내에 Linked List를 할당하여, 데이터를 연결하는 방식.
한정된 저장소를 효율적으로 쓸 수 있고, 같은 주소값을 가지며 상대적으로 적은 메모리를 사용하지만, 한 해시값에 데이터가 계속 연결되면, 검색의 효율이 낮아진다.
2-2. Open Addressing
해시 충돌이 일어나면, 다른 버켓에 데이터를 저장하는 방식이며, 오픈 어드레싱의 방식에는 3가지가 있다.
- 선형 탐색(Linear Probing): 해시충돌 시 다음 버켓, 혹은 몇 개를 건너뛰어 데이터를 삽입한다. 아래 도식 참고
- 제곱 탐색(Quadratic Probing): 해시충돌 시 제곱만큼 건너뛴 버켓에 데이터를 삽입(1,4,9,16..)
- 이중 해시(Double Hashing): 해시충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용함.
3. Time Complexity
해시는 평균적으로는 키&밸류로 이루어져있기 때문에 검색, 저장, 제거를 할 때는 O(1)의 시간복잡도를 가지지만, 최악의 경우(혹은 collision의 경우)는 모든 저장소를 다 봐야 할 수 있기 때문에 O(n)의 시간복잡도를 가진다.
4.참고자료 & 출처
