충돌 없는 완벽한 해싱이 존재한다고 ? (퍼펙트 해싱 개념 및 사례, 최적화 방법에 대해서)

이 글의 탄생 배경, 이 글에 대해서

코딩 스터디 중 해싱 챕터에서 시간 복잡도를 주제로 이야기할 때였다. 해싱하면 연상되는 이미지는 당연히 "빠르다"였고 나는 당연스럽게 O(1)이지! 라고 생각하며 대화를 이어나갔는데, 한 멤버가 질문했다.

"어... 해싱도 최악의 경우는 O(n) 아니에요?"

어라, 순간 멈칫했다. 사실 해싱에서 최악의 경우는 O(n)이라는 걸 깜빡하고 있었다! 자바에서 해싱을 사용할 때는 충돌 문제를 자동으로 처리해주고, 또 key-value 스토어로서 레디스와 같은 저장소를 사용할 때, 단순히 "빠르다"는 이미지에만 노출되어 있다 보니 당연히 해싱은 O(1)이라고 생각했던 것이다. 문득 기억을 환기시키며 깨달았다.

 

앗,,, 해싱은 충돌이 없다면 O(1)이지만, 충돌이 발생하면 O(n)이네!

그런데 바로 다음과 같은 질문이 또 떠올랐다.

"정말 만약에 해싱이 계속해서 충돌을 일으킨다면, 그러면 해싱을 사용하는 의미가 없어지는 거 아니야?"

맞다. 해싱에서 충돌은 피할 수 없고, 충돌이 많아지면 해싱의 효율이 떨어질 수밖에 없다. 그리고 충돌을 해결하는 방법은 대체로 복잡하다. 이 문제를 완전히 해결해서, 일반적으로 생각하는 그 key-value 스토어의 직접 접근 장점만을 취할 수는 없는 걸까?

 

즉, 혹시 충돌을 아예 없애는 방법은 없는 걸까? 이런 질문을 갖고 리서치해본 결과, 퍼펙트 해싱(Perfect Hashing)이라는 개념을 만날 수 있었다. 퍼펙트 해싱은 충돌이 일어나지 않도록 설계된 특별한 해싱 기법이다. 충돌이 없는 해싱이라니, 가능한 것일까?

 

이 글은 퍼펙트해싱에 대해 기본 개념부터 응용 사례까지 탐구해본 내용을 작성한 글이다.

퍼펙트해싱이란?

퍼펙트 해싱(Perfect Hashing)은 해시 충돌을 완벽히 피하기 위해 특별히 설계된 해싱 기법이다. 보통의 해싱에서는 키를 해시 함수에 넣어 계산된 인덱스로 바로 접근하는 방식이다. 이를 통해 Θ(1)을 보장하는 것이다. 속도가 빠른데, 문제는 충돌이다. 두 개 이상의 키가 동일한 인덱스를 가지면 같은 자리에 놓이게 되므로, 해싱의 장점인 빠른 접근이 무색해진다. 체이닝(Chaining)과 오픈 어드레싱(Open Addressing)으로 해싱 충돌을 해결하곤 하지만, 각각의 방식 모두, 충돌이 많아지면 선형적으로 탐색시간이 증가하므로 O(n)으로 귀결된다.

 

퍼펙트 해싱은 특정 데이터 집합에 대해서 적용한다. 여기서 특정 데이터 집합이란 정적 데이터 집합이어야 한다. 이것이 전제이다. 즉, 삽입이나 삭제 없이 한 번 설정되면 변하지 않는 데이터에 대해서, 애초에 모든 데이터가 서로 다른 위치에 매핑되도록 해시 함수를 설계하여 충돌이 아예 발생하지 않도록 하는 것이다. 만약 데이터가 추가되거나 삭제되면 기존 해시 구조가 깨질 수 있어, 퍼펙트 해싱을 할 수 없다.

이게 무슨 말일까? 원리를 살펴보자

퍼펙트 해싱은 기본적으로 2단계 해싱(two-level hashing) 구조로 이루어진다. 이 과정에서 각각의 키가 유일한 위치에 배치될 수 있도록 설계된다.

