Hash

가능한 한 빨리 데이터를 저장하고 검색하기 위해 Hash라는 자료구조를 많이 활용한다. 해시 테이블은 데이터를 저장하는 테이블로 Key와 Value가 한 쌍으로 존재한다. Key 값은 해시 테이블에서 인덱스로 사용되며, 데이터를 찾기 위해 해시 함수를 거쳐 키 값을 얻고 검색하는 데 평균적으로 O(1)의 시간 복잡도가 걸린다. Hash에 대해 알아보자

---

Hash

Hash Function

해시 함수는 임의의 길이를 갖는 데이터를 고정된 길이의 키 값(인덱스 값)으로 변환하여 해시 테이블에 저장하는 기능을 한다. 그림의 우측 테이블은 해시 테이블로, Index는 해시 함수를 통해 생성된 키 값으로 해시 테이블에 저장될 공간을 의미하고 Data는 hash 값, Value라고도 하며 입력받은 데이터를 저장한다. 

 

Collision

당연한 소리이겠지만 해시 테이블은 무한한 데이터를 저장할 공간을 가지고 있지 않다. 100만 개의 데이터를 오랜 기간에 걸쳐 순차적으로 들어온다고 했을 때 처음부터 100만 개의 데이터가 저장될 수 있는 테이블을 만들어 놓을 수도 없는 노릇이다. 따라서 100만보다 작은 한정된 크기의 테이블을 만들어 놓고 데이터를 저장한다. 테이블의 크기가 한정되어 있다 보니 서로 다른 데이터여도 해시 함수는 같은 키 값을 생성할 수 있다. 이때 Collision(충돌)이 발생했다고 한다. 따라서 충돌이 발생했을 때 Collision 해결 방법 중 Chaining 또는 Open Addressing 기법을 통해 다른 위치에 저장시키도록 한다.

 

Collision 해결 기법

 

Chaining

 

 

• 해시 함수를 통해 동일한 키 값(인덱스)이 나올 경우 데이터를 Linked List로 관리
• 충돌이 발생할 경우 데이터가 들어올 때마다 추가적인 메모리 공간이 필요하다.

 

Open Addressing

해시테이블에서 하나의 인덱스에 여러 개의 데이터를 저장할 수 있는 Chaining 기법과 달리 하나의 인덱스에 하나의 데이터만 허용하도록 한다. Collision이 발생할 경우 다음과 같은 방법을 사용해서 Collision을 해결한다. 따라서 빈 공간을 찾을 때까지 키 값을 계속 생성한다.

• Linear Probing(선형 탐사) : 해당 인덱스에 데이터가 존재할 경우 다음 인덱스(현재 인덱스 + 1)에 데이터 저장
  • 해당 방식으로 Collision을 해결할 경우 Primary Clustering 문제에 취약하다.
  • ※ Primary Clustering : 특정 영역에 데이터가 몰리는 현상
  • 위 문제를 해결하기 위해 Quadratic Probing이 나왔다.
• Quadratic Probing(제곱 탐사) : 데이터 공간에 접근하며 충돌이 발생할 때마다 증가 폭을 제곱으로 하여(1 → 2^2 → 3^2 ) 빈 공간을 찾는다. 
  • Secondary Clustering 발생
• Double Hashing(이중 해싱) : 2개의 해시 함수를 구현하여 첫 번째 해시 함수에서 Collision이 발생할 경우, 두 번째 해시함수로 다음으로 이동할 폭을 결정한다. 선형 탐사, 제곱 탐사에 비해 건너뛰는 폭의 너비가 불규칙하기 때문에 Clustering 문제가 해결된다. 

Chaining 방식과 다르게 추가적인 메모리 공간을 사용하지 않고, 데이터의 양이 적을 경우 Linear Probing 기법을 사용하여 뛰어난 지역 참조성을 가질 수 있다.

 

결론

데이터 탐색, 삽입, 삭제에 관해 평균적으로 O(1)의 시간 복잡도를 가진다. 하지만 충돌이 발생할 경우 최악의 경우 O(n)의 시간 복잡도가 발생하니 충돌이 발생하지 않도록 해시 함수를 설계하는 것이 중요하다. 데이터에 빠르게 접근할 수 있다는 장점 때문에 캐싱 기법으로 활용된다.

---

참고하면 좋은 사이트

해싱, 해시함수, 해시테이블 · ratsgo's blog

 

[해시] Hash란?