[자료구조] 해시(Hash)

해시

이번에는 해시, 해시테이블에 대해서 알아보자

이전에 배웠던 자료형들은 값을 여러가지 형태로 저장할 수 있었다.

그러나 원하는 자료형을 찾기란 쉽지않다. 예를들어 리스트에서 원하는 값을 찾기 위해서는 앞에서부터 순서대로 순회해야하며, 힙의 경우에서도 최소값, 최대값을 찾을 수 있을 뿐, 원하는 값을 찾을 수는 없다.

 

그래서 이번에 배울 자료형인 해시는 색인이 쉽게 만들어 졌다.

 

해시의 원리

해시는 값과, 이 값을 찾기위한 key를 사용한다.

파이썬의 딕셔너리와 비슷하다고 생각할 수 있는데, 딕셔너리도 해시로 이루어져있다.

 

가장 먼저 키를 해시함수에 입력한다. 해시함수는 키를 입력받아서 숫자로된 인덱스를 결과로 내는 함수이다.

해시함수의 출력으로 인덱스가 나오면 리스트와 비슷한 자료형 테이블의 인덱스 위치에 값을 저장한다.

리스트에서도 인덱싱의 시간복잡도는 O(1)이므로 키를 이용해서 인덱스를 찾을 수 있다면 빠른 시간 안에 원하는 값을 찾을 수 있다.

 

위 그림을 예로 들면 '김가나'라는 Key를 해시 함수에 입력했을 때 나오는 출력값은 05이고, 이 숫자를 이용해 Value를 찾을 수 있다. 

 

해시 충돌

해시함수도 적절한 알고리즘을 통해 구현되는 만큼 모든 경우에 대응할 수 없다.

서로 다른 Key임에도 불구하고 해시 함수의 결과값이 같은 경우가 있을 수 있는데, 이를 '해시 충돌'이라고 한다.

체이닝

해시 충돌이 일어났을 경우 해당 인덱스에 선형적으로 자료를 연결하는 방법이다.

이 방법은 쉽게 구현할 수 있고, 유연하다는 장점이 있으나, 하나의 인덱스에 쌓이는 데이터가 많아질 경우

데이터를 찾을 때 까지 다시 O(N)의 시간이 걸리게 된다.

 

개방 주소법

해시 충돌이 일어났을 때, 해시 테이블에 빈 공간이 있을 경우 그 공간에 값을 할당하는 방법이다.

'최사아'라는 키가 들어왔을 때, 5번 인덱스에는 값이 있으므로, 다음 인덱스를 찾고, 6번에도 있으므로 다음 인덱스인 7번에 저장된다.

이렇게 인덱스를 옮겨가는 방법은 보통 세 가지라고 한다.

선형탐색: 정해진 간격(위의 경우에는 1)만큼 이동하면서 빈공간을 탐색한다.

제곱탐색: 제곱값의 간격에 따라서 검색하면서 찾는다. (1, 4, 9, 16, ...)

이중해싱: 두개의 해시함수를 적용하여 첫번째 해시함수는 인덱스를 찾는데 사용하고, 충돌이 일어났을 경우 두번째 해시함수를 사용하여 이동할 거리를 계산한다. 

 

선형탐색과 제곱탐색의 경우 테이블의 가까운 공간에 값이 밀집되는 현상(클러스터링)이 발생할 수 있다. 이는 비효율적이다.

이중해싱의 경우 연산량이 늘어난다는 단점이 있다.

 

해시 함수 개선

충돌할 가능성을 줄이는 해시함수를 만드는 것도 하나의 방법이 될 수 있다.

많은 해시 함수들이 있겠지만, 가장 기본적인 나눗셈법과 곱셈법을 알아보자.

 

나눗셈법

숫자로 된 키 K를 해시 테이블 크기 m으로 나눈 나머지를 인덱스로 하는 방법.

계산이 빠르다.

해시 충돌을 방지하기 위해서 m은 대부분 소수를 사용한다. 메모리 낭비문제 때문에 2의 제곱수는 사용하지 않는다.

 

곱셈법

숫자로 된 키 K와 0<A<1을 만족하는 A에 대해서 KA의 소수점 이하 부분에 테이블의 크기 m을 곱하는 방법이다.

어느 m에서도 잘 작동하나, 대부분 2의 제곱수를 선택한다고 한다. 

A값의 선택도 중요하다.

나눗셈법 보다는 조금 느리다.

 

로드 팩터와 리해싱

테이블의 크기를 정해놓고 시작하기 때문에 자료가 다 찰 경우 테이블을 새로 작성해주어야 한다.

로드 팩터란 '(저장된 데이터의 수) / (테이블 크기)'를 표현하며, 언어마다 정해진 로드팩터가 넘을 경우 테이블을 새로 만들어 준다.

 

파이썬의 딕셔너리의 경우 선형탐색법을 기반으로 충돌을 해결하는데, 로드팩터를 낮게 잡아서 빠르게 다음 테이블로 리프레싱 하는 방법을 사용한다고 한다.