해시의 원리를 이해하고 문제에서 요구하는 해시 함수를 구현할 수 있습니다.
총 3편으로 준비했습니다.
1. 해시의 개념
2. 해시 함수와 충돌 처리
3. 해시 몸풀기 문제
해시 함수
앞서 언급했던 해시 함수는 어떻게 구현할까요? 이것을 알기 위해서는 해시 함수를 구현할 때 고려할 것들을 알아야 합니다. 사실 코딩 테스트에서 해시 함수를 직접 구현하라는 문제가 나오는 경우는 거의 없습니다. 그리고 파이썬에는 딕셔너리라는 자료형을 제공하는데 이 자료형은 해시와 거의 동일하게 동작하므로 해시를 쉽게 사용할 수 있습니다. 하지만 해시의 원리를 이해하고 딕셔너리를 사용하면 좀 더 효율적으로 딕셔너리를 사용할 수 있으므로 한 번쯤은 해시 개념을 공부하기를 추천합니다.
해시 함수를 구현할 때 고려할 내용
첫 번째, 해시 함수가 변환한 값은 인덱스로 활용해야 하므로 해시 테이블의 크기를 넘으면 안 됩니다. 다음 그림으로 예를 들겠습니다. 현재 해시 함수의 결과는 해시 테이블의 크기인 0과 N – 1 사이의 값을 내야 합니다.
두 번째, 해시 함수가 변환한 값의 충돌은 최대한 적게 발생해야 합니다. 충돌의 의미는 서로 다른 서로 다른 두 키에 대해 해싱 함수를 적용한 결과가 동일한 것을 의미합니다. 다음과 같이 홍길동과 홍길서를 해시 함수에 넣었을 때 둘 다 결괏값이 1이면 저장 위치가 같습니다. 즉, 충돌이 발생합니다.
※ 필자가 충돌이 최대한 적어야 한다라고 이야기한 이유는 충돌이 아예 발생하지 않는 해시 함수는 거의 없기 때문입니다.
자주 사용하는 해시 함수 알아보기
그러면 이제 실제로 자주 사용하는 해시 함수를 알아보겠습니다.
나눗셈법
나눗셈법은 가장 떠올리기 쉬운 단순한 해시 함수입니다. 나눗셈법(Division Method)은 키를 소수로 나눈 나머지를 활용합니다. 이처럼 나머지를 취하는 연산을 모듈러 연산이라고 하며 연산자는 %로 표시합니다. 예를 들어 7%2 = 1입니다. 앞으로 나머지를 취하는 연산은 모듈러 연산이라고 하겠습니다. 나눗셈법을 수식으로 작성하면 다음과 같습니다
x는 키, k는 소수입니다. 아주 간단하죠. 키를 소수로 나눈 나머지를 인덱스로 사용하는 겁니다. 나눗셈법을 그림으로 나타내면 다음과 같습니다.
나눗셈법에 소수가 아닌 15를 사용하면 어떻게 될까?
그런데 왜 소수로 나눌까요? 소수를 사용하는 이유는 다른 수를 사용할 때보다 충돌이 적기 때문입니다. 예를 들어 소수가 아닌 15를 나눗셈법에 적용했다고 해봅시다. 나눗셈법에 적용했다는 의미는 위 식에서 k에 15를 적용한다는 의미입니다. 이때 x가 3의 배수인 경우를 한번 보겠습니다. 다음 그림을 보면 규칙적으로 계속 같은 해시값이 반복되는 것을 알 수 있습니다.
그림을 보면 나눗셈법을 적용하면, x는 3의 배수, k는 15를 적용하면 수식은 h(x) = x mod 15(단, x는 3의 배수)가 됩니다. 이 식을 활용하면 해시값은 3, 6, 9, 12, 0이 반복됩니다. 해시값을 보면 동일한 값들이 계속 반복되며, 이를 해시값이 충돌되었다고 표현합니다. 왜 그럴까요? x가 k의 약수 중 하나인 3의 배수이기 때문입니다. x를 5의 배수로 생각해도 충돌이 많이 발생합니다.
왜 충돌이 많이 발생할까?
이유는 생각보다 간단합니다. N의 약수 중 하나를 M이라고 한다면 임의의 수 K에 대해 M * K = N이 되는 수가 반드시 있습니다. 위 그림에서는 N이 15이고, M이 3인 경우입니다. 3 * 5 = 15이므로 K = 5가 됩니다. 그리고 그림은 K를 주기로 같은 해시값이 반복됨을 알 수 있습니다. 따라서 K는 1과 자신 빼고는 약수가 없는 수, 즉, 소수를 사용하는 것이 좋습니다.
나눗셈법의 해시 테이블 크기는 K
그리고 나눗셈법은 해시 테이블의 크기가 자연스럽게 K가 됩니다. 왜냐하면 K에 대해 모듈러 연산을 했을 때 나올 수 있는 값은 0 ~ (K – 1)이기 때문입니다. 즉, 상황에 따라 아주 많은 데이터를 저장해야 한다면 굉장히 큰 소수가 필요할 수도 있습니다. 아쉽게도 매우 큰 소수를 구하는 효율적인 방법은 아직은 없으며 필요한 경우 기계적인 방법으로 구해야 합니다. 나눗셈법의 단점 중 하나입니다.
곱셈법
이번에는 곱셈법(Multiplication Method)을 알아보겠습니다. 나눗셈법은 때에 따라 큰 소수를 사용해야 하는데 큰 소수를 구하기가 쉽지 않다는 단점이 있었습니다. 곱셈법은 나눗셈법과 비슷하게 모듈러 연산을 활용하지만 소수는 활용하지 않습니다. 곱셈법의 공식은 다음과 같습니다.
m은 최대 버킷의 개수, A는 황금비(Golden Ratio Number)입니다. 황금비는 무한소수로 대략 1.6180339887…이며 이 책에서 계산에는 황금비의 소수부의 일부인 0.6183만 사용했습니다.
※ 황금비는 수학적으로 임의의 길이를 두 부분으로 나누었을 때, 전체와 긴 부분의 비율이 긴 부분과 짧은 부분의 비율과 같은 비율을 뜻합니다.
01단계 키에 황금비를 곱합니다.
02단계 01단계에서 구한 값의 모듈러 1을 취합니다. 쉽게 말해 정수 부분을 버리고 소수 부분만 취합니다. 예를 들어 모듈러 1의 결과가 3.1523이면 0.1523만 취합니다. 소수 부분만 취하기 때문에 0.xxx 형태의 값이 나오게 됩니다.
03단계 02단계에서 구한 값을 가지고 실제 해시 테이블에 매핑합니다. 테이블의 크기가 m이면 02단계에서 구한 수에 m을 곱한 후 정수 부분을 취하는 연산을 통해 해시 테이블에 매핑할 수 있습니다. 02단계에서 구했던 값은 0.xxx의 값이므로 매핑할 테이블의 크기인 m을 곱하면 테이블의 인덱스인 0 ~ (m – 1)에 매치할 수 있습니다.
이처럼 곱셈법은 황금비를 사용하므로 나눗셈법처럼 소수가 필요 없다는 장점이 있습니다. 따라서 해시 테이블의 크기가 커져도 추가 작업이 필요 없습니다.
문자열 해싱
지금까지 알아본 해시 함수는 키의 자료형이 숫자였습니다. 이번에는 키의 자료형이 문자열일 때도 사용할 수 있는 해시 함수인 문자열 해싱을 알아보겠습니다. 문자열 해싱은 문자열의 문자를 숫자로 변환하고 이 숫자들을 다항식의 값으로 변환해서 해싱합니다. 공식은 다음과 같습니다.
※ 다음 함수는 문자열 해싱을 하기 위해 사용하는 polynomial rolling method입니다.
p는 31이고, m은 해시 테이블 최대 크기입니다. 이 수식이 실제 적용되는 과정을 그림과 함께 알아봅시다.
※ p를 31로 정한 이유는 홀수이면서 메르센 소수이기 때문입니다.
※ 메르센 소수는 일반적으로 2N-1 형식으로 표시할 수 있는 숫자 중 소수인 수를 말합니다. 메르센 소수는 해시에서 충돌을 줄이는데 효과적이라는 연구 결과가 있습니다.
01단계 다음 그림은 알파벳 a부터 z까지 숫자와 매치한 표와 키입니다.
02단계 “a”는 매치 표를 보면 1입니다. 따라서 “apple”의 “a”는 1입니다. 그러므로 수식의 s[0] * p0는 1 * 1이므로(31의 0승은 1입니다) 1입니다.
03단계 두 번째 문자열 “p”에 대해 연산을 진행합니다. “p”는 16입니다. 여기에 p1을 곱하면 496입니다.
04단계 이렇게 곱한 값들을 더하면 최종값은 4,990,970입니다. 이를 해시 테이블의 크기 m으로 모듈러 연산해 활용하면 됩니다.
기존에는 키 자체가 숫자였으므로 바로 해시 함수를 적용했지만 키가 문자열이면 각 문자열의 문자들을 적절한 숫자로 변경한 다음 해시 함수를 적용해야 합니다. 이런 변환 과정을 통해 문자열이 키인 데이터에도 해시를 사용할 수 있습니다. 하지만 해시 함수를 적용할 때 중요한 점이 있습니다. 해시 함수를 적용한 값이 해시 테이블 크기에 비해 너무 클 수 있다는 겁니다. 그래서 해시 함수가 내는 결과의 크기를 해시 테이블 크기에 맞도록 하는 작업이 필요합니다. 그림을 보면 “apple”이라는 간단한 문자열을 해싱했는데도 결괏값은 4,990,970으로 굉장히 큽니다. 오버플로가 발생시킬 여지가 있으므로 다음 연산 법칙을 활용해 문자열 해시 함수를 수정할 수 있습니다.
문자열 해시 함수 수정하기
덧셈을 전부한 다음 모듈러 연산을 하는 왼쪽 수식 대신, 오른쪽 수식처럼 중간 중간 모듈러 연산을 해 더한 값을 모듈러 연산하면 오버플로를 최대한 방지할 수 있습니다.
※ 두 수식의 실제 결과는 같습니다.
이를 활용해서 앞서 본 문자열 해싱 공식을 수정하면 다음과 같습니다.
해시 함수뿐 아니라 보통 수식에 모듈러 연산이 있는 문제 중 큰 수를 다루는 문제는 이런 오버플로 함정이 있는 경우가 많습니다. 난이도가 높은 문제는 대부분 이런 함정을 포함하고 있으니 이번 기회에 제대로 기억해두기 바랍니다.
충돌 처리
앞서 자주 언급했던 것처럼 서로 다른 키에 대해서 해시 함수의 결괏값이 같으면 충돌(Collision)이라고 합니다. 하나의 버킷에 2개의 값을 넣을 수는 없으므로 해시 테이블을 관리할 때는 반드시 충돌 처리를 해야 합니다.
그림을 보면 두 키는 서로 다르지만 해시 함수를 적용해 해시값이 17이 나왔습니다. 이렇게 되면 해시 테이블의 같은 위치를 나타내므로 충돌이 발생합니다. 여기서는 이런 충돌이 발생하면 어떻게 처리해야 하는지 알아보겠습니다.
체이닝으로 처리하기
체이닝은 해시 테이블에 데이터를 저장할 때 해싱한 값이 같은 경우 충돌을 해결하는 간단한 방법입니다. 체이닝은 충돌이 발생하면 해당 버킷에 링크드리스트로 같은 해시값을 가지는 데이터를 연결합니다.
※ 링크드리스트(linked list)는 데이터 요소들을 연결하여 구성한 선형 데이터 구조입니다.
그림을 보면 키 B와 C를 해싱했을 때 3입니다. 즉, 해시 테이블의 같은 위치를 가리키므로 데이터를 저장할 때 충돌이 발생합니다. 이때 체이닝은 링크드리스트로 충돌한 데이터를 연결하는 방식으로 충돌을 해결합니다. 이후 어떤 데이터가 해시 테이블 상 같은 위치에 저장되어야 하면 이런 방식으로 데이터를 저장합니다. 이처럼 체이닝은 충돌을 링크드리스트로 간단히 해결한다는 장점이 있지만 2가지 단점이 있습니다.
해시 테이블 공간 활용성이 떨어짐
충돌이 많아지면 그만큼 링크드리스트의 길이가 길어지고, 다른 해시 테이블의 공간은 덜 사용하므로 공간 활용성이 떨어집니다.
검색 성능이 떨어짐
충돌이 많으면 링크드리스트 자체의 한계 때문에 검색 성능이 떨어집니다. 링크드리스트로 연결한 값을 찾으려면 링크드리스트의 맨 앞 데이터부터 검색해야 하기 때문입니다. 다음 그림을 보면 맨 뒤의 키 K에 해당하는 값을 검색하려면 B, C, K를 거쳐 확인해야 합니다. 만약 N개의 키가 있고 모든 키가 충돌하여 체이닝되었다면 마지막 버킷을 검색하는 경우 시간 복잡도는 O(N)입니다.
개방 주소법으로 처리하기
개방 주소법(Open Addressing)은 체이닝에서 링크드리스트로 충돌값을 연결한 것과 다르게 빈 버킷을 찾아 충돌값을 삽입합니다. 이 방법은 해시 테이블을 최대한 활용하므로 체이닝보다 메모리를 더 효율적으로 사용합니다.
선형 탐사 방식
선형 탐사(linear probing) 방식은 충돌이 발생하면 다른 빈 버킷을 찾을 때까지 일정한 간격으로 이동합니다. 수식은 다음과 같습니다.
※ 보통 간격은 1로 하는 것이 일반적입니다.
m은 수용할 수 있는 최대 버킷입니다. 선형 탐사 시 테이블의 범위를 넘으면 안 되므로 모듈러 연산을 적용한 겁니다. 수식을 그림으로 표현하면 다음과 같습니다.
키5에 해시 함수를 적용하면 값2가 있는 위치 정보를 참조하므로 충돌이지만 선형 탐사 방법으로 1칸씩 아래로 내려갑니다. 값3, 값4를 지나 그다음 위치에 값5를 넣습니다. 하지만 이 방법도 단점이 있습니다. 충돌 발생 시 1칸씩 이동하며 해시 테이블 빈 곳에 값을 넣으면 해시 충돌이 발생한 값끼리 모이는 영역이 생깁니다. 이를 클러스터(Cluster)를 형성한다고 하는데요, 이런 군집이 생기면 해시값은 겹칠 확률이 더 올라갑니다.
※ 그래서 이를 방지하기 위해 제곱수만큼 이동하며 탐사하는 방법도 있습니다.
이중 해싱 방식
이중 해싱 방식은 말 그대로 해시 함수를 2개 사용합니다. 때에 따라 해시 함수를 N개로 늘리기도 합니다. 두 번째 해시 함수의 역할은 첫 번째 해시 함수로 충돌이 발생하면 해당 위치를 기준으로 어떻게 위치를 정할지 결정하는 역할을 합니다. 예를 들어 보겠습니다. h1이 1차 해시 함수, h2가 2차 해시 함수입니다.
수식을 보면 선형 탐사와 비슷하게 더하는 방식으로 데이터의 위치를 정하지만 클러스터를 줄이기 위해 m을 제곱수로 하거나 소수로 합니다. 이는 주어지는 키마다 점프하는 위치를 해시 함수로 다르게 해서 클러스터 형성을 최대한 피하기 위함입니다.
지금까지 해시에 대해 알아봤습니다. 솔직히 말하자면 해시 함수 자체를 구현하라는 문제는 나오지 않을 가능성이 높습니다. 그렇다고 지금까지 공부한 개념이 중요하지 않은 건 아닙니다. 해시는 IT 기업에 입사하려면 당연히 알고 있어야 할 기본 지식이므로 이참에 한번 정리하기 바랍니다. 면접에서 해시 관련 질문이 나와도 이 정도 수준으로 공부하면 충분히 대답할 수 있을 겁니다. 실제 코딩 테스트 문제에서 해시 문제의 핵심은 키와 값을 매핑하는 과정입니다. 특정 값이나 정보를 기준으로 빈번한 검색을 해야 하거나 특정 정보와 매핑하는 값의 관계를 확인해야 하는 작업이 문제에 있으면 해시를 고려해야 합니다.
자료구조, 알고리즘, 빈출 100 문제로 대비하는 코테 풀 패키지
[되기] 코딩 테스트 합격자 되기(파이썬 편)
저자 박경록
매일 퇴근과 점심 메뉴를 고민하는 9년차 시스템 S/W 개발자입니다. 수학, 알고리즘 같은 실생활과 가깝고도 먼 학문을 좋아하고, 명확하지만 개선 여지가 있는 문제들에 대해 논의하고 사고를 개선해 나가는 과정을 좋아합니다.
