CPython Dicts가 음수 값 1과 음수 2의 해시 값의 영향을받지 않는 이유는 무엇입니까

Question

Hash tables are supposed be high-performance mappings, and because Python dicts are implemented with hash tables 등의 높은 성능도 있습니다. 하지만 음수의 해시 값을 살펴볼 때 이상한 결과가 발생했습니다.

>>> for i in range(7): 
...  print hash(i-4) 
...  
-4 
-3 
-2 
-2 
0 
1 
2 

그러나 이것은 분명히 dicts에 아무런 영향이 없습니다 :

>>> d = dict() 
>>> d[-1] = 'foo' 
>>> d[-2] = 'bar' 
>>> d 
{-2: 'bar', -1: 'foo'} 

왜 이런 일이 않는, 그리고 내가 그들을 사용할 때 왜 dicts이 영향을받지 않습니다?

Answer 1

이 y과 다른 해시 값을 가지고 있다는 사실은 x != y을 의미합니다. 그러나 그 반대는 사실이 아닙니다! 따라서 x의 해시 값이 y이면 동등성이 명시 적으로 검사됩니다.

hash(x) == hash(y) 및 x != y은 해시 함수의 컨텍스트에서 충돌 전화를 수시로 일어날 가능성 뭔가되는 상황. 가능한 한 많이 피하고 싶지만 일반적으로 불가피합니다. 해시 함수 및 충돌에 대한 자세한 내용은 here을 참조하십시오.

Answer 2

해시 값이 반복 해시 값의 영향을받지 않는 이유는 해시 값이 해시 테이블에서 작동 할 때 고유하지 않아도되기 때문입니다.

파이썬은 정수 해시 값이 자체적으로 해석되는 정수의 간단한 해싱을 구현합니다. 내부적으로 해시 값 생성 실패를 알리는 데 -1이 사용되므로 값 -1은 자동으로 -2로 바뀌므로 잘 작동합니다.

Answer 3

-1은 C 코드의 오류 코드이며, 해시 함수가 C 코드 오류를 표시하지 않도록 반환 할 수 없습니다. C에는 예외가 없기 때문에 Python 개발자는 하나를 오류를 알리는 리턴 값으로 예약해야했습니다.

사전은 을 사용하지 않습니다. 단지 해시입니다. 그것은 또한 평등을 테스트합니다. 해시 값이 이 아니고이 아닌 해시 값이 동일한 슬롯에 계속 매핑 될 수있는 경우에도 해시 테이블은 가능한 해시 값 수와 비교하여 작은입니다. 해시 값이 동일한 슬롯에 매핑되고 키가 같지 않으면 해시가 불안정 해지고 새 슬롯이 발견됩니다.

-1 != -2이므로 파이썬은 여전히 ​​두 키를 구분합니다.

파이썬의 사전에서 해시를 사용하는 방법에 대한 자세한 내용은 Overriding Python's Hashing Function in Dictionary 및 Why is the order in dictionaries and sets arbitrary?을 참조하십시오.

Answer 4

해시 값이 다를 경우 해시 테이블의 성능이 향상되지만 동일한 해시 값을 처리 할 수 ​​있습니다. 이를 해시 충돌이라고하며 해시 충돌을 처리하는 방법은 해시 테이블을 최적화하고 조정하는 큰 방법 중 하나입니다.

hash(-1) == -2 -1은 C 구현에서 오류를 알리는 데 사용되는 특수 값이기 때문에. 해시 코드는 그 값을 사용할 수 없습니다. -1의 해시를 제공하는 클래스를 정의하려고하면 파이썬이 그것을 검색하고 대신 -2를 사용합니다.