· 개발

해시 테이블은 언제 O(1)이 아닐까: 충돌, O(n²) 삽입, 해시 플러딩

dict와 HashMap의 O(1)은 기댓값입니다. 키의 해시가 모두 같으면 n개 삽입에 비교가 최소 n(n−1)/2번 필요한 이유, Python 해시 무작위화와 PYTHONHASHSEED, Rust SipHash, Java의 Comparable 대응을 정리했습니다.

개발알고리즘자료구조보안

해시 테이블의 조회와 삽입은 O(1)이라고 배웁니다. 공식 문서를 보면 이 말에는 조건이 붙어 있습니다.

Rust 표준 라이브러리의 컬렉션 비용 표는 HashMap의 get과 remove를 O(1)~, insert를 O(1)~*로 적습니다. ~는 기대(expected) 비용, *는 상각(amortized) 비용이라는 표시입니다. 확률적으로 드물지만 기대 비용보다 훨씬 나빠질 수 있다는 단서도 달려 있습니다. Java SE 21의 HashMap 문서는 get과 put이 상수 시간이라고 하면서 “해시 함수가 원소를 버킷에 고르게 흩어 놓는다고 가정하면”이라는 조건을 붙입니다.

그 가정이 깨지면 무슨 일이 생기는지, 그리고 누군가 일부러 깨뜨리려 할 때 언어 런타임이 어떻게 막는지 정리합니다. 문서 기준은 Python 3.15 문서(2026년 10월 10일 갱신), Rust 1.99.0 문서, Java SE 21 API 문서입니다.

해시가 같으면 남는 수단은 비교뿐이다

해시 테이블은 키의 해시값으로 저장 위치를 정합니다. 해시값이 다르면 두 키는 같을 수 없으니 바로 건너뛸 수 있습니다. 해시값이 같으면 해시만으로는 구별이 안 되므로 키끼리 직접 같은지 비교해야 합니다. Python 데이터 모델 문서가 요구하는 성질도 한쪽 방향뿐입니다. 같다고 비교되는 객체는 해시값이 같아야 한다는 것이고, 해시값이 같다고 같은 객체라는 보장은 없습니다.

극단적인 경우를 생각해 봅시다. 서로 다른 키 n개의 해시값이 모두 같다고 합시다.

  • k번째 키를 넣을 때 테이블에는 이미 k−1개의 키가 있고, 모두 해시값이 같습니다.
  • 새 키가 이미 있는 키인지 판정하려면 그 k−1개와 하나씩 비교해야 합니다. 비교하지 않고 넘어간 키가 하나라도 있으면, 그 키가 새 키와 같을 가능성을 배제할 수 없습니다.
  • 따라서 n개를 다 넣는 데 필요한 비교는 최소 0 + 1 + … + (n−1) = n(n−1)/2번입니다.

이 하한은 n이 1,000이면 499,500번, 10,000이면 49,995,000번입니다. 입력이 10배 늘면 하한은 약 100배로 커지는 Θ(n²)입니다. 조회도 마찬가지입니다. 같은 해시·동등 비교 모형에서 없는 키를 찾으면 동등 비교를 최소 n번 한 뒤에야 “없음”이 나옵니다. 위 논증은 키에 대해 해시와 동등 비교만 쓸 수 있다는 전제에서 나온 것입니다. 아래에서 볼 Java처럼 키 사이의 대소 순서를 추가로 쓸 수 있으면 이 논증을 그대로 적용할 수 없습니다.

Python에서 이 상황은 __hash__를 상수로 돌려주기만 하면 만들 수 있습니다.

class Key:
    eq_calls = 0

    def __init__(self, v):
        self.v = v

    def __hash__(self):
        return 42  # 모든 키의 해시값이 같다

    def __eq__(self, other):
        Key.eq_calls += 1
        return isinstance(other, Key) and self.v == other.v

