[python] Python dict에 동일한 해시를 가진 여러 키가있는 이유는 무엇입니까?

Question 1

hash후드 아래에서 Python 함수 를 이해하려고합니다 . 모든 인스턴스가 동일한 해시 값을 반환하는 사용자 지정 클래스를 만들었습니다.

class C:
    def __hash__(self):
        return 42

위의 클래스의 인스턴스는 한 번에 하나만있을 수 있다고 가정 dict했지만 실제로 dict는 동일한 해시를 가진 여러 요소를 가질 수 있습니다.

c, d = C(), C()
x = {c: 'c', d: 'd'}
print(x)
# {<__main__.C object at 0x7f0824087b80>: 'c', <__main__.C object at 0x7f0823ae2d60>: 'd'}
# note that the dict has 2 elements

좀 더 실험을 해보니 __eq__클래스의 모든 인스턴스가 동일하게 비교 되도록 메서드를 재정의 dict하면 하나의 인스턴스 만 허용 된다는 것을 알았습니다 .

class D:
    def __hash__(self):
        return 42
    def __eq__(self, other):
        return True

p, q = D(), D()
y = {p: 'p', q: 'q'}
print(y)
# {<__main__.D object at 0x7f0823a9af40>: 'q'}
# note that the dict only has 1 element

따라서 dict동일한 해시를 가진 여러 요소를 가질 수있는 방법을 알고 싶습니다 .

Question 2

Python의 해싱이 어떻게 작동하는지에 대한 자세한 설명은 왜 조기 반환이 다른 것보다 느린가요?

기본적으로 해시를 사용하여 테이블의 슬롯을 선택합니다. 슬롯에 값이 있고 해시가 일치하면 항목을 비교하여 동일한 지 확인합니다.

해시가 일치하지 않거나 항목이 같지 않으면 다른 슬롯을 시도합니다. 이것을 선택하는 공식이 있습니다 (참조 된 답변에서 설명합니다), 해시 값의 사용되지 않는 부분을 점차적으로 가져옵니다. 그러나 일단 모두 사용하면 결국 해시 테이블의 모든 슬롯을 통해 작동합니다. 결국 일치하는 항목이나 빈 슬롯을 찾게됩니다. 검색에서 빈 슬롯을 찾으면 값을 삽입하거나 포기합니다 (값을 추가하거나 가져 오는지 여부에 따라 다름).

주목해야 할 중요한 점은 목록이나 버킷이 없다는 것입니다. 특정 수의 슬롯이있는 해시 테이블 만 있고 각 해시는 후보 슬롯의 시퀀스를 생성하는 데 사용됩니다.

Question 3

여기에 내가 모을 수 있었던 파이썬 딕셔너리에 대한 모든 것이 있습니다 (아마 누구도 알고 싶어하는 것보다 더 많을 것입니다.하지만 대답은 포괄적입니다). Python dicts가 슬롯을 사용하고 나를이 토끼 굴로 이끄는 것을 지적한 Duncan 에게 외침 .

파이썬 사전은 해시 테이블 로 구현됩니다 .
해시 테이블은 해시 충돌을 허용해야합니다. 즉, 두 개의 키가 동일한 해시 값을 가지고 있더라도 테이블 구현에는 키와 값 쌍을 모호하지 않게 삽입하고 검색하는 전략이 있어야합니다.
Python dict는 개방 주소 지정 을 사용 하여 해시 충돌을 해결합니다 (아래 설명 됨) ( dictobject.c : 296-297 참조 ).
파이썬 해시 테이블은 연속적인 메모리 블록 일뿐입니다 (배열과 비슷하므로 O(1)인덱스로 조회 할 수 있습니다 ).
테이블의 각 슬롯은 하나의 항목 만 저장할 수 있습니다. 이것은 중요하다
테이블의 각 항목 은 실제로 세 값의 조합입니다.. 이것은 C 구조체로 구현됩니다 ( dictobject.h : 51-56 참조 ).

아래 그림은 파이썬 해시 테이블의 논리적 표현입니다. 아래 그림에서 왼쪽의 0, 1, …, i, … 는 해시 테이블 에있는 슬롯의 인덱스입니다 (이들은 단지 설명을위한 것이며 테이블과 함께 저장되지 않습니다!).

