[자료구조] 11-3. 해쉬

지금까지 배워온 탐색, 서치 알고리즘 중에 가장 안정적인 성능을 가진 것이 이진 탐색이었다. O(log n)이 나오는다는 의미를 생각해보면, 데이터의 개수가 10, 100, 1000, 10000...이렇게 증가해 나갈 때 성능은 밑이 10인 로그라고 가정할 때 1 2 3 4...이렇게 증가한다는 것이다.

매우 우수한 성능이지만 이 시간도 데이터의 크기에 의존한다. 데이터가 크면 클 수록 시간도 느려지는 것이다. 현실에서는 자료의 크기에 상관없이 실시간으로 특정 시간 내에 탐색이 수행되어야 하는 경우가 많다.

이용자나 데이터가 아무리 많아도 동일한 시간이 걸리는 즉, O(1)의 탐색 시간을 보장하는 자료구조 및 알고리즘이 해쉬다.

다시 정리하자면, 모든 키의 레코드를 산술 연산에 의해 한 번에 바로 접근할 수 있는 기법이다. 해쉬는 다음의 4가지 요소로 구성되어 있다.

1. 해쉬 함수

2. 해쉬 인덱스

3. 해쉬 테이블

4. 이 때 발생하는 충돌과 그 총돌에 대한 해소

위와 같은 고객 리스트가 있다고 해보자. 전화번호를 이용해 고객 정보에 접근하려고 한다. 이렇게 어떤 레코드에 접근할 수 있는 속성, 다른 레코드와 비교해 특이점(!)을 가지는 속성을 키 애트리뷰트 라고 한다. 그리고 이렇게 값이 저장된 곳을 hash table이라고 한다.

실제 위의 값들은 메모리에 저장되어있고 접근하려면 인덱스가 필요하다.

그리고 그 index에는 key를 가지고 접근한다. 이 키로 테이블에 접근하려면 index가 필요한데, key와 index를 매칭시켜주는 것이 해쉬 함수다. 해쉬 함수는 키를 x값으로 받아서 인덱스를 리턴한다.

그래서 실제로 번호를 입력하면 거기에 해당되는 인덱스를 매칭시켜줄 것이다.

해쉬 함수를 정의하는 데에는 여러 방법이 있다. 그 중 하나는 digit selection 즉, 자릿수 선택이 있다. 자리수 선택은 키 값 중에서 일부의 자릿수만 골라내서 인덱스로 사용하는 것이다.

예를 들어 위의 숫자는 홀수 자리만 선택해서 만들 수 있다. 하지만 이 경우에 충돌이 발생할 수 있다. 충돌이란, 다른 키가 동일한 인덱스에 대응되는 것을 말한다.

또 다른 해쉬 함수로는 자릿수 접기가 있다. 모든 자릿수를 다 더해서 인덱스를 만드는 것이다. 당연히 이 경우도 키는 다르지만 다 더해보니 인덱스 값이 같아지는 충돌이 발생할 수 있다.

세번째로는 사용 빈도가 높은 모듈로 함수가 있다. 어떤 키를 적당한 테이블 사이즈로 나눈 나머지(모듈로 연산)로 인덱스를 만드는 것이다.

예를 들어, 157이 key인 경우 mod 10을 하면 7이 남는다. 이 7이 인덱스가 된다. 하지만 이 경우에도 충돌은 발생할 수 있다.

충돌을 다시 한 번 정리하자면, 다른 키를 가진 인덱스가 해쉬 함수에 의해서 동일한 인덱스로 대응되는 현상이다.

이렇게 다른 숫자여도 모듈러 연산을 하면 같은 인덱스를 갖게 되어 충돌이 일어난다.

그래서 충돌한 레코드를 다른 주소에 저장하는 방법이 있다. 방법에는 두 가지가 있다.

1. open addressing

충돌이 발생한 레코드를 다른 주소에 저장한다. 레코드의 주소가 바뀔 수 있기 때문에 즉, 다른 주소로 찾아가기 때문에 열려있다고 표현한다.

- 선형 탐사

- 제곱 탐사

- 이중 해시

2. closed addressing

충돌이 발생한 레코드를 동일한 주소에 어떻게든 집어넣는다. 새로운 주소를 찾아가는 게 아니므로 닫혀있다고 이야기한다.

- 버켓

- 별도 체인

open addressing의 첫 번째 예제인 선형 탐사를 보자.

선형 탐사는 충돌이 발생하면 다른 빈 곳에 원소를 저장한다. 해쉬 키에 의해서 찾아간 주소가 이미 차있으면 +1인 그 다음 자리로 찾아가는 것이다. 거기에도 원소가 있따면 또 그 다음 자리를 찾아간다. 맨 마지막까지 가면 다시 처음으로 돌아가서 찾는다.

예를 들어 모듈러 31을 해쉬 함수로 사용한다고 해보자. 65를 모듈러 연산 하면 인덱스 3에 저장된다. 

그런데 34도 모듈러 연산을 하면 인덱스 3이 된다.