1. 1차 해싱: 먼저, 모든 키를 큰 해시 테이블에 분산시킨다. 여기까지는 일반적인 해시 함수와 동일하다. 키를 해싱하여 테이블의 특정 버킷에 매핑한다. 하지만 이 과정에서 충돌이 생길 수 있다. 예를 들어, 키 A와 키 B가 같은 해시 값을 가진다면, 두 키 모두 같은 버킷에 위치하게 될 것이다.
2. 2차 해싱: 따라서 중요한 것은 2차 해싱이다. 각 버킷에서 충돌이 발생한 경우, 해당 버킷만을 위한 작은 해시 테이블을 만들어 충돌을 해결한다. 여기서 각 키를 다시 해싱하여 고유한 인덱스에 저장할 수 있도록 조정한다. 1차 해시 함수가 각 키를 버킷으로 나누는 역할을 하고, 2차 해시 함수는 각 버킷 안에서 고유하게 키를 배치하는 역할을 하는 것이다. 이때 2차 해시 함수는 충돌 없이 키를 정확한 위치에 배치할 수 있도록 여러 차례 조정될 수 있다.

어떻게 한다는 것일까? 예시를 들어 살펴보자. 다음과 같은 데이터 집합에 먼저 1차 해싱을 적용해 보자.

• 데이터 집합: ["cat", "dog", "bat", "rat", "hat"]

간단화하기 위해, 각 단어의 첫 번째 문자 ASCII 값을 사용하여 해시 값을 계산한다고 가정한다.

 

1차 해시 함수: h1(x) = ASCII(첫 번째 문자) % 3

데이터	h1(x) 결과 (버킷 번호)
"cat"	ASCII("c") % 3 = 0
"dog"	ASCII("d") % 3 = 1
"bat"	ASCII("b") % 3 = 1
"rat"	ASCII("r") % 3 = 0
"hat"	ASCII("h") % 3 = 2

 

1차 해싱 결과는 다음과 같다.

버킷 0: ["cat", "rat"]
버킷 1: ["dog", "bat"]
버킷 2: ["hat"]

 

이때, 버킷 0과 버킷 1에서 각각 충돌이 발생한 것을 볼 수 있다!

 

이제 충돌이 발생한 버킷에 대해 2차 해싱을 적용한다. 각 버킷에 대해 별도의 해시 테이블을 생성하고, 2차 해시 함수로 충돌을 제거해 보자.

• 버킷 0에 대해: "cat"과 "rat"이 충돌 중이므로, 버킷 내에서 고유한 위치에 배치하기 위해 새로운 2차 해시 함수 h2(x) = ASCII(두 번째 문자) % 2를 적용한다.
  • "cat": h2("cat") = ASCII("a") % 2 = 1
  • "rat": h2("rat") = ASCII("a") % 2 = 1

만약 동일한 결과가 나온다면, 테이블 크기를 늘리거나 해시 함수를 조정하여 충돌이 해소될 때까지 반복한다.

• 버킷 1에 대해: "dog"과 "bat"도 충돌 중이므로 h2(x) = ASCII(두 번째 문자) % 2를 적용하면,
  • "dog": h2("dog") = ASCII("o") % 2 = 1
  • "bat": h2("bat") = ASCII("a") % 2 = 0

이 과정을 통해 충돌이 해결된다. 이제 최종 해시 테이블 구조는 다음과 같다.

버킷 0 (2차 해시 테이블):
  인덱스 0: "cat"
  인덱스 1: "rat"
버킷 1 (2차 해시 테이블):
  인덱스 0: "bat"
  인덱스 1: "dog"
버킷 2 (2차 해시 테이블):
  인덱스 0: "hat"

 

그렇다면 조회는 어떻게 하는 걸까?

 

조회 과정에서는 먼저 1차 해시 함수를 통해 버킷을 찾고, 2차 해시 함수를 통해 최종 위치를 찾는다. 예를 들어 "dog"을 찾는 과정을 살펴보면,

1. 1차 해시 함수로 h1("dog") = 1이므로 버킷 1로 이동
2. 버킷 1의 2차 해시 테이블에서 h2("dog") = 1이므로 인덱스 1에 있는 "dog"를 찾기