# Logical model of Python Hash table
-+-----------------+
0| <hash|key|value>|
-+-----------------+
1|      ...        |
-+-----------------+
.|      ...        |
-+-----------------+
i|      ...        |
-+-----------------+
.|      ...        |
-+-----------------+
n|      ...        |
-+-----------------+

새로운 dict가 초기화되면 8 개의 슬롯으로 시작 합니다 . ( dictobject.h : 49 참조 )
테이블에 항목을 추가 할 때 i키의 해시를 기반으로하는 슬롯으로 시작 합니다. CPython은 초기 i = hash(key) & mask. 어디 mask = PyDictMINSIZE - 1,하지만 그다지 중요하지 않습니다). 확인되는 초기 슬롯 i 는 키 의 해시 에 따라 다릅니다 .
해당 슬롯이 비어 있으면 항목이 슬롯에 추가됩니다 (항목에 따라 <hash|key|value>). 그러나 그 슬롯이 점유되면 어떨까요!? 다른 항목에 동일한 해시 (해시 충돌!)가 있기 때문일 가능성이 높습니다.
슬롯이 점유 된 경우 CPython (및 PyPy)은 슬롯에있는 항목 의 해시와 키 ( ==비교가 아닌 is비교를 통해)를 삽입 할 현재 항목의 키 ( dictobject.c : 337 , 344-345 ). 경우 모두 일치, 다음은 항목이 이미 생각하고 포기하고 다음 항목에 이동 삽입 할 수 있습니다. 중 해시 또는 키가 일치하지 않는 경우, 시작 프로빙 .
Probing은 빈 슬롯을 찾기 위해 슬롯별로 슬롯을 검색한다는 의미입니다. 기술적으로 우리는 하나씩, i + 1, i + 2, …로 이동하고 첫 번째 사용 가능한 것을 사용할 수 있습니다 (선형 프로빙). 그러나 주석 ( dictobject.c : 33-126 참조)에서 아름답게 설명 된 이유 때문에 CPython은 임의 조사를 사용합니다 . 랜덤 프로빙에서 다음 슬롯은 의사 랜덤 순서로 선택됩니다. 항목이 첫 번째 빈 슬롯에 추가됩니다. 이 논의에서 다음 슬롯을 선택하는 데 사용되는 실제 알고리즘은 실제로 중요하지 않습니다 ( 프로빙 알고리즘 은 dictobject.c : 33-126 참조 ). 중요한 것은 첫 번째 빈 슬롯을 찾을 때까지 슬롯이 검색된다는 것입니다.
조회에서도 똑같은 일이 발생합니다. 초기 슬롯 i (여기서 i는 키의 해시에 따라 다름)로 시작합니다. 해시와 키가 모두 슬롯의 항목과 일치하지 않으면 일치하는 슬롯을 찾을 때까지 검색을 시작합니다. 모든 슬롯이 소진되면 실패를보고합니다.
BTW, 딕셔너리는 2/3가 차면 크기가 조정됩니다. 이렇게하면 조회 속도가 느려지지 않습니다. ( dictobject.h : 64-65 참조 )

됐어요! dict의 Python 구현은 ==항목을 삽입 할 때 두 키의 해시 같음과 키의 정상 같음 ( ) 을 모두 확인 합니다. 요약하면, 두 개의 키 a와 b및 hash(a)==hash(b),하지만 a!=b이면 둘 다 파이썬 딕셔너리에 조화롭게 존재할 수 있습니다. 그러나 만약 hash(a)==hash(b) 및 a==b 이면 둘 다 같은 사전에있을 수 없습니다.

모든 해시 충돌 후 조사해야하기 때문에 너무 많은 해시 충돌의 한 가지 부작용은 조회 및 삽입이 매우 느려진다는 것입니다 (Duncan이 주석 에서 지적했듯이 ).

내 질문에 대한 짧은 대답은 “그게 소스 코드에서 구현되는 방식이기 때문에”입니다.

이것은 알아두면 좋지만 (괴짜 포인트에 대해?) 실생활에서 어떻게 사용할 수 있는지 잘 모르겠습니다. 왜냐하면 당신이 명시 적으로 무언가를 깨뜨 리려고하지 않는 한, 같지 않은 두 객체가 같은 해시를 가지는 이유는 무엇입니까?

