Python set() 및 __hash__ confusion

Question

내가 정의한 클래스 중 하나는 set()에서 동일한 객체를 필터링하는 데 사용됩니다. 하지만 예상대로 작동하지 않으므로 잘못된 점을 분명히 이해합니다.

class Foo(object): 

    def __hash__(self): 
     return 7 

x = set() 
x.add(Foo()) 
assert len(x) == 1 
x.add(Foo()) 
assert len(x) == 1 # AssertionError 

집합은 하나의 요소로만 구성 될 것으로 예상되지만 두 개가 있습니다. 왜 그런가요?

Answer 1

해시 충돌은 집합 (해시 맵)에서 발생하는 것으로 알려져 있으며 해시 알고리즘은 모든 항목에 대해 고유 한 해시를 가질만큼 충분하지 않으며 그렇지 않으면 계산하는 데 시간이 오래 걸립니다. 충돌이 발생하면 파이썬은 값의 동일성을 __eq__으로 확인하여 동일하지 않은지 확인합니다.

class Foo(object): 

    def __hash__(self): 
     return 7 
    def __eq__(self, other): 
     return True 

>>> x = set() 
>>> x.add(Foo()) 
>>> assert len(x) == 1 
>>> x.add(Foo()) 
>>> assert len(x) == 1 
>>> 

이 당신이 here을 통해 무서운 런타임을 볼 수 있지만 그들이 O (N) 최악의 경우에도 불구하고, 당신은 O (1) 세트의 멤버 검사를 상각 기대할 수 있습니다 이유입니다 (모든 해시 충돌입니다). 최악의 경우는 파이썬의 스마트 한 구현으로 인해 발생할 가능성이 매우 낮습니다.