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

정의

 

해싱 (Hashing)

 

해싱(Hashing)은 임의의 길이의 데이터를 고정된 길이의 데이터로 변환하는 작업을 뜻하며 고정된 길이의 데이터를 따로 해시(Hash) 혹은 해시 값(Hash Value)이라고도 부른다.

 

 

해싱(Hashing) 과정

 

 

해시 함수 (Hash Function)

 

해시 함수(Hash Function)는 해싱을 진행할 때 사용하는 함수를 뜻하며 해시 함수에 따라 변환되는 데이터 값이 다르다. 그러나 입력된 데이터의 값이 같으면 같은 해시 함수를 사용하여 해싱했을 때 출력되는 데이터의 값은 항상 같다. 

 

 

해시 테이블 (Hash Table)

 

해시 테이블(Hash Table)은 [ Key : Value ]로 이루어진 데이터에서 Key의 해시 값을 색인(index) 혹은 주소 삼아 Key에 대응하는 Value를 버킷(Bucket)이라 하는 배열에 저장하는 자료구조이다. 해시 테이블은 평균적으로 삽입, 삭제, 탐색 연산에 대해서 O(1)의 시간복잡도를 갖는다.

 

배열에서 이루어지는 삽입, 삭제 연산은 O(n)의 시간복잡도를 갖지만 해시 테이블에서는 해시 값이 색인의 역할을 하기 때문에 해시 값에 대응하는 Value 값만이 저장되어 O(1)의 시간복잡도를 가질 수 있는 것이다. 이것이 뜻하는 것은 배열에서 삽입, 삭제 연산 시 발생하는 저장요소들의 이동이 없다는 것이다. 

 

 

해시 테이블 (Hash Table)의 구조

 

해시 충돌(Hash Collision)과 해결 방법

 

 

해시 충돌 (Hash Collision)

 

해싱과정에서 같은 Key값을 해싱할 때 출력되는 해시 값은 항상 같다. 그러나 서로 다른 Key값을 해싱했을 때 같은 해시 값이 출력되는 경우가 있다. 같은 해시 값을 가질 경우 저장 공간이 중복되는 문제점이 발생한다. 이 경우를 해시 충돌(Hash Collision)이라고 하며 이를 최소화 하기 위한 방법으로 개방 주소법 (Open Addressing)과 체이닝(Chaining)이 있다.

 

 

해시 충돌(Hash Collision)

 

개방 주소법 (Open Addressing)

 

개방 주소법(Open Addressing)은 추가적인 메모리 공간을 사용하지 않고 비어있는 버킷의 공간을 활용하는 방법이다. 개방 주소법에는 대표적인 3가지 방법이 존재한다.

 

1. Linear Probing : 충돌이 발생한 곳에서 부터 고정된 값만큼 이동 및 탐색하며 비어있는 공간 발견 시 저장하는 방법, 끝에 다다를 경우 처음 공간으로 이동한다.
2. Quadratic Probing : 충돌이 발생한 곳에서 부터 이동 및 탐색에 쓰이는 값을 제곱씩 변화시켜 탐색에 사용, 예시로 한 번 충돌이 일어났을 때 1^2만큼 이동 및 탐색 후에 다시 충돌이 일어나면 2^2만큼 이동 및 탐색, 다시 충돌이 일어나면 3^3만큼....반복, 끝에 다다를 경우 처음 공간으로 이동한다.
3. Double Hashing : 충돌이 발생하면 해시 값을 한번 더 해싱하는 방법, 다른 방법에 비해 많은 연산 발생

 

 

 

체이닝 (Chaining)

 

체이닝(Chaining)은 해시 충돌이 발생한 곳의 공간을 연결 리스트로 연결하는 방법이다. 연결 리스트로 연결하게 될 경우 해시 충돌로 인한 오버플로우나 저장 공간이 부족한 문제점은 해결되나 해시 테이블의 장점 중 하나인 빠른 탐색 연산의 시간 복잡도가 O(n)을 갖게 될 수 있다는 점이다.