정말 이 방식이 유효한 걸까? 만약 "cat"과 "rat"이 2차 해싱에서도 동일한 해시 값을 가지면 어떻게 되는 걸까?

 

위에서 언급한 것과 같이, 말 그대로 충돌이 없는 해시 테이블이 완성될 때까지 2차 해시 함수를 조정하거나 테이블 크기를 늘리는 방식으로 해시 함수를 반복 설계하는 것이다. 예를 들어, "cat"과 "rat" 모두 h2(x) = ASCII(두 번째 문자) % 2로 동일한 해시 값을 가져서 충돌이 발생하면, 버킷의 크기를 두 배로 늘려 더 많은 고유 위치를 확보하는 방식으로 해결한다.

 

버킷 0의 크기를 2에서 4로 늘리고, 새로운 2차 해시 함수 h2(x) = ASCII(세 번째 문자) % 4를 적용해 보자.

• "cat": h2("cat") = ASCII("t") % 4 = 0
• "rat": h2("rat") = ASCII("t") % 4 = 0

이 경우에도 충돌이 발생한다면, 테이블 크기를 다시 늘려 각 데이터를 고유한 위치에 배치할 수 있는 해시 함수를 찾을 때까지 반복한다. 이렇게 반복하면 반드시 다른 해시값이 나오게 되어 있으므로 이론적으로 다른 공간에 배치가 가능하게 된다.

 

그렇게 하여 최종구조가 다음과 같이 나온다.

버킷 0 (2차 해시 테이블):
  인덱스 0: "cat"
  인덱스 2: "rat"
버킷 1 (2차 해시 테이블):
  인덱스 0: "bat"
  인덱스 1: "dog"
버킷 2 (2차 해시 테이블):
  인덱스 0: "hat"

 

따라서, 퍼펙트 해싱은 충돌을 애초부터 방지하는 것이 아니라 충돌이 발생하더라도 충돌이 완전히 해결될 때까지 2차 해시 함수를 조정하는 과정을 거쳐 고유한 위치를 보장하는 기법이라고 할 수 있다. 이러한 방식으로 항상 조회 시간 항상 (O(1)) 조회 시간을 보장한다.

 

단, 정적 데이터 집합에 대해서 말이다.

정적 데이터만 사용할 수 있는 거라고?

그렇다. 퍼펙트 해싱 기법은 정적 데이터 집합에 한정하여 사용할 수 있는 기법이다. 왜 그럴까?

 

퍼펙트 해싱의 핵심은 미리 주어진 데이터에 대해 충돌이 없는 해시 테이블을 만드는 것이다. 데이터가 정적이기 때문에, 모든 키가 고유한 위치에 정확히 배치될 수 있도록 사전에 해시 함수와 테이블 구조를 설계할 수 있는 것이다. 하지만 데이터가 변경된다면, 기존 해시 테이블 구조가 깨져 버리고, 새로운 데이터를 위한 충돌 없는 해시 함수와 테이블을 다시 설계해야 한다. 이렇게 되면 퍼펙트 해싱의 "한 번 설정하면 변경 없이 빠르게 조회"라는 본질이 무너져 버린다. 즉, 반복된 작업으로 고유한 해시값을 배치하는 과정이 실시간 일어나는 과정에서 성능이 말도 못 하게 떨어질 것이므로 쓸 이유가 없어질 것이다.

 

그렇다면 이런 의문이 들 수 있다.

"계속 변경되는 데이터를 처리할 수 없다면, 퍼펙트 해싱이 정말 필요할까? 어디에 사용할 수 있지?"

답은 간단하다. 계속 변경이 안 되는 데이터만 처리하면 되잖아?이다.

 

퍼펙트 해싱은 고정된 데이터를 다루는 상황에서 매우 유용하다. 대표적인 예시가 컴파일러에서 사용하는 예약어 집합이다. 프로그래밍 언어의 예약어는 미리 정해져 있고, 사용자가 새로운 예약어를 추가하거나 삭제하는 일이 없다. 따라서 이와 같은 고정된 데이터 집합에 대해 빠르게 접근할 수 있는 퍼펙트 해싱을 적용하면, 컴파일러는 예약어를 빠르게 조회할 수 있어 성능이 크게 향상된다.

 