Question 4

편집 : 아래의 대답은 해시 충돌을 처리 할 수있는 방법 중 하나입니다, 그러나 그것은 것입니다 하지 파이썬은 어떻게하는지. 아래 참조 된 Python의 위키도 올바르지 않습니다. 아래 @Duncan이 제공하는 최고의 소스는 구현 자체입니다. https://github.com/python/cpython/blob/master/Objects/dictobject.c 혼합에 대해 사과드립니다.

해시에 요소 목록 (또는 버킷)을 저장 한 다음 해당 목록에서 실제 키를 찾을 때까지 해당 목록을 반복합니다. 사진은 천 단어 이상을 말합니다.

여기에 당신이 볼 John Smith과 Sandra Dee에 모두 해시 152. 버킷 152에는 둘 다 포함됩니다. 조회 할 Sandra Dee때 먼저 버킷에서 목록을 찾은 152다음 Sandra Dee찾을 때까지 해당 목록을 반복하여 반환합니다 521-6955.

다음은이 상황 만 여기에 잘못된 : 에 파이썬의 위키는 파이썬이 조회를 수행하는 방법 (? 의사) 코드를 찾을 수 있습니다.

실제로이 문제에 대한 몇 가지 가능한 해결책이 있습니다. wikipedia 문서에서 멋진 개요를 확인하세요. http://en.wikipedia.org/wiki/Hash_table#Collision_resolution

Question 5

일반적으로 해시 테이블은 해시 충돌을 허용해야합니다! 당신은 불행해질 것이고 두 가지가 결국 같은 것을 해시 할 것입니다. 그 아래에는 동일한 해시 키를 가진 항목 목록에 개체 집합이 있습니다. 일반적으로 해당 목록에는 한 가지만 있지만이 경우 동일한 항목에 계속 쌓입니다. 그들이 다르다는 것을 아는 유일한 방법은 같음 연산자를 통하는 것입니다.

이런 일이 발생하면 시간이 지남에 따라 성능이 저하되므로 해시 함수가 “가능한 한 무작위”가되기를 원합니다.

Question 6

스레드에서 파이썬이 사용자 정의 클래스의 인스턴스를 키로 딕셔너리에 넣었을 때 정확히 무엇을하는지 보지 못했습니다. 몇 가지 문서를 읽어 보겠습니다. 해시 가능한 객체 만 키로 사용할 수 있다고 선언합니다. Hashable은 모두 변경 불가능한 내장 클래스와 모든 사용자 정의 클래스입니다.

사용자 정의 클래스에는 기본적으로 __cmp __ () 및 __hash __ () 메서드가 있습니다. 그들과 함께, 모든 객체는 같지 않다 (자신을 제외하고) 비교하고 x .__ hash __ ()는 id (x)에서 파생 된 결과를 반환합니다.

따라서 클래스에 지속적으로 __hash__가 있지만 __cmp__ 또는 __eq__ 메서드를 제공하지 않으면 모든 인스턴스가 사전과 같지 않습니다. 반면에 __cmp__ 또는 __eq__ 메서드를 제공하지만 __hash__를 제공하지 않는 경우 인스턴스는 사전 측면에서 여전히 동일하지 않습니다.

class A(object):
    def __hash__(self):
        return 42


class B(object):
    def __eq__(self, other):
        return True


class C(A, B):
    pass


dict_a = {A(): 1, A(): 2, A(): 3}
dict_b = {B(): 1, B(): 2, B(): 3}
dict_c = {C(): 1, C(): 2, C(): 3}

print(dict_a)
print(dict_b)
print(dict_c)

산출

{<__main__.A object at 0x7f9672f04850>: 1, <__main__.A object at 0x7f9672f04910>: 3, <__main__.A object at 0x7f9672f048d0>: 2}
{<__main__.B object at 0x7f9672f04990>: 2, <__main__.B object at 0x7f9672f04950>: 1, <__main__.B object at 0x7f9672f049d0>: 3}
{<__main__.C object at 0x7f9672f04a10>: 3}