해싱(들어가기 전에)
임의의 길이의 값을 해시함수를 사용하여 고정된 크기의 값으로 변환하는 작업
해시 테이블
해시 테이블이란 해시함수를 사용하여 변환한 값을 index로 삼아 key와 value를 저장하는 자료구조를 말한다.
기본연산으로 탐색, 삽입, 삭제가 있다.
그래서 해시테이블이 뭔데?
해시함수를 사용하여 특정 해시값을 알아내고그 해시값을 인덱스로 변환하여 키값과 데이터를 저장하는 자료구조이다. 개념자체는 어려운 개념이 아니다.
하지만 문제가 되는 것은 collision(충돌)이다. 충돌에 대해서 이해하기 위해서는 Load Factor(적재율)에 대해서 이해해야 한다.
적재율?
적재율이랑 해시 테이블의 크기 대비, 키의 개수를 말한다. 즉, 키의 개수를 K, 해시 테이블의 크기를 N이라고 하면 적재율은 K/N이다. Direct Address Table은 키 값을 인덱스로 사용하는 구조이기 때문에 적재율이 1 이하이며 적재율이 1 초과인 해시 테이블의 경우는 반드시 충돌이 발생하게 된다.
만약,
충돌이 발생하지 않는다고 할 경우 해시 테이블의 탐색,삽입,삭제 연산은 모두 O(1)에 수행되지만 충돌이 발생할 경우 탐색과 삭제 연산이 최악에 O(K)만큼 걸리게 된다. 이는 같은 인덱스에 모든 키 값과 데이터가 저장된 경우로 충돌이 전부 발생했음을 말한다.
따라서,
충돌을 최대한으로 줄여서 연산속도를 빠르게 하는 것이 해시테이블의 핵심이다.
이런 충돌을 막기위해 구현하는 것이 해시 알고리즘이다. 해시 알고리즘이 견고하지 못하게 되면 해시함수로 도출된 값들이 같은 경우가 빈번하게 발생하게 되고잦은 충돌로 이어지게 된다.
그래서 뭐가 중요한 데??
해시 데이블의 중점사항은 충돌을 완화하는 것이며 방법으로는 2가지가 존재한다.
해시 테이블의 구조를 개선하거나
or
해시 함수를 개선하도록 한다.
해결방법 1 : 해시 테이블의 구조개선
체이닝
(K/N 해시 테이블 내에 공간 대비 키 값들이 얼마나 있느냐)
해시 테이블에서 충돌문제를 해결하는 방법 중 하나다. 체이닝은 같은 인덱스에 여러 개의 데이터를 저장할 수 있도록 각각의 인덱스마다 연결리스트(linked list)를 만들어서 사용하는 방법이다. 충돌이 발생하면 해당 인덱스에 연결 리스트가 존재하는 경우, 연결 리스트의 맨 끝에 새로운 데이터를 추가한다. 아래와 같은 해시테이블이 있다고 가정해보자
Hash Table:
0:
1: 10 -> 21 -> 32
2: 3
3: 4
4: 15 -> 26위와 같은 해시 테이블에서 index(인덱스)1에 21이라는 새로운 데이터를 추가하면, 인덱스1의 연결 리스트의 맨 끝에 21이 추가된다.
체이닝은
해시 충돌이 발생하더라도 연결 리스트(linked list)를 사용하기 때문에 저장할 수 있는 데이터의 양이 무한대에 가깝다. 그러나 해시 충돌이 자주 발생하거나 저장된 데이터의 수가 많아질수록 연결리스트(linked list)의 길이가 길어져서 검색 속도가 느려질 수 있다.
open addressing
해시 테이블에서 충돌이 발생하면 충돌이 발생한 버킷이 아닌 다른 버킷에 데이터를 저장하는 방식이다. 만약 충돌이 발생한다면 새로운 버킷을 선택하여 데이터를 저장하는데,이 때 선택된 버킷을 검사해서 다른 데이터가 저장되어 있는 경우 해당 버킷에 새로운 데이터를 저장할 때까지 이 과정을 반복한다.
즉, 원래라면 해시함수로 얻은 해시값에 따라서 데이터와 키값을 저장하지만 동일한 주소에 다른 데이터가 있을 겨우 다른 주소도 이용할 수 있게 하는 기법이다.
1. 선형 탐사(linear probing):
충돌이 발생한 버킷 다음에 순서대로 버킷을 검사하여 다른 버킷에 데이터를 저장하는 방식,이 때 검사할 버킷의 순서는 일정한 간격으로 정해진다. 가장 기본적인 충돌해결방법이지만 클러스터링(Clustering)문제가 발생하여 탐색과 삭제가 느려지게 된다.
cf)클러스터링은
비슷한 속성을 가진 데이터를 그룹화하는 기술이다. 데이터 분석에서 일반적으로 사용되며, 비슷한 특징을 가진 데이터끼리 그룹을 이루어 데이터를 이해하고 분석하기 쉬운 형태로 만든다. 클러스터링 알고리즘은 데이터를 분석하고 유사한 데이터끼리 클러스터를 형성하며, 클러스터 내의 데이터 간에는 유사성이 높고, 클러스터 간의 데이터 간에는 차이가 크다. 클러스터링을 통해 데이터를 분석하면, 데이터 같의 패턴이나 규칙을 찾을 수 있고, 분류 및 예측 등의 다양한 응용 분야에서 활용된다.
2. 제곱 탐사(Quadratic Probing):
제곱탐사는 말 그래로 1^2, 2^2, 3^2...으로 탐사를 하는 방식으로 선형탐사에 비해 더 폭넓게 탐사하기 때무에 탐색과 삭제에 효율적일 수 있다. 하지만 이 경우에도 해시값이 같을 경우에 탐사하는 클러스터링(clustering)문제가 발생하게 된다.
3. 이중해싱(Double Hashing)
이중해싱은 선형탐사와 제곱탐사에서 발생하는 클러스터링 문제를 모두 피하기 위해 도입되었다. 처음 해시함수로는 해시값을 찾기 위해 사용하고 두번째 함수는 충돌이 발생했을 때 탐사폭을 계산하기 위해 사용된다.
비교
여기서
α는 적재율
successful search는 찾고자 하는 데이터가 해시테이블에 있는 경우
unsuccessful search는 없는 경우
충돌해결2 : 해시 함수 개선
나눗셈법(Division Method)
아주 간단하게 해시값을 구하는 방법으로 미리 해시 테이블의 크기인 N을 아는 경우에 사용할 수 있다. 해시 함수를 적용하고자 하는 값을 N으로 나눈 나머지를 해시값으로 사용하는 방법이다.
H(K) = K%N (N은 소수를 사용하는 것이 좋다.)
곱셈법(Multiplication Method)
0<A<1인 A에 대하여 다음과 같이 구현가능하다.
h(k) = [N(kA%1)]
kA%1의 의미는 kA의 소수점 이하 부분을 의미하며 이를 N에 곱하므로 0부터 N 사이의 값이 된다. 이 방법의 장점은 N이 어떤 값이더라도 잘 동작하는 것이며 A를 잘 잡는 것이 중요하다.
