[알고리즘] 파이썬 dict, C++ map/unordered_map

우리는 문제를 풀거나 프로그래밍을 할 때 map(unorderd_map), dict을 쓰곤 한다.

키에 무엇이든 넣을 수 있어 편리한 자료구조이지만 사용 시 조심해야 할 부분이 있는 것 같아 포스팅하게 되었다.

 

감사한 곳

https://codeforces.com/blog/entry/101817

Anti-hash-table test in Python - Codeforces

 

	시간복잡도	기반
python dict(defaultdict)	$O(1)$	해시
C++ map	$O(\log{n})$	RB Tree
C++ unordered_map	$O(1)$	해시

우선 차이는 위와 같다.

dict이랑 unordered_map은 같은 해시 기반이다.

위 표만 보면 $O(1)$이기 때문에 dict, unordered_map을 쓰는것이 훨씬 좋아 보인다.

하지만 해시는 충돌이라는 개념이 있기 때문에 언제나 $O(1)$을 보장하지는 않는다.

 

해시충돌

$f(x) = x\mod 7$이라는 해시함수가 있다고 하자.

$f(5) = 5, f(10) = 3, f(27) = 6, \dots$같은 형태일 것이다.

여기서 $f(5)=f(12)=5$이기 때문에 다른 입력에 대해 같은 해시값이 나오게 된다.

이런 경우 충돌이 났다고 표현하고 별도로 처리를 해줘야 한다.

 

보통 처리하는 방법은 배열로 해시값들을 관리하는 것이다.

예를 들어 $f(5) = \{5, 12\}$ 같이 처리한다.

이렇게 되면 해시값 접근하는데 $O(len(f(5)))$의 시간이 걸리게 된다.

운 없게 데이터가 서로 다른 $n$개의 $5k + 7$꼴인 데이터만 들어온다면 접근시간이 $O(n)$이 되는 것이다.

 

물론 파이썬 해시에서는 위에서 언급한 함수처럼 간단한 꼴은 사용하지 않지만 예측이 가능한 형태를 사용한다.

https://github.com/python/cpython/blob/3.8/Objects/dictobject.c#L801

GitHub - python/cpython: The Python programming language

위 레포에서 801번 라인을 보면 해시함수를 볼 수 있다.

i = (i*5 + perturb + 1) & mask;

이를 기반으로 코드포스 오픈핵같은 경우 해시저격이 가능해진다. (저격이 불가능한 대회, 코딩테스트같은 경우는 써도 됨)

경험상 해시저격은 정수형을 키로 썼을 때 발생한 것 같다.

오픈핵에서 해시저격을 안 당하려면 커스텀 해시를 구현해야 한다.

 

구현체

인터넷 자료를 끌어다가 살짝 수정하여 구현했다.

import random

class defaultdict:
    def __init__(self, func):
        self.RANDOM = random.randint(0, 1 << 64)
        self.default = func
        self.dict = {}

    def __iter__(self):
        for key in [self.RANDOM ^ i for i in self.dict]:
            yield key

    def __repr__(self): # debug only
        ret = '{'
        for ix, key in enumerate(self):
            if ix >0:
                ret+=', '
            ret += str(key) + ': ' + str(self[key])
        ret += '}'
        return ret

    def __getitem__(self, key):
        myKey = self.RANDOM ^ key
        if myKey not in self.dict:
            self.dict[myKey] = self.default()
        return self.dict[myKey]

    def __setitem__(self, key, item):
        myKey = self.RANDOM ^ key
        self.dict[myKey] = item

    def getKeys(self):
        return [self.RANDOM ^ i for i in self.dict]

 

C++은 map이 있기 때문에 대신 사용하면 된다.

다만 시간복잡도가 $O(\log{n})$이기 때문에 제한이 $1,000,000$인상황에서 $O(n\log{n})$알고리즘에 사용하면 $O(n(\log{n})^2)$이 되기 때문에 조심해야 한다.

 

마무리

H 해시저격당함

어제 Codeforces Round #799 (Div.4)를 치룬 결과이다.

다 풀고 오렌지퍼포가 나와 블루 복귀 각이었는데 해시저격을 당해 관련 공부를 하고 글을 올렸다. (ㅠㅠㅠ)

앞으로 dict 쓸 때 조심해야겠다.

실제로 백준에서도 해시저격 데추주를 몇 번 본 것 같다..

 

요약

1. 코포 오픈핵이 있는 라운드는 커스텀 해시를 쓰자. (오픈핵 없으면 dict, unordered_map을 써도 되지만 혹시 모른다.)

2. 키를 정수형으로 사용하면 한번쯤은 의심해보자.

3. 평소에는 그냥 내장 해시써도 된다.

4. 안전 : C++ map, C++ set, python custom dict/set, 위험!! : C++ unordered_map, C++ unordered_set, python dict/set

 

---

+ 2022/07/11 추가

python set을 써도 터진다.

절대 python set도 쓰지 말고 커스텀 해시를 쓰자.