또한, 데이터베이스 시스템에서도 특정한 고정 데이터에 대해 퍼펙트 해싱을 사용할 수 있다. 예를 들어, 국가 코드나 화폐 코드처럼 정해진 데이터에 대해 자주 조회하는 경우, 퍼펙트 해싱을 사용한다면 빠른 조회 성능이 보장된다.

 

따라서 퍼펙트 해싱은 고정된 데이터에 대한 조회 성능을 극대화해야 하는 시스템에서 강력한 선택지라고 할 수 있다.

컴파일러의 예약어 세트를 예시로 들어보자

실제 사용 사례를 좀 더 체감해 보기 위해 컴파일러 예약어 세트를 예시로 퍼펙트 해싱의 활용 방법을 좀 더 살펴보자.

 

컴파일러는 프로그래밍 언어의 예약어(keyword)들을 빠르게 판별해야 한다. 예약어는 미리 정해진 단어들이고, 사용자가 임의로 추가하거나 삭제하지 않기 때문에 정적 데이터에 속한다. 이러한 고정된 집합을 빠르게 조회할 수 있는 퍼펙트 해싱이 컴파일러에서 효과적으로 사용될 수 있는 이유다.

 

예를 들어, 다음과 같은 예약어들에 대해,

• 예약어 목록: "if", "else", "for", "while", "return", "int", "float", "double", "char", "struct"

퍼펙트 해싱을 사용하여 이 예약어 집합에 대해 충돌 없이 빠르게 접근할 수 있는 해시 테이블을 만들어보자.

1차 해싱 (1차 해시 함수 적용)

우선 1차 해싱을 통해 각 예약어를 해시 테이블의 버킷으로 나눈다. 예시로 예약어의 첫 번째 문자의 ASCII 값을 테이블 크기로 나눈 나머지를 해시 값으로 계산하는 1차 해시 함수 h1을 사용한다.

• h1(x) = (x의 첫 번째 문자의 ASCII 값) % 5

예약어	ASCII 값 (첫 글자)	1차 해시 값 h1(x)	버킷 번호
"if"	105	105 % 5 = 0	0
"else"	101	101 % 5 = 1	1
"for"	102	102 % 5 = 2	2
"while"	119	119 % 5 = 4	4
"return"	114	114 % 5 = 4	4
"int"	105	105 % 5 = 0	0
"float"	102	102 % 5 = 2	2
"double"	100	100 % 5 = 0	0
"char"	99	99 % 5 = 4	4
"struct"	115	115 % 5 = 0	0

1차 해싱 결과:

• 버킷 0: "if", "int", "double", "struct"
• 버킷 1: "else"
• 버킷 2: "for", "float"
• 버킷 4: "while", "return", "char"

버킷 0, 2, 4에서 충돌이 발생한 것을 볼 수 있다. 이제 2차 해싱을 통해 각 버킷에서 충돌을 제거해 보자.

2차 해싱 (충돌이 발생한 버킷에 작은 해시 테이블 생성)

각 충돌이 발생한 버킷에 대해 별도의 작은 해시 테이블을 만들고, 2차 해시 함수를 적용하여 고유한 인덱스를 배정한다. 예를 들어, 각 예약어의 두 번째 문자의 ASCII 값을 사용하여 충돌을 해소할 수 있는 해시 함수를 만들 수 있다.

• 예시 2차 해시 함수: h2(x) = ASCII(두 번째 문자) % 테이블 크기

버킷 0 (예약어: "if", "int", "double", "struct")

• "if": ASCII("f") % 4 = 2
• "int": ASCII("n") % 4 = 3
• "double": ASCII("o") % 4 = 0
• "struct": ASCII("t") % 4 = 1

이 결과에 따라 버킷 0의 2차 해시 테이블은 다음과 같이 구성된다.

버킷 0 (2차 해시 테이블):
  인덱스 0: "double"
  인덱스 1: "struct"
  인덱스 2: "if"
  인덱스 3: "int"

버킷 2 (예약어: "for", "float")

