서론
코드포스를 참가하다보면 라운드 중일 때에는 Accept 떠서 기분좋게 다른 문제 풀러 갔지만, 시스텟 돌 때 TLE가 터지는 경우가 어떤 자료구조를 사용하면 99% 있다.
이유는 바로 해시 저격 때문이다.
우리는 해시 맵의 조회, 삭제, 삽입 연산이 $O(1)$이라고 알고 그렇게 사용해왔다. 하지만 이는 평균 시간복잡도이지 최악의 경우 $O(1)$을 보장해주지 못하고 $O(n)$이 된다. 파이썬에서 해시를 사용하는 dict와 set은 물론이고 collections의 Counter와 defaultdict 역시 해시 저격에 안전하지 않다.
본론
해시 저격이 가능한 이유는 해시 충돌이 생기기 때문이다.
먼저 해시 충돌에 대해 설명해보자면,,,
해시는 임의의 데이터를 고정된 크기의 값으로 변환해주는 과정이다. 해싱을 이용한 방법에서는 키 $k$를 갖는 원소는 위치 $h(k)$에 저장된다. 즉 키로부터 저장될 위치를 계산하기 위해 해시 함수 $h$를 사용하고, $h(k)$를 키 $k$의 해시 값이라고 한다. 여기서 $h$는 키들의 전체 집합 $U$를 해시 테이블 $T[0:m-1]$의 각 위치에 대응시킨다. 이때 해시 테이블의 크기 $m$은 일반적으로 $|U|$보다 훨씬 작다. 때문에 서로 다른 키이지만 같은 해시 값을 같는 해시 충돌이 발생하게 된다.
$k1 \neq k2$를 만족하며 $h(k1) = h(k2)$인 경우
해시 충돌을 해결하기 위해 사용하는 것이 체이닝(chaining)과 개방 주소법(open addressing)이다. 체이닝 기법은 같은 해시 값을 가진 데이터를 연결 리스트로 관리하는 것이고, 개방 주소법은 충돌 시 해시 테이블의 빈 공간을 찾아 재배치를 하는 것이다.
만약 누군가 동일한 해시 값을 가지는 데이터만을 집어넣는다면 계속해서 해시 충돌이 발생하고 $O(1)$을 보장하지 못하는 상황이 생겨버린다.
핵 방법(?)
CPython에서 정수의 해시 함수는 Identity funtion(정수 그 자체가 해시)이다. 그리고 개방 주소법을 사용하여 해시 충돌을 해결한다. 개방 주소법에서도 다음 버킷을 찾는 방법이 여러 가지 있는데, 그중 파이썬은 더블 해싱 방법을 사용한다. 더블 해싱 말고도 선형 조사가 있는데, 이는 다음 버킷을 찾기 위해 바로 다음 버킷을 차례대로 탐색해나간다.
더블 해싱은 보조 해시 함수를 사용하여 다음 버킷을 찾는다.
CPython dict 구현 코드를 보자.
mask, perturb, i 값을 세팅한다. 이때 mask는 딕셔너리에서 사용된 키의 개수를 따라 결정되는데, CPython에는 2^k * 3 / 2 >= len(dict)를 만족하는 k에 대해 mask = 2^k - 1이다. 그리고 i = (size_t)hash & mask로 해시 값의 하위 비트를 사용해 초기 인덱스를 계산한다. 이제 for 루프를 통해 해시 테이블을 반복적으로 탐색한다. 해시 충돌이 발생하면 perturb 값을 오른쪽으로 시프트하여 업데이트 하고, i를 다시 계산하는데 이때는 i = mask & (i * 5 + perturb + 1) 이다.
(for 루프 안에 중복된 코드가 보이는데 이는 루프 언롤링 기법으로 반복문의 제어 오버헤드를 줄여 실행 속도를 향상시기 위한 기법이다)
딕셔너리가 특정 크기일 때 해시 값이 같은 mask 값을 갖는 두 정수 x와 y를 찾는다. ($x \& mask = y \& mask$를 만족하며 $x \neq y$ 인 값). 이제 y를 먼저 딕셔너리에 넣고, 그 다음 x가 자리를 찾아가는 경로에 있는 값들을 순서대로 삽입한다. 딕셔너리에 이 값들을 모두 채워놓으면 x를 키로 접근할 때 해시 테이블을 모두 탐색해야 하므로 $O(N)$의 시간이 걸린다.
대안
만약 해시 기반 자료구조를 사용하고 싶으면 어떻게해야 할까. set을 사용해서 중복을 제거하고 싶은 경우라면?? 예를 들어 nums 리스트에는 $1 \le num \le 10^6$ 범위의 수가 있고, 이 수들의 중복을 제거하고 싶다.
그럴 때에는 list를 사용하자. 길이가 $10^6 + 1$ 인 list를 생성하고 nums를 돌면서 배열 인덱스로 접근하여 원하는 작업을 수행하면 된다.
중복 제거
카운터(Counter)
방문처리 (visited)
가끔 bfs에서 set을 사용해서 방문처리 하는 코드를 보았다.
둘다 st에서 출발해 bfs를 수행하여 ed에 도착여부를 판단하는 코드이다. 차이는 방문처리를 할 때 set을 사용했냐 아니면 list를 사용했냐이다. 시간복잡도는 둘다 동일하다. 이는 방문처리 코드인 visited.add(nxt)와 visited[nxt] = True의 시간복잡도가 O(1)으로 동일하고, 방문확인 코드인 nxt not in visited와 not in visited[nxt]의 시간복잡도가 O(1)으로 동일하기 때문이다.
하지만 실행시간을 확인했을 때, 대부분 list를 사용하여 방문처리한 코드의 속도가 더 빨랐다. set의 해시접근과 list의 인덱싱 모두 시간복잡도는 O(1)이지만 물리적인 시간은 인덱싱이 더 빠르기 때문이다. 해시접근은 우선 해시연산을 수행하고 해시 테이블에서 값을 조회하는 반면, 인덱싱은 해시연산 필요없이 단순히 list의 인덱스에 접근하면 되기 때문이다.
난죽어도해시를써야겠다
진짜 꼭 필요한 경우라면 str로 감싸서 사용하자. 정수는 Identity funtion이지만 문자열은 Identity funtion이 아니며 또 매 실행마다 해시 값이 다르다. 이는 실행마다 해시 시드가 다르기 때문인데, 해시 충돌 공격을 방지하고자 설계되었다. 때문에 정수를 사용했을 때보다 해시 저격 당할 확률이 낮아진다.
자바는 어떻게 될지 궁금해서 봤는데 자바는 여러번 실행해도 해시값은 동일했다.
추측컨데 자바에서는 체이닝을 사용하지만 일정 비율을 넘어가면 Linked List에서 RB Tree라는 쓰껄한 자료구조를 사용하기 때문에 해시 충돌이 발생하여도 $O(n)$이 아닌 $O(logn)$으로 동작하도록 최적화가 되어 있어서 따로 처리 안한것 같다.
결론
설명이 길었는데 정리하면 파이썬은 개방 주소법을 사용하여 해시 충돌을 방어하지만 그럼에도 해시 저격 코드를 피하기는 힘들다.
하지만 킹갓제너럴 러스트의 해시맵은 resistance against HashDoS attacks이다. 즉 해시도스에 저항성이 있도록 설계되어 있다. 그러니 러스트를 사용하자.
TMI
해시 충돌 알아보면서 파이썬 구현체 뒤적뒤적하다가 기여도 하고 왔다.
참고
'Computer Science > 알고리즘' 카테고리의 다른 글
| [대회] KUPC Open contest 후기 (2) | 2024.11.26 |
|---|---|
| [알고리즘] 이분 매칭 (bipartite matching) (1) | 2024.08.12 |
| [알고리즘] 비트 연산 (1) | 2024.02.04 |
| [알고리즘] KMP 알고리즘 (0) | 2023.09.15 |
| [알고리즘] 서로소 집합 알고리즘 (Union-Find) (0) | 2022.09.23 |