[Hash]35. Hashing

목차

1. Hashing 정의, 기본 개념

2. Hashing 충돌 관리

3. Separate Chaning

4. Linear Probing

5. Double Hashing

 

1. Hashing 정의, 기본 개념

 Hashing은 데이터를 (key, value)화 시켜서 빠르게 저장하고, 빠르게 불러오는 방식을 말합니다. 사실 제가 활용하는 파이썬에서는 이미 딕셔너리가 hashing으로 구현되어 있지만, 그래도 한번 개념을 정리해보고 구현해보도록 하겠습니다.

 Hashing의 최종 목표는 골고루, 공평하게 데이터가 펼져디고록 배분하는 것이 최종 목표 입니다. 만일 정해진 규칙에 의하여 배분하였을 시 뒤에 서술하겠지만 충돌이 발생할 경우, 이를 해결하기 위한 방법을 마련해야 하기 때문입니다.

 

 Hashing의 기본 컨셉은 넓은 저장공간에 데이터를 일정한 규칙으로 저장하는 것으로, 보통 데이터에서 일정한 규칙에 의해 수 k를 뽑아내고, 정해진 수 N에 대하여 kmodN 위치에 데이터를 삽입합니다.

 예를 들어서 전화번호를 저장하는 hash를 설계할 경우, 전화번호의 뒤 네자리를 수 k값으로 지정하고, 전체 hash의 크기를 10000으로 하면, 삽입/찾을 때 마다 kmod10000으로 값을 삽입/찾을 수 있습니다.

 

2. Hashing 충돌 관리

 위에서도 잠깐 언급했지만, Hashing을 사용할 경우, 두 개 이상의 데이터가 한 곳의 저장공간에 몰릴 수 있는 가능성이 생기게 됩니다. 만일에 충돌 관리가 되지 않는다면 중복된 데이터의 손실이 일어나는 큰 에러가 발생할 수 있으므로, 필수적으로 고려해야 합니다.

 Hashing에서의 충돌을 피하기 위한 방법은 정말 다양하지만, 우선 그 중에서 Separate Chaning, Linear Probing, Double Hashing 에 대해 다루어보도록 하겠습니다.

 

3. Separate Chaning

 Separate Chaning 기법은 Hashing에서 충돌이 발생할 경우, 추가적인 메모리를 할당하여 해당 위치에 여러개의 데이터를 linked된 형식으로 저장하는 것을 말합니다. 이 방법은 성능적인 측면에서 꽤나 좋은 모습을 보여주지만, 처음 해당된 hash를 저장하는 배열 외에 추가적인 메모리를 소모한다는 단점이 존재합니다.

 

4. Linear Probing

  Linear Probing(선형 탐색법)은 probe를 활용하여 데이터를 저장하는 방식입니다. 기본적으로 처음 정해져 있는 mod N에 의해 데이터를 삽입하며, 만일에 내가 삽입하고자 하는 자리에 데이터가 존재한다면, 그 옆으로 이동하여 저장하는 방법입니다. 그 옆에도 데이터가 존재한다면, 데이터가 비어져있는 자리까지 이동하여 저장하게 됩니다.

 

 이 방법은 추가적인 메모리를 사용하지 않아도 데이터 누수 없이 저장할 수 있다는 장점을 지니고 있습니다. 하지만, 한번 충돌이 발생하기 시작하면 그 주소를 중심으로 데이터가 밀접화 될 가능성이 높으며, 오른쪽 index의 데이터가 비어있지 않는 한 데이터를 삭제할 때 그 자리에 dummy값을 넣어주어야 한다는 단점이 있습니다.

 

5. Double Hashing

 Double Hashing은 Linear Probing의 단점을 개선한 방법으로, 이름 그대로 hashing을 두번 진행하고, probe을 진행하는 방식을 의미합니다.

  Double Hashing의 기본적인 원리는 다음과 같습니다.

 

1) size N과 2차 해싱에 필요한 값 q를 정한다. (예를 들어 N=13, q=7)

2) 1차 해싱은 h(k) = kmod13

3) 2차 해싱은 d(k) = 7 - kmod7 이다.

4) 우선 1차 해싱값에 접근, 데이터가 존재할 경우 2차 해싱된 값을 더한 위치에 접근한다.

5) 4번을 반복하며, 빈 공간일 경우 데이터를 삽입한다.

 

 Double Hashing의 장점으론, Linear Probing에 비해서 데이터가 덜 군집화된다는 점이 있습니다.