[C++] Hash

해쉬란?

-> 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑(mapping)한 '값' 입니다.

• 키에 대한 해시값을 사용하여 값을 저장하고 키-값 쌍의 갯수에 따라 동적으로 크기가 증가하는 associate array 이다
• 키에 대한 해시값을 구하는 과정을 hashing(해싱)이라고 한다.
• 해시값 자체를 index로 사용하기 때문에 평군 시간복잡도가 O(1) 로 매우 빠르다
  → 해시 태이블의 크기에 상관없이 데이터에 빠르게 접근할 수 있다.
  → 모든 데이터를 살피지 않아도 검색과 삽입/삭제를 빠르게 실행할 수 있다.

 

그리고 첫번째항목인 key를 Value로 변환시키는 함수를 해쉬함수라 한다.

각 키값들은 해쉬테이블이라 하는 곳에 저장되며, 해쉬함수의 결과값의 범위(보통 인덱스)를 버켓(bucket)이라 하며,

한 개의 버켓에 저장될 키 값의 개수를 슬롯(slot)이라 한다. (밑에 체이닝기법에서 설명하겠지만, 해쉬함수의 결과가 동일할 경우, 하나의 버켓에 value값을 여러개 넣을 수 있다.)

만약 해쉬테이블이란 무엇인가..라고 질문을 한다면, key값과 value가 1:1로 연관되는 자료구조 라고 할 수 있다.

 

이렇게 다양한길이의 키값을 고정된 크기인 밸류로 변환시켜주는 함수를 해쉬함수라 한다.

해쉬함수 종류에는 대표적으로 아래의 4가지 방법이 있다.

 

1. Division Method

    -> 입력값을 테이블의 크기로 나누어 계산하는 방식.

        테이블의 크기는 소수일수록 좋다. 소수가 아닐 경우 입력값에 따라 골고루 분포안되고  특정버킷들에 몰릴수 있다.

2. Multiplication Method

    -> 입력값과 0과 1사이의 실수를 곱한값의 정수만 취한것과 2^n승인 정수를 곱한 값을 인덱스로 쓰는 방법

3. Digit Folding

   -> 입력문자열들의 아스키코드값을 전부 합한값을 인덱스로 쓰는 방법

4. Universal Hashing

   -> 무작위 해쉬함수들을 모아놓고, 거기서 임의로 하나 골라서 쓰는 방법

 

 

 

 

 

 

다른 key값으로 동일한 해쉬값이 나오는걸 해쉬충돌(Hash Collision)이라 한다.

해쉬함수를 잘 만들어서 최대한 확률을 떨어뜨리는게 좋지만, 어쩄든 아예 안날수는 없다.

그렇다면 해쉬충돌이 발생하면 어떻게해야할까?

 

1. Chainning 

먼저 Chaining 기법이 있다. 동일한 해쉬값이 나와서 같은 버켓에 value를 저장할 경우, 해당 버켓의 뒤에 이어 붙여버리는것이다. 즉 해당 버켓이 링크드리스트가 되는것이다.

그럴일은 없겠지만, 버켓의 사이즈가 1이라면 원하는 value값을 찾기위한 시간복잡도는 O(n)이 될 것이다. (sequence container 마냥, 하나의 버켓에 그냥 줄줄이 달아버린 모양새가 된다)

사실상 그냥 일반배열에서의 원하는값 탐색과 동일하다고 볼 수 있다. 물론 버켓을 이렇게 설계할 일은 없기 때문에 평균적으로 O(1)이라 상정한다.

 

2. Open Addressing

또다른 방법으로는 Open Addressing이 있다. 충돌이 일어날 경우, 다른 빈공간을 탐색해서 찾아 그 공간에다가 value값을 넣는 방법이다. 탐색방법에도 여러방법이 있는데 선형탐사(Linear Probing), 제곱탐사(Quadratic Probing)가 있다. 

 

선형탐사는 고정된폭을 증가시키며 탐색하는 방법인데, value가 특정구간에 밀집되어버리는 현상(cluster)이 발생하기 쉽다. 따라서 다음에 충돌이 일어났을 경우, 탐색하는 시간이 길어지는 단점이 있다.

 

