[자료구조] 해시 테이블(Hash Table)

해시 테이블(Hash Table)

해시 테이블은 key, value로 데이터를 저장하는 자료 구조입니다. 해시 테이블은 내부적으로 버킷(배열)을 사용하여 데이터를 저장하는데 각 key에 해시 함수를 적용하여 버킷의 고유한 index를 생성하고 이 index를 활용하여 값을 저장, 검색할 수 있습니다. value가 저장되는 장소를 버킷 혹은 슬롯이라고 명칭합니다.

key에 해시 함수를 적용해 바로 버킷에 도달할 수 있어 시간복잡도는 O(1)입니다.

 

해시 충돌

해시 함수에는 문제점이 하나 존재하는데 해시 함수는 입력 값의 길이에 상관없이 고정된 길이의 값을 출력하기 때문에 입력 값이 다르더라도 같은 결과 값이 나오는 케이스가 발생합니다. 이를 해시 충돌(Hash collision)이라고 명칭합니다.

이를 해결하는 방법은 2가지(개방 주소법, 분리 연결법)이 있습니다.

 

개방 주소법

개방 주소법 (Open addessing)은 한 버킷 당 들어갈 수 있는 값은 하나이지만 해시 함수로 얻은 index가 아닌 다른 index에 데이터를 저장할 수 있도록 허용하는 방법입니다.

 

1. 선형 탐사법 (Linear Probing)

해시 함수로 나온 index에 이미 다른 값이 저장되어 있다면 해당 해시값에서 고정 폭을 옮겨 순차적으로 탐색해 비어있는 버킷에 값을 저장하는 방식입니다.

 

2. 제곱 탐사법 (Quadratic Probing)

해시 저장 순서 폭을 제곱으로 탐색하는 방식으로 1^2, 2^2, 3^2... 로 이동해서 버킷에 값을 저장하는 방식입니다.

 

3. 이중 해싱 (Double Hashing)

해시 함수를 통해 적용된 index에 한 번더 해시 함수를 적용하는 방식으로 해시의 규칙성을 없애 값을 저장하는 방식입니다.

 

분리 연결법 (Separate Chaining)

동일한 인덱스를 가진 버킷의 데이터에 대해 자료구조를 추가적으로 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 방식입니다. 이때 자료구조는 linked list와 tree를 사용합니다.