• "for": ASCII("o") % 2 = 1
• "float": ASCII("l") % 2 = 0

버킷 2의 2차 해시 테이블은 다음과 같다.

버킷 2 (2차 해시 테이블):
  인덱스 0: "float"
  인덱스 1: "for"

버킷 4 (예약어: "while", "return", "char")

• "while": ASCII("h") % 3 = 2
• "return": ASCII("e") % 3 = 1
• "char": ASCII("h") % 3 = 2

충돌이 또 발생하면 테이블 크기를 조정해 해소할 수 있다. 이 과정을 반복해 최종 테이블을 완성하면, 예약어 조회 시 항상 O(1) 시간 복잡도로 접근할 수 있게 된다.

조회 과정

예를 들어, int를 조회하는 과정은 다음과 같다.

1. 1차 해시 함수 h1("int") = 3로 버킷 3으로 이동
2. 버킷 3의 2차 해시 테이블에서 h2("int")를 통해 인덱스 3에 있는 int를 조회
   
   

그렇다면 퍼펙트 해싱도 최적화할 수 있을까?

퍼펙트 해싱은 충돌을 완전히 제거하여 검색 시간을 O(1)로 보장할 수 있지만, 그럼에도 몇 가지 최적화가 가능하다.

 

퍼펙트 해싱이 일반 해싱과 달라지는 지점은 2단계 해싱 부분이다. 하지만 퍼펙트 해싱도 1단계 해싱의 작업이 필요하므로 일반 해싱의 기법이 당연히 사용된다. 따라서 퍼펙트 해싱의 최적화 역시 일반 해싱을 최적화하는 방법과 크게 다르지 않다.

 

이때 최적화의 주요 목표는 각 단계에서 메모리 사용량을 최소화하면서도 충돌 가능성을 확실히 낮추는 것이다.

 

1차 해시 함수의 선택과 테이블 크기 최적화

먼저 1차 해시 함수는 주어진 데이터 집합을 특정 버킷에 고르게 분포시키는 역할을 한다. 일반적으로, 1차 해싱은 유니버설 해싱(universal hashing)을 활용하여 충돌 확률을 줄이는 방식으로 설계한다. 유니버설 해싱은 임의의 해시 함수를 다수 시도함으로써 평균적으로 충돌이 적게 발생하는 해시 함수를 선택하는 방식이다.

"By trying several hash functions from a universal class, we can easily achieve the goal of having no collisions in the secondary tables"

- University of Otago, COSC 242 – Algorithms and Data Structures, Lecture 11: Perfect Hashing. 25p.

 

1차 해시 함수의 선택에서는 테이블의 크기 \( m \)을 데이터 개수 \( n \)의 제곱, 즉 \( m = O(n^2) \)로 설정하는 것이 일반적이다. 이는 충돌 확률을 50% 이하로 낮추기 위한 수학적 근거에 기반한다. 이를 통해 적절한 해시 함수가 선택되면, 모든 버킷 내에서 각 키를 고유하게 분배하는 것이 가능해진다.

 

이와 같은 방식은 이른바 "생일 문제(birthday problem)"에 기반한다. 생일 문제는 확률적으로 두 명 이상이 같은 생일을 가질 가능성이 생각보다 높다는 수학적 원리(23명이 모였을 때 확률은 50% 이상)로, 해시 테이블에서 충돌이 발생할 확률을 분석할 때 자주 사용된다. 해시 테이블의 크기를 데이터 개수의 제곱에 비례하도록 설정하면, 각 키가 동일한 해시 위치에 할당될 확률을 급격히 낮출 수 있다.

 

"The birthday problem ... shows that as the number of keys approaches the square root of the table size, the probability of at least one collision becomes high."

- University of Otago, COSC 242 – Algorithms and Data Structures, Lecture 11: Perfect Hashing. 17p.

 

 

"The analysis shows that for m = n^2, the probability of a collision is less than 0.5, giving us a high likelihood of achieving unique placements."

- University of Otago, COSC 242 – Algorithms and Data Structures, Lecture 11: Perfect Hashing. 22p.

2차 해싱: 버킷 충돌 해소와 부가 테이블 최적화

