자료구조 해시 테이블(HashTable)
해시 테이블(HashTable)이란?
Key와 Value로 데이터를 저장하는 방법 중 하나로 데이터를 빠르게 검색할 수 있는 자료구조이다.
해시 테이블은 Key 값을 '해시값'으로 생성한 이후 실제 데이터가 저장되는 장소인 '버킷(Buckets)'에 저장하는 방식이다.
이때 해시값은 '해시 함수'를 통해 연산이 되어 생성이 되는데해시 함수는 해당 키 값에 대해서는 항상 고정적인 Index를 반환한다.이러한 과정을 통해 Key로 한번에 필요한 데이터를 찾는 게 가능하기 때문에평균적으로 O(1) 시간복잡도를 가진다.
해시 함수(Hash Function)
해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.이러한 해시 함수를 적용하여 나온 고정된 길이의 값을 해시값, 해시 코드, 해시섬(sum), 체크섬 등으로 부른다.
해시 함수는 결정론적 알고리즘(Deterministic Algorithm)으로 작동해야 한다.그렇기 때문에 두 해시 값이 다르다면 그 해시값에 대한 원래 데이터가 달라야 한다.(역은 성립하지 않는다.)
하지만 이러한 해시값은 '고유의 값(Unique Value)'을 갖지 않기 때문에서로 다른 입력값에도 동일한 값이 출력되는 경우도 존재한다.이러한 경우를 '해시 충돌(Hash Collision)'이라고 한다.
해시 충돌(Hash Collision)
해시 테이블에선 동일한 해시값에 의한 충돌을 크게 2가지 방식으로 해결하고 있다.
분리 연결법(Separate Chaining)
각 Index에 데이터를 Linked List에 대한 포인터를 가지는 충돌 처리 방식이다.
동일한 Index로 인해 충돌이 발생한다면
해당 Index가 가리키고 있는 Linked List에 노드를 추가하여 값을 추가한다.
데이터를 추출할 때는 Key에 대한 Index를 통해
해당 Index가 가리키고 있는 Linked List를 선형 검색하여 데이터를 가져오게 된다.
삭제 역시 Index가 가리키고 있는 Linked List에서 해당 데이터를 삭제하면 된다.
새로운 데이터를 추가할 때 테이블이 가득 차도 각 버킷에 있는 Linked List에 추가할 수 있기 때문에
추가하는 데이터 수의 제약이 적다.
시간 복잡도
중복된 해시값이 많아질수록 List에서 선형으로 검색이 이루어지기 때문에
데이터 삽입, 삭제, 검색에 있어 시간복잡도는 평균적으로 O(1)을 가진다.
하지만 최악의 경우 최대 O(n) 시간 복잡도까지 증가하게 되어 그만큼 캐시의 효율성이 떨어진다.
개방 주소법(Open Addressing)
빈 버킷을 찾아 데이터를 저장하는 충돌 처리 방식이며,
찾는 방식은 세 가지로 나뉜다.
1. 선형 탐사(Linear Probing)
충돌 발생 시 Index에 해당하는 버킷의 다음 버킷들을 순차적으로 탐색하며
빈 버킷 발견 시 해당 버킷에 데이터를 저장하는 방식으로 구현이 간단하다.
위와 같이 Key % 9 해시 함수를 사용하는 해시 테이블이 있을 때
Key값이 1, 12인 경우는 충돌이 없어 데이터가 저장된 모습이다.
하지만 Key값이 10인 경우엔 1과 충돌이 나기 때문에
그 이후 존재하는 빈 버킷에 바로 데이터를 저장하고 있다.
하지만 충돌이 빈번해지면 특정 구간에 연속된 데이터가 몰리는 클러스터링(clustering) 문제가 발생하게 된다.
이는 탐색 시간을 오래걸리게 하여 검색 효율이 떨어지게 된다.
2. 이차 탐사(Quadratic Probing)
선형 탐사와 비슷하지만 간격이 이차 함수 꼴로 증가하면서 빈 버킷을 찾는 방식이다.
예를 들어 Index가 3에서 충돌이 난다면 다음과 같은 형태로 Index가 증가한다.
3 → 3 + 1^2 → 3 + 2^2 → 3 + 3^3 → ...
선형 탐색에 비해 클러스터링이 적게 일어나지만
만약 두 Key의 해시값이 동일하다면 빈 버킷을 찾는 과정이 동일하므로 같은 버킷을 탐색하게 된다.
즉 처음 충돌한 위치가 같다면 다음 충돌할 위치에서도 반복적으로 충돌이 나게 되는 것이다.
2차 클러스터링 문제가 발생하게 된다.
3. 이중 해싱(Double Hashing)
이중 해싱은 클러스터링 문제를 방지하기 위한 기법으로
두 개의 해시 함수를 사용해 빈 버킷을 찾는 방식이다.
첫 해시 함수를 통해 해시값을 얻었을 때 충돌이 날 경우
두 번째 해시 함수를 통해 새로운 해시값을 받아 빈 버킷을 찾는다.
만약 이후에도 충돌이 난다면 두 번째 해시 함수를 통해 계속해서 빈 버킷을 탐색한다.
이러한 방식은 충돌이 발생했을 때 무작위로 빈 버킷을 찾게 되어 클러스터링 문제를 피할 수 있다.
하지만 그만큼 구현이 복잡하며 위의 두 방식에 비해 연산이 오래 걸린다는 단점이 있다.
삭제
삭제를 하기 위한 버킷을 찾고 해당 버킷을 삭제되었다고 표시한다.해당 버킷을 삭제되었다고 표시하지 않고 완전히 삭제하게 된다면탐색을 하지 못하는 경우가 발생할 수 있다.
위의 그림에서 모든 Key는 해시 함수를 통해 Index 1을 반환받게 된다.
Key 1의 경우 그대로 데이터가 적재되지만
나머지 10, 19의 경우 충돌로 인해 그 다음 Index에 연속적으로 적재된 것을 확인할 수 있다.
이때 Key 10을 완전히 삭제하게 될 경우 Key 19의 값을 찾을 수 없게 되는데
그 이유는 충돌을 해결하기 위해 사용된 연속적인 탐사 방식이 깨지기 때문이다.
Key 19의 값을 찾기 위해 Index 1부터 시작해 차례로 탐색을 하는 과정에서
빈 상태를 확인하게 되면 해당 자리에 값이 Key 19의 값이 없다고 판단하고 탐사를 중단해 버린다.
그렇기 때문에 완전히 삭제하지 않고 삭제되었다는 표시를 통해 유지한다.
해당 삭제 방식은 선형 탐사를 제외한 나머지 방식(이차 탐사, 이중 해시)에서도 똑같이 적용이 된다.
시간 복잡도
개방 주소형같은 경우도 충돌 시 찾아가는 횟수가 많아지므로
최상의 경우 O(1)에서 최악의 경우 O(n)으로 증가하게 된다.
리사이징(Resizing)
분리 연결법(Separate Chaining)의 경우 버킷이 일정 수준이상 차 버리면
각 버킷에 연결되어 있는 List의 길이가 늘어나기 때문에 성능 저하가 일어나고
주소 개방형(Open Addressing)의 경우 고정 크기 배열을 사용하기 때문에
일정 수준이상 차 버리면 성능 저하가 일어날 뿐더러 데이터를 적재할 공간이 남지 않게 된다.
즉 해시 테이블의 '부하율(Load Factor)'이 높아질수록 그만큼 충돌이 많아지고 성능이 저하되기 때문에
이러한 경우 리사이징이 일어난다.
리사이징 이후에는 테이블이 더 커지기 때문에 충돌이 줄어들어 검색 성능이 다시 O(1)에 가깝게 유지되게 된다.
하지만 리사이징을 통해 테이블의 크기가 늘어나면
모든 데이터를 새 해시 테이블로 재해싱하는 작업이 필요하므로 작업에 대한 큰 비용을 요구하게 된다.
참고 블로그