사전 및 해시 테이블 공간 복잡성

Question

사전 및 해시 테이블에 대해 혼란 스럽지만 명확히하고 싶습니다. 현재의 사전 및 현재의 파이썬 실행 결과 해시가 있습니다.

Dict = dict() 
print(hash('a')) 
print(hash('b')) 
print(hash('c')) 
Dict['a'] = 1 
Dict['b'] = 2 
Dict['c'] = 3 
print(Dict) 

그래서 내 지식 해시 테이블은 해시 해시 테이블의 인덱스 배열은 단순히

1714333803 
1519074822 
1245896149 
{'a': 1, 'c': 3, 'b': 2} 

의 출력을 가지고있다. 예를 들어, 'a'는 해시 테이블이 1714333803이므로 해시 테이블 1714333803의 값은 'a'입니다. 따라서 해시 테이블에있는 인덱스의 수와 해시 함수로 어떻게 해답을 얻는 지 혼란 스럽습니까? 모듈러스를 사용하고 인덱스의 고정 범위가 있습니까? 사전의 주어진 인쇄물은 {'a': 1, 'c': 3, 'b': 2}을 출력하기 때문에 출력하지만 실제로 출력한다고 가정하는 것은 정확합니다. 사전은 실제로 1714333803 개의 인덱스가 가장 많은 배열입니다. 3 개의 요소를 포함하는 말도 안되는 것 같습니다. 공간의 낭비이다. 또한 해시 테이블의 경우 값이없는 인덱스에는 무엇이 있습니까?

Answer 1

dict의 실제 크기는 구현에 따라 다르지만, 귀하의 경우에는 아마도 8 일 것입니다. 어떻게 작동합니까?

dict (또는 일반적으로 해시 맵)의 작동 원리는 모든 키에 대한 수치 해시를 계산하는 것입니다. 귀하의 경우 예를 들어 hash("a") == 1714333803입니다. 이제 해시는 색인으로 직접 사용되지 않습니다. 대신 사전의 크기에 매핑됩니다.

이렇게하는 간단한 방법은 모듈로 (%)입니다. dict 크기가 8이라고 가정 해 보겠습니다. 그런 다음 hash("a") % 8 == 1714333803 % 8 == 3. 그래서 귀하의 항목은 실제로 4 위입니다. 어떤 항목도 배열 외부에 인덱스를 가질 수 없습니다.

여기에는 해시 충돌과 같은 몇 가지 복잡한 것들이 있습니다. 예를 들어 다른 항목의 해시가 98499 인 경우 도은 3에 매핑됩니다. 이 경우 다른 색인을 선택하는 충돌 해결 전략이 있습니다.

따라서 dict 크기가 8 인 이유는 무엇입니까? 그게 default size in python이기 때문입니다. dict 크기가 너무 작 으면 크기를 조정해야합니다. 배열과 달리, dict이 실제로 채워지기 전에 완료됩니다 (즉, two thirds filling). 해시 충돌을 줄이기 위해 수행됩니다. dict이 99 %로 가득 차면 충돌이 실제로 보장됩니다. 크기 8 사전의 경우 크기를 조정하기 전에 5-32 개의 항목을 입력해야합니다 (예 : doubles its capacity - 16).