앞에서 계속 살펴보았듯이, 2차 해싱의 목적은 각 버킷 안에서도 충돌 없는 구조를 만들어주는 것이다.

 

각 버킷에 대해 2차 해싱 함수는 선택된 데이터에 최적화된 방식으로 설계되며, 버킷 크기 \( m_j \)는 충돌 데이터의 개수 \( n_j \)를 기준으로 \( m_j = O(n_j^2) \)로 설정된다. 이러한 설계 방식은 각 버킷이 서로 독립적이기 때문에 충돌이 발생하더라도 해당 버킷만 재설정하면 전체 테이블 구조에 영향을 미치지 않는 장점이 있다.

예를 들어, 1차 해싱에서 각 키가 특정 버킷에 할당되었을 때, 각 버킷에 저장된 키 개수를 \( n_i \)라고 하자. 이때 최적화를 위해 2차 해시 테이블의 크기 \( m_i \)를 \( n_i^2 \)로 설정하는 방법이 자주 사용된다. 예를 들어, 어떤 버킷에 3개의 키가 저장된다면 해당 버킷의 2차 해시 테이블 크기는 \( 3^2 = 9 \)가 된다. 이렇게 설정하면 각 버킷에서 충돌이 완전히 해소될 확률이 높아진다.

“For each slot ( i ), get the secondary hash function ( h_i ) by setting ( m_i = n_i^2 ). This ensures that the secondary hash table for each bucket has enough space to avoid collisions within the bucket.”

- University of Otago, COSC 242 – Algorithms and Data Structures, Lecture 11: Perfect Hashing. 28p.

 

이와 같이, 각 버킷의 2차 해시 테이블이 고유한 해시 함수 \( h_i \)를 사용해 충돌을 해소하도록 설계되므로, 만약 충돌이 발생하더라도 해당 버킷만 재구성하면 된다. 예를 들어, 특정 버킷에 4개의 키가 할당되었다면, 2차 해시 테이블의 크기를 \( 4^2 = 16 \)으로 설정하여 모든 키가 충돌 없이 고유한 위치에 배치될 가능성을 크게 높인다.

요약하자면

한마디로 말해서 퍼펙트 해싱의 최적화는 메모리 사용량과 충돌 최소화의 균형을 유지하며, 확률적 접근을 통해 최적의 해시 함수를 선택하는 전략이라고 할 수 있겠다.

결론

지금까지 퍼펙트 해싱의 개념과 작동 방식, 최적화 방법, 그리고 실제 적용 사례까지 알아보았다.

 

사실 해시 충돌을 완전히 피하면서 빠르게 데이터를 조회할 수 있는 "완벽한 해싱"이 정말 가능할까?라는 질문은, 어쩌면 너무 떼쓰는 질문이었는지도 모른다. 실질적으로 데이터가 동적으로 변하는 환경에서는 충돌 없는 해싱을 완벽히 보장하는 방법이 없다. 하지만 퍼펙트 해싱은 이러한 질문에 조금 다르게 접근한다. 정적 데이터 집합을 전제로, 충돌을 피할 수 있는 해시 함수를 설계하여 "특정 상황"에서는 완벽히 충돌 없는 해싱을 구현할 수 있다는 점이다.

 

퍼펙트 해싱은 컴파일러의 예약어 세트와 같이 변하지 않는 고정된 데이터에 대해 높은 성능을 발휘한다. 이러한 특수한 상황에서는 모든 데이터를 고유한 위치에 배정하여 O(1) 조회 속도를 달성할 수 있다. 즉, 퍼펙트 해싱은 모든 상황에서 "완벽한 해싱"을 보장할 수는 없지만, 정적 데이터 환경에서는 해싱의 이상적인 성능을 실현할 수 있는 강력한 방법이다.

 

 

---

 

reference

• https://en.wikipedia.org/wiki/Perfect_hash_function
• https://en.wikipedia.org/wiki/Birthday_problem
• University of Otago, COSC 242 – Algorithms and Data Structures, Lecture 11: Perfect Hashing. (n.d.). (https://www.cs.otago.ac.nz/cosc242/pdf/L11.pdf)