제곱탐사는 선형탐사와 거의 비슷한데, 단순히 선형적으로 증가시키는게 아니라 제곱한 값을 더하며 탐색하는 방법이다.

버켓2번에서 충돌이 일어났을 경우, 먼저 1의제곱만큼 뒤인 3을 탐색하며, 거기도 값이 이미 있을 경우 3 + 2^2으로 이동해서 검사한다. 7에서도 값이 이미 있을 경우 7 + (3^2)인 16으로 가서 검사한다. 이런식으로 제곱하며 탐색하는 방법이다.

하지만 선형탐색보다 덜할뿐이지 일정한 규칙을 가지고 이동하기 때문에 마찬가지로 군집화현상이 일어날 수 있다.

 

이런 일정한 규칙을 가진 주소이동방식에 의한 군집화현상라는 단점을 보완하기위한 방법중 하나로는

더블해싱이란 방법이 있다. 더블해싱은 두개의 해쉬함수를 이용해서 주소이동의 규칙성을 없앤 방법이다.

식은 다음과 같다.

 

(A(k) + i * B(k)) mod m 

 

여기서 B(k)는 해쉬테이블의 사이즈와 서로소 관계여야 한다. (두 수의 최대공약수는 1이여야 한다는 뜻.)

 

테이블에 데이터가 꽉 차 있을수록 해쉬충돌은 자주 일어나게 되는데, 선형탐사가 가장 많이 실패를 하고 제곱탐사와 더블해싱은 비슷하다고 한다.

 

 

Chaining VS Open Addressing

 

체이닝방식은 오픈어드레싱에 비해 일단 구현이 더 쉽다. 오픈어드레싱처럼 데이터클러스터링현상에 거의 영향을 받지 않기 때문이다. 그리고 인풋데이터가 많아지더라도, 오픈어드레싱처럼 급작스럽게 성능하락이 이루어지지 않고 좀 더 리니어하게 이루어진다.

각 버켓이 링크드리스트형식이기 때문에 삽입,삭제도 적은비용으로 가능하다.

링크드리스트를 사용하는 방식말고도 Red-Black-Tree를 사용하는 방식도 있다. 하지만 트리를 사용하는 방식은 메모리가 많이 필요하다. 버켓의 사이즈가 클 수록 트리를 이용하는 방식이 더 효율적이다. (레드블랙트리 특성상 자체적으로 정렬이 되어 관리되기 때문.)

 

 

 

Open-Addressing 방식은 추가적인 저장 공간이 필요 없으므로 chaining 방식보다 메모리 효율이 높다.
삽입시에도 메모리할당 오버헤드가 없다. 체이닝방식은 리스트로 구현될 경우 리스트자료구조 특유의 (head,tail) 오버헤드가 있기때문에 삽입시에 오버헤드가 있다고 말할 수 있다.

외부에 별도 공간을 필요로 하지 않기 때문에 chaining의 연결 리스트 같은 외부 공간에 필요한 추가적인 작업이 요구되지 않는다. 또한 (특히 linear probing에서) chaining보다 뛰어난 locality of reference(하나의 자원에 여러 번 접근하는 process)를 가진다. 데이터의 크기가 작다면, 특히 lookup에서, 이러한 특성들로 인해 chaining보다 성능이 좋을 수 있는 것이다.


반면에 open-addressing 방식은 큰 데이터를 다뤄야 할 때는 좋지 않은 선택인데, 데이터들이 캐쉬 라인을 채워버릴 것이며(캐쉬의 이득이 없어짐) 많은 공간이 (크기가 큰) 빈 슬롯들에 의해 낭비될 것이다.

정리하자면 open-addressing 방식은 테이블에 모두 저장될 수 있고 캐쉬 라인에 적합할 수 있을 정도로 데이터의 크기가 작을수록 성능이 더 좋아진다. 테이블의 높은 load factor가 예상되거나, 데이터가 크거나, 데이터의 길이가 가변일 때 chained 해쉬 테이블은 open-addressing 방식보다 적어도 동등하거나 훨씬 더 뛰어난 성능을 보인다.