n = 1000
d = {Key(i): i for i in range(n)}
print(Key.eq_calls, n * (n - 1) // 2)

위 논증은 __eq__ 호출 수의 하한을 줍니다. CPython이 정확히 몇 번 부르는지는 dict 구현에 달린 문제라 이 글에서는 숫자를 단정하지 않습니다. 직접 실행해 두 값을 비교해 보면 됩니다. 실무 코드에서 이런 __hash__를 쓰면 정확성은 유지되지만 dict와 set이 리스트처럼 느려집니다. Python 문서는 비교에 쓰는 속성들을 튜플로 묶어 hash((self.name, self.nick, self.color))처럼 해시하라고 권합니다.

입력을 고를 수 있는 쪽이 공격자일 때

상수 해시는 실수로 생기는 문제입니다. 더 곤란한 경우는 해시 함수 자체는 멀쩡한데 입력을 바깥에서 고를 수 있을 때입니다. 키를 정하는 쪽이 해시값이 같은 서로 다른 키를 대량으로 만들어 낼 수 있다면, 서버가 그 키들을 dict에 담을 때 앞에서 본 상황이 그대로 생깁니다. 위의 모형에서는 최소 n(n−1)/2번의 동등 비교가 필요합니다. 이런 공격을 해시 플러딩이라고 하고, Rust 문서는 HashDoS라는 이름으로 부릅니다.

Python 문서는 해시 무작위화를 설명하면서 그 목적을 “dict 삽입의 최악 성능인 O(n²)을 노리고 신중하게 고른 입력이 일으키는 서비스 거부를 막기 위한 것”이라고 적고, 2011년 oCERT 권고(oCERT-2011-003)를 참고 링크로 겁니다.

Python: str과 bytes의 해시에 비밀 값을 섞는다

Python 3.3부터 해시 무작위화가 기본으로 켜져 있습니다. 문서에 따르면 str과 bytes의 __hash__() 값에는 예측할 수 없는 무작위 값이 “솔트”로 섞입니다. 한 프로세스 안에서는 값이 변하지 않지만, Python을 다시 실행하면 달라집니다. 공격자가 서버 프로세스의 비밀 값을 모르면 충돌하는 문자열을 미리 계산해 둘 수 없다는 발상입니다.

이 동작은 PYTHONHASHSEED 환경 변수로 바꿀 수 있습니다.

  • 설정하지 않거나 random이면 무작위 시드를 씁니다.
  • 0부터 4294967295까지의 10진 정수를 주면 그 값을 고정 시드로 씁니다. 문서가 드는 용도는 인터프리터 자체 테스트처럼 해시를 재현해야 할 때, 여러 Python 프로세스가 해시값을 공유해야 할 때입니다.
  • 0을 주면 해시 무작위화가 꺼집니다.

테스트 결과를 재현하려고 넣은 PYTHONHASHSEED=0이 운영 환경 설정까지 따라 들어가면 위의 방어가 사라집니다. 고정 시드도 그 값이 알려지면 같은 처지가 됩니다.

무작위화에는 부작용도 있습니다. 해시값이 바뀌면 set의 순회 순서가 바뀝니다. Python 문서는 set의 순서를 보장한 적이 없고, 32비트와 64비트 빌드 사이에서도 흔히 다르다고 적습니다. 실행할 때마다 set 출력 순서가 다르다면 버그가 아니라 이 기능 때문입니다. 사용 중인 문자열 해시 알고리즘의 이름은 sys.hash_info.algorithm으로 확인할 수 있습니다(3.4부터).

정수 키는 무작위화 대상이 아니다

문서가 솔트 대상으로 적는 타입은 str과 bytes입니다. 숫자의 해시는 별도 규칙으로 정해져 있습니다. 유리수 해시는 고정된 소수 P로 나눈 나머지로 정의되고, CPython은 C long이 64비트인 환경에서 P = 2**61 − 1을 씁니다(sys.hash_info.modulus). 음수는 부호를 붙이고, 결과가 −1이면 −2로 바꿉니다.

정수는 분모가 1인 유리수이므로 이 규칙을 그대로 적용하면 음이 아닌 정수 m의 해시는 m mod P입니다. 그러면 64비트 CPython에서 다음이 성립합니다.

import sys

P = sys.hash_info.modulus      # 64비트 CPython에서 2**61 - 1
assert hash(P) == hash(2 * P) == hash(3 * P) == 0
assert hash(-1) == -2

P의 배수는 모두 해시가 0이고, 이 값은 실행할 때마다 바뀌지 않습니다. 정수 키로 dict를 채우는 코드에 바깥 입력이 그대로 들어간다면 해시 무작위화가 지켜 주지 않는다는 뜻입니다. 이런 경우에는 아래에서 다룰 키 개수 제한이 방어 수단 중 하나가 됩니다.

Rust: 기본 해셔가 HashDoS를 염두에 두고 골라져 있다

Rust 1.99.0 문서에 따르면 HashMap의 기본 해시 알고리즘은 HashDoS 공격에 저항하도록 고른 것이고, 무작위 시드를 씁니다. 시드는 호스트가 제공하는 안전한 난수원에서 만들도록 최선을 다하지만, 부팅 직후처럼 시스템 엔트로피가 비정상적으로 적을 때 만든 시드는 품질이 낮을 수 있다고 문서가 직접 경고합니다.

현재 알고리즘은 SipHash 1-3이며 언제든 바뀔 수 있다고 명시되어 있습니다. 문서는 정수처럼 작은 키나 긴 문자열처럼 큰 키에서는 다른 알고리즘이 더 빠르지만, 그런 알고리즘은 대개 HashDoS를 막아 주지 않는다고 덧붙입니다. 속도를 위해 해셔를 바꿀 때는 키를 바깥 입력이 정하는지 먼저 따져야 한다는 이야기입니다.

Java: 동점을 가르는 데 키의 순서를 쓸 수 있다

Java SE 21의 HashMap 문서는 hashCode()가 같은 키를 많이 쓰는 것은 어떤 해시 테이블이든 느리게 만드는 확실한 방법이라고 적습니다. 그 영향을 줄이기 위해 키가 Comparable이면 키 사이의 비교 순서를 써서 동점을 가르는 데 도움을 받을 수 있다(may)고 설명합니다.

앞에서 n(n−1)/2라는 하한은 동등 비교만 쓸 수 있다는 전제에서 나왔습니다. Java 문서는 비교 순서를 쓸 수 있다는 것까지만 말하고, 어떻게 쓰는지는 설명하지 않습니다. String은 Comparable<String>을 구현하므로 이 처리의 대상이 될 수 있습니다. 문서가 “may”라고 쓴 만큼 실제로 쓰이는 조건이나 비용 상한은 API 계약이 아닙니다.

코드에서 확인할 것

  • 사용자 정의 __hash__는 비교에 쓰는 필드 전부를 튜플로 묶어 해시합니다. 상수나 일부 필드만 쓰는 해시는 충돌을 늘립니다.
  • Python 운영 환경에 PYTHONHASHSEED=0이나 알려진 고정값을 두지 않습니다. set의 순회 순서에 기대는 코드도 쓰지 않습니다.
  • Python의 정수 해시는 무작위화되지 않습니다. 바깥 입력이 정하는 정수 키에는 요청이나 자원 사용에 알맞은 제한을 둡니다.
  • Rust에서 기본 해셔를 더 빠른 것으로 바꾸기 전에 키가 신뢰할 수 없는 입력에서 오는지 확인합니다.
  • 요청 하나가 바깥 입력으로 만들 수 있는 키 개수를 제한하면 공격자가 일으킬 수 있는 작업량도 제한됩니다. 요청이나 자원 사용에 알맞은 한도를 정해 둡니다.

해시 함수 자체의 성질과 암호학적 해시의 차이는 해시 함수란 무엇인가에서 다뤘습니다. 평균과 최악이 크게 갈리는 다른 예로는 퀵 정렬이 O(n²)이 되는 경우가 있고, 표의 * 표시가 뜻하는 상각 비용은 동적 배열과 상각 시간에서 설명했습니다.

블로그로