이전 블로그에서 글 옮김

해시테이블(Hash Table)이란?

해시테이블은 Key, Value 페어로 데이터를 저장하는 자료구조의 유형 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조 입니다.
해시테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 이용하여 데이터를 저장하기 때문입니다. 해시테이블은 각각의 Key값에
해시함수를 적용해 배열의 고유한 index를 생성하고 이 index를 활용하여 값을 저장하거나 검색하게 됩니다. 여기서 실제 값이 저장되는 장소를
버킷 또는 슬롯이라고 합니다.

예를 들어, 우리가 Key, Value가 'John Smith', '521-1234'인 데이터를 크기가 16인 해시테이블에 저장한다고 가정해봅시다. 그러면
면저 index = hash_function('John Smith') % 16 연산을 통해 index값을 계산합니다. 그리고 array[index] = '521-1234'로
전화번호를 저장하게 됩니다. 이러한 구조로 데이터를 저장하면 Key값으로 데이터를 찾을 때 해시 함수를 한 번만 수행하면 되어 매우 빠르게 데이터를
저장/삭제/조회 할 수 있습니다.

이렇게 index를 통해 필요한 데이터를 바로 찾을 수 있기 때문에 해시테이블의 평균 시간복잡도는 O(1)입니다.

해시함수

해시함수에서 중요한 것은 고유한 인덱스 값을 설정하는 것입니다. 해시테이블에서 사용되는 대표적인 해시함수는 아래의 4가지가 있습니다. 그 중 가장 대표적인것은 Division Method와 Multiplication Method입니다.

1. Division Method: 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산합니다. 주소 = 입력값 % 테이블의 크기로 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 알려져 있습니다.
2. Digit Folding: 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법입니다.
3. Multiplication Method: 숫자로된 Key값 K와 0과 1 사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같은 계산을 해줍니다.
4. Universal Hashing: 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법입니다.

해시충돌

해시충돌은 해시테이블의 한 주소를 놓고 두 개 이상의 원소가 충돌하는 것을 말합니다. 쉽게 말하면 해싱을 해서 삽입하려하니 이미 다른 원소가 자리를 차지하고 있는 상황을 말합니다.
해시함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우, 비둘기집 원리에 의해 해시충돌은 항상 존재하게 됩니다.
해시충돌을 해결하는 방법은 크게 2가지가 있습니다.

해시충돌 해결법

분리 연결법(Separate Chaining)

분리 연결법이란 자료를 저장할 때 버킷에서 충돌이 일어나면 해당 값을 기존 값과 연결시키는 방법입니다. 위 사진에서 Sandra를 저장할 때 충돌이 일어났고, 기존에 있던 John에 연결시켰습니다.
이 때 연결리스트(Linked list) 자료구조를 이용합니다. 다음에 저장된 자료를 기존의 자료 다음에 위치시키는 것입니다.

분리 연결법에는 장점과 단점이 존재합니다.

장점

1. 한정된 버킷을 효율적으로 사용할 수 있습니다.
2. 해시함수를 선택하는 중요성이 상대적으로 낮습니다.
3. 상대적으로 적은 메모리를 사용합니다. 즉, 미리 공간을 잡아 놓을 필요가 없습니다.

단점

1. 데이터의 수가 많아지면 동일한 버킷에 연결되는 데이터가 많아지게 됩니다. (쏠림 현상)
2. 그에 따라 캐싱의 효율성이 감소하게 됩니다.
3. 추가 저장 공간을 사용해야 합니다.

개방 주소법(Open Addressing)

개방 주소법이란 추가적인 메모리를 사용하는 분리 연결법 방식과 다르게 비어있는 해시 테이블의 공간을 활용하는 방법입니다. 개방 주소법을 구현하기 위한 방식에는 대표적으로 3가지가 있습니다.

1. Linear Probing: 현재 버킷의 index로부터 고정폭만큼 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장하는 방식입니다.
2. Quadratic Probing: 해시의 저장순서 폭을 제곱으로 저장하는 방식입니다. 예를 들어, 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2칸씩 옮기는 방식입니다.
3. Double Hashing Probing: 해시된 값을 한 번 더 해싱하여 해시의 규칙성을 없애버리는 방식입니다. 한 번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 됩니다.

장점

1. 또 다른 저장공간 없이 해시테이블 내에서 데이터 저장 및 처리가 가능합니다.
2. 또 다른 저장공간에서의 추가적인 작업이 없습니다.

단점

1. 해시함수의 성능에 전체 해시테이블의 성능이 좌지우지 됩니다.
2. 데이터의 길이가 늘어나면 그에 해당하는 저장소를 마련해두어야 합니다.

해시테이블의 시간 복잡도

각각의 Key값은 해시함수에 의해 고유한 index를 가지게 되어 바로 접근할 수 있으므로 평균 O(1)의 시간복잡도로 데이터를 조회할 수 있습니다.
하지만 해시충돌이 발생한 경우 체이닝에 연결된 리스트들까지 검색을 해야하기 때문에 최악의 경우 O(n)까지 시간복잡도가 증가할 수 있습니다.
만약 테이블이 꽉 차있는 경우라면 테이블을 확장해야 하는데, 이는 매우 섬각한 성능의 저하를 불러오기 때문에 가급적이면 확장을 하지 않도록 테이블을 설계해야 합니다.
해시테이블의 공간 사용률이 70 ~ 80% 정도가 되면 해시충돌이 빈번하게 발생하여 성능이 저하되기 시작한다고 합니다.

또한 해시테이블에서 자주 사용하게 되는 데이터를 캐시에 적용하면 효율을 높일 수 있습니다. 자주 hit하게 되는 데이터를 캐시에서 바로 찾음으로써 해시테이블의 성능을 향상시킬 수 있습니다.