Hash Table의 정의
해쉬함수(hash function)를 사용하여 변환한 해시(hash)를 색인(index)으로 삼아 키(key)와 데이터(value)를 저장하는 자료구조
필요한 데이터의 키(key)를 해시함수를 사용해 별도의 해시(hash)로 바꿔 주고, 해당하는 데이터(value)를 함께 저장하는 자료구조
Hash Table의 구조
Hash Table은 키(key)와 해시함수(hash function), 해시(hash), 데이터(value)로 이루어져 있다.
- 키(key) : 고유한 값으로 해시 함수의 입력값이 된다. 다양한 길이의 값이 들어올 수 있다. 해시 함수를 통해 변환하지 않은 상태로 저장소에 저장이 되면 다양한 길이만큼의 저장소를 구성해 두어야하기 때문에 해시 함수로 값을 바꾸어 저장하게 된다.
- 해시함수(hash function): 키를 해시로 바꿔주는 역할을 한다. 다양한 길이를 가지고 있는 키를 일정한 길이를 가지는 해시로 변경하여 저장소를 효율적으로 운영할 수 있도록 도와준다. 다만, 서로 다른 키가 같은 해시가 되는 경우를 해시 충돌이라고 하는데, 해시 충돌을 일으키는 확률을 최대한 줄이는 것이 중요하다.
- 해시(hash) : 키를 해시함수를 사용하여 만들어진 결과물로, 저장소에서 데이터와 매칭되어 저장된다. 변환된 값을 배열의 색인(index)과 같이 사용하게 된다.
- 데이터(value) : 저장소에 최종적으로 저장되는 값으로 색인(index)과 매칭되어 저장된다.
Hash Table의 특징
Hash Table에서 저장, 삭제, 검색 과정은 모두 평균적으로 O(1)의 시간복잡도를 가지고 있어 데이터를 다루는 작업이 매우 빠르다는 장점이 있다.
다만, 해시 충돌이 발생할 수 있고 데이터가 저장되기 전에 저장공간을 미리 만들어놔야 하기 때문에 공간 효율성이 떨어진다. 또한 해시함수의 의존도가 높다.
해시함수가 복잡하다면, 해시값을 만들어내는 데 많은 시간이 소요된다.
-
저장, 삭제, 검색 과정
hash table에서 값을 저장, 삭제, 검색하기 우해서는 해시함수에 키 값을 넣어 해시 값을 만들게 된다. 이후 만들어진 해시 값과 일치하는 색인을 찾아 저장하거나 삭제, 검색한다.
기본적으로 해당 작업들의 시간복잡도는 O(1)
해시함수를 거쳐 해시 값을 찾아내는데 걸리는 과정은 고려하지 않는다. 그러나 해싱 충돌이 발생할 경우 저장소의 모든 색인(삽입) 혹은 데이터(삭제, 검색)를 찾아봐야 하기 때문에 O(n)이 된다. -
대표적인 해시 알고리즘
- Division Method : Number type의 키(key)를 저장소의 크기로 나누어 나온 나머지를 색인(index)으로 사용하는 방법이다. 이때 저장소의 크기를 소수(Prime Number)로 정하고 2의 제곱수와 먼 값을 사용하는 것이 효과가 좋다.
- Digit Folding : 키(key)의 문자열을 ASCII 코드로 바꾸고 그 값을 합해 저장소에서 색인(index)으로 사용하는 방법이다. 만약 이때 색인(index)가 저장소의 크기를 넘어간다면 Division Method를 적용할 수 있다.
- Multiplication Method : 숫자로 된 Key 값 K와 0과1 사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같이 계산한 값을 사용한다. index = (KA mod 1)m
- Universal Hashing : 다수의 해시함수를 만들어 특정한 장소에 넣어두고, 무작위로 해시함수를 선택해 해시(hash)값을 만드는 기법이다.
해시 충돌을 해결할 수 있는 방법
- 개방 연결법(Open Addressing)
개방 연결법이란 해시 충돌이 발생하면 다른 색인에 해당 자료를 삽입하는 방식이다.
- Linear Probing : 현재 중복된 색인으로 부터, 고정된 숫자만큼 이동하여 비어있는 저장소(버킷)를 찾아 데이터를 저장한다.
- Quadratic Probing : 현재 중복된 색인(index)으로 부터 이동할 숫자를 제곱으로 사용하는 방식이다. 처음 충돌이 발생하면 1(1^2)만큼 이동하고, 또 충돌이 발생한다면 4(2^2)만큼, 3번째는 9(3^2)만큼, 4번째는 16(4^2)만큼 이동하여 빈 공간을 탐색하는 방법이다.
- Double Hasing Probing : 하나의 해시함수(hash function)에서 충돌이 발생한다면 미리 지정해둔 다른 해시함수(hash function)를 이용해 새로운 주소를 받아 사용하는 방법이다. 다른 방법들보다 많은 연산이 필요하다.
- 분리 연결법(Seperate Chaining)
분리 연결법이란 동일한 색인(index)의 데이터에 대해 연결리스트(linked list), 트리(Red-Black tree) 등의 자료구조를 활용해 데이터의 주소를 저장하는 방법이다.
이 방식의 경우 구현이 간단하며, 데이터(value)를 쉽게 삭제할 수 있다는 장점이 있다. 하지만 중복으로 저장되는 데이터(value)가 많아지면 동일한 버킷에 연결되는 데이터(value)가 많아져서 검색의 효율성이 감소하는 단점이 있다. - 저장소 확장(Resize)
