[알고리즘] - 해시 (Hash)

buckshot·2024년 5월 20일

알고리즘

목록 보기

9/19

해시는 데이터를 다루는 기법 중 하나이다.

임의의 크기를 갖고있는 데이터를 고정된 크기의 값으로 변환시켜 Key - Value의 형태로 저장을 한다. 이런 형태로 인하여 Key의 값이 배열의 인덱스로 저장되기 때문에 검색과 저장의 실행이 빠르다.

키에 대한 해시 값을 구하는 과정을 해싱(hashing)이라고 한다. 이때 사용하는 함수를 해시 함수라고 칭한다.

해시 값 자체를 인덱스로 사용한다거 했다. 그렇기에 평균 시간 복잡도가 $O(1)$ 이므로 매우 빠르다.

해시에서 주의할 부분이 특정 데이터가 저장되는 인덱스는 해당 데이터만의 고유한 Key를 갖기 때문에 삽입 시 다른 데이터 중간에 저장되거나 제거 시 다른 데이터로 대신 할 수 없다. 그렇기 때문에 데이터 삽입과 제거를 할 수 없는 구조로 만들어 졌다.

해시 함수는 Key값을 고정된 길이의 hash로 변환을 한다.

데이터를 효율적으로 관리하는 것을 목적으로 임의의 길이의 데이터를 입력받아 일정한 길이의 비트열로 바꿔준다.
함수는 계산이 복잡하지 않고 키값에 대하여 중복없이 해시 값을 고르게 만들어 내는 함수가 좋은 함수다.

여기서 Key값을 Hash로 변환하는 동작을 앞서 간단하게 설명을 할 때 해싱(hashing)이라고 했다.

해시 함수를 이용하여 키를 해시 값으로, 해시 값을 인덱스로 삼아 Key와 Value를 저장하는 자료 구조를 말한다.

해시 충돌은 해시 함수가 서로 다른 두 개의 입력값에 대하여 동일한 해시 값을 반환하는 상황을 이야기 한다.

충돌이 많으면 자료구조나 알고리즘의 효율성을 떨어뜨리며 탐색의 시간 복잡도가 $O(n)$ 에 가까워지게 된다. 그렇기에 충돌이 발생하지 않게 대비를 해야한다.

해당 충돌에 대하여 대응 방법을 알아보겠다.

먼저 확인한 개별 체이닝의 경우는 더 이상 빈 슬롯이 없더라도 추가적으로 연결 리스트로 늘려가기 때문에 데이터의 주소값은 바뀌지 않는다. 그렇기에 이 방법은 Closed Address의 성격을 띈다.

개방 주소는 충돌이 발생하면 해시 테이블 내 다른 빈 슬롯을 찾아 데이터를 저장하는 방식이다.

개방 주소의 방법에 있어서 빈 슬롯을 찾는 과정을 탐사라고 한다.
개방 주소에 있어 여러 방법으로 탐사를 한다.

선형 탐사 Linear Probing

선형 탐사는 충돌이 일어나면 일정한 간격으로 다음 슬롯을 검사하는 방법이다. 일반적으로는 간격은 1이다.

선형 탐사의 장점으로는 구현이 간단하다. 하지만 단점으로는 연속된 슬롯이 점점 채워지는 현상클러스터링(Clustering)으로 성능 저하가 발생할 수 있다
이차 탐사 Quadratic Probing

이차 탐사는 충돌이 발생할 때마다 탐사 간격이 제곱수로 증가를 한다.

장점으로는 선형탐색의 단점으로 나타나는 클러스터링(Clustering) 문제가 줄어든다.
단점으로 이차 탐사로도 해결되지 않는 이차 클러스터링(Clustering)이 발생할 수 있다.
이중 해싱 Double Hashing

이중 해싱은 두 개의 독립적인 해시 함수를 사용하여 충돌을 해결한다.

장정은 클러스터링(Clustering)문제를 최소화 하고, 이론적으로 가장 좋은 분포를 제공한다.
하지만 이중 해싱은 구현이 복잡하고, 두 개의 해시 함수를 정의해야 한다.