파이썬 사전에 동일한 해시를 가진 여러 키를 어떻게 가질 수 있습니까?

파이썬 사전에 동일한 해시를 가진 여러 키를 어떻게 가질 수 있습니까?

---

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

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

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

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

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

class D(C):
    def __eq__(self, other):
        return hash(self) == hash(other)

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

그래서 어떻게 dict가 동일한 해시를 가진 여러 요소를 가질 수 있는지 알고 싶습니다. 감사!

참고 : 답변의 모든 토론이 dicts에 관한 것이기 때문에 dict의 예를 제공하기 위해 질문을 편집했습니다 (set 대신). 그러나 세트에도 동일하게 적용됩니다. 세트는 동일한 해시 값을 가진 여러 요소를 가질 수도 있습니다.

---

Python의 해싱 작동 방식에 대한 자세한 설명은 왜 조기 반환이 다른 것보다 느린가요?

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

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

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

---

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

• 파이썬 사전은 해시 테이블 로 구현됩니다 .
• 해시 테이블은 해시 충돌을 허용해야합니다. 즉, 두 개의 키가 동일한 해시 값을 가지고 있더라도 테이블 구현에는 키와 값 쌍을 모호하지 않게 삽입하고 검색하는 전략이 있어야합니다.
• 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 이면 둘 다 동일한 사전에있을 수 없습니다.

Because we have to probe after every hash collision, one side effect of too many hash collisions is that the lookups and insertions will become very slow (as Duncan points out in the comments).

I guess the short answer to my question is, "Because that's how it's implemented in the source code ;)"

While this is good to know (for geek points?), I am not sure how it can be used in real life. Because unless you are trying to explicitly break something, why would two objects that are not equal, have same hash?

---

Edit: the answer below is one of possible ways to deal with hash collisions, it is however not how Python does it. Python's wiki referenced below is also incorrect. The best source given by @Duncan below is the implementation itself: http://svn.python.org/projects/python/trunk/Objects/dictobject.c I apologize for the mix-up.

---

It stores a list (or bucket) of elements at the hash then iterates through that list until it finds the actual key in that list. A picture says more than a thousand words:

Here you see John Smith and Sandra Dee both hash to 152. Bucket 152 contains both of them. When looking up Sandra Dee it first finds the list in bucket 152, then loops through that list until Sandra Dee is found and returns 521-6955.

The following is wrong it's only here for context: On Python's wiki you can find (pseudo?) code how Python performs the lookup.

There's actually several possible solutions to this problem, check out the wikipedia article for a nice overview: http://en.wikipedia.org/wiki/Hash_table#Collision_resolution

---

Hash tables, in general have to allow for hash collisions! You will get unlucky and two things will eventually hash to the same thing. Underneath, there is a set of objects in a list of items that has that same hash key. Usually, there is only one thing in that list, but in this case, it'll keep stacking them into the same one. The only way it knows they are different is through the equals operator.

When this happens, your performance will degrade over time, which is why you want your hash function to be as "random as possible".

---

In the thread I did not see what exactly python does with instances of a user-defined classes when we put it into a dictionary as a keys. Let's read some documentation: it declares that only hashable objects can be used as a keys. Hashable are all immutable built-in classes and all user-defined classes.

User-defined classes have __cmp__() and __hash__() methods by default; with them, all objects compare unequal (except with themselves) and x.__hash__() returns a result derived from id(x).

So if you have a constantly __hash__ in your class, but not providing any __cmp__ or __eq__ method, then all your instances are unequal for the dictionary. In the other hand, if you providing any __cmp__ or __eq__ method, but not providing __hash__, your instances are still unequal in terms of dictionary.

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)

Output

{<__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}

참고URL : https://stackoverflow.com/questions/9010222/how-can-python-dict-have-multiple-keys-with-same-hash