이 충돌을 해소하기 위해 다음 인덱스에 넣는다.

여기서 또 127을 넣으면 인덱스 3에 해당되는데

3과 4가 차있으므로 5에 저장이 된다.

이렇게 다음 자리로 계속 이동하는 방법을 선형 탐사라고 한다.

다음 자리를 찾아가도록 만드는 포인터를 태그라고 한다. 즉, 선형 탐사에서 다음 원소를 가리키는 포인터이다.

태그는 어떤 자리를 찾아왔을 때 이미 값이 존재한다면 그 다음 원소의 위치를 가리키는 용도로 사용된다.

또 이렇게 태그를 따라간 상황에서 중간에 있는 값이 제거되면, 

그 다음 원소를 가리킬 수 있도록 한다.

선형 탐사의 단점은 클러스터링이다. 클러스터링이란, 이 넓은 메모리 영역에서 한쪽으로 모여있는 현상을 말한다. 클러스터링은 메모리를 효율적으로 사용하지 못하는 문제가 발생한다. 또, 어떤 원소를 찾으려고 할때 순차적으로 접근해야 하므로 O(n)에 가까운 비효율적인 연산을 수행해야 한다.

만약 이와 같은 레코드에서 계속 모듈러 연산을 해서 들어오면 다음 칸, 또 그 다음칸으로 들어올테니 해쉬의 장점이 사라지게 된다.

이 문제를 해결하기 위해 제곱 탐사라는 방법을 사용한다. 충돌이 일어날 때 바로 그 다음 위치가 아니라 조금 간격을 두고 삽입하는 것이다.

만약 h(key)가 점유되어 있다면 h(key)+1, 그 다음은 h(key)+2^2, h(key)+3^2...이 되는 것이다.

예를 들자면, 65는 3에, 34는 그 다음칸에 오지만, 127은 4를 더해서 인덱스 7에 오게 된다.

그리고 또 다음 원소가 들어오면 9만큼 떨어진 곳에 들어가게 된다. 그 다음에 또 들어오면 16만큼 떨어져서 앞까지 돌아온다.

이렇게 하면 데이터가 한 곳에 몰려있는 연속적인 배열을 피할 수 있지만, 그래도 동일한 키를 가진 레코드는 계속 동일한 자리에 삽입되므로 계속 다음 원소를 찾아 들어가야 한다는 문제가 남아있게 된다.

이렇게 궁극적으로는 클러스터링을 피할 수 없어서 2차 클러스터링이 발생한다고 이야기한다.

2차 클러스터링을 피하기 위해 해쉬를 한 번 더 하는 이중 해쉬가 제안되기도 한다. 이중 해쉬는 두 개의 해쉬 함수를 이용한다. 

첫 번째 해쉬 함수(h1)로 인덱스를 계산하고, 그때 충돌이 발생하면 그 다음 얼마나 떨어진 곳에 원소를 집어넣을지는 함수2(h2)를 이용해서 계산하는 것이다.

예를 들어 첫 번째 해쉬는 모듈러 13, 두 번째 해쉬는 모듈로 11을 한다고 생각해보자. 14를 넣으려고 하니 79와 충돌한다.

그래서 h2를 실행하면 4칸 떨어진 곳에 삽입하게 된다. 만약 또 원소가 있다면 다음 칸을 찾아가도록 하면 된다.

하지만 이중 해쉬도 결국 클러스터링 문제를 완벽하게 해소하기는 힘들다. 이미 저장된 곳의 다음 칸, 다음 칸을 찾아가는 방식이 동일하기 때문이다.

이전의 방법을 해결하기 위해 닫힌 어드레싱 방법이 있다. 닫힌 어드레싱은 해쉬 테이블의 각 원소에 여러 개의 값을 저장하는 것이다. 이와 같은 방법을 버켓이라고 한다.

예를 들어 인덱스 3에는 위와 같이 배열을 저장할 수 있도록 만든다. 일종의 2차원 배열같은 것이다. 이 배열 안에 있는 원소 개수를 상수 k로만 유지하면 검색하는 데는 O(k)가 된다. 이는 O(1)과 같으므로 실시간으로 원소를 찾을 수 있는 해쉬 테이블을 제공할 수 있다.

하지만, 이 배열의 크기가 너무 길어지게 되면 그때는 실시간이 의미 없게 된다. 또한, 한 인덱스에 값이 하나만 들어오게 되면, 그 하나만을 저장하기 위해 불필요한 배열 공간을 만들어야 한다는 단점이 있다.

이와 같은 단점을 해소하기 위한 방법으로는 별도 체인이 있다. 해쉬 테이블의 각 원소가 아까와 같은 배열이 아니라 연결 리스트로 표현된다. 그래서 충돌이 발생할 때마다 연결 리스트에 원소를 하나씩 넣어준다. 각 테이블의 원소 크기가 동적으로 변하기 때문에 동적 구조를 갖는다고 말한다.

예를 들어 serious와 funny가 동일한 주소를 갖는다면, 0번의 주소 안에서 연결 리스트로 저장된다.