Python의 사전 및 해시 테이블과 해시 충돌 해결에 대한 간략한 토론

이 기사의 내용은 Python의 사전 및 해시 테이블에 대한 간략한 설명과 해시 충돌 해결에 대한 내용입니다. 도움이 필요한 친구들이 참고할 수 있기를 바랍니다.

Python은 해시 테이블을 사용하여 dict를 구현합니다.

해시 테이블은 실제로 희소 배열입니다. 항상 빈 요소가 있는 배열을 희소 배열이라고 합니다. 일반 서적에서는 해시 테이블의 단위를 일반적으로 버킷이라고 합니다. 존재하다 딕셔너리 해시 테이블에서 각 키-값 쌍은 테이블 요소를 차지하고 각 테이블 요소는 두 부분으로 구성됩니다. 하나는 키에 대한 참조이고 다른 하나는 값에 대한 참조입니다. 각 테이블 셀의 크기가 동일하므로 오프셋을 기준으로 테이블 셀을 읽을 수 있습니다.

Python은 테이블 요소의 약 1/3이 비어 있는지 확인하려고 시도하며 이 임계값에 거의 도달하면 원본 해시 테이블을 확장하여 더 큰 해시 테이블로 복사합니다.

해시 테이블에 객체를 넣으려면 먼저 요소 키의 해시 값을 계산해야 합니다. 이를 위해서는 키가 해시 가능해야 합니다.

해시 가능 객체는 다음 조건을 충족해야 합니다.

hash() 함수를 지원하며 __hash__() 메서드를 통해 얻은 해시 값은 변경되지 않습니다.

__eq__() 메서드를 통해 동등성 검사를 지원합니다.

a == b가 true이면 hash(a) == hash(b)도 true입니다.

다음은 주로 해시 테이블 알고리즘을 설명합니다.

열쇠를 얻으려면 search_key에 해당하는 search_value 값, Python은 먼저 hash(search_key)를 호출하여 계산합니다. 검색_키 해당 값의 해시 값, 이 값의 가장 낮은 몇 자릿수가 오프셋으로 사용되며 테이블 요소는 해시 테이블에서 검색됩니다(구체적인 숫자는 현재 해시 테이블의 크기에 따라 다름). 찾은 테이블 요소가 비어 있으면 KeyError가 발생합니다. 예외; 비어 있지 않은 경우 테이블 요소에found_key:found_value 쌍이 있습니다. search_key 및found_key를 확인하세요. 동일한지 여부, 그렇다면found_value를 반환합니다. 동일하지 않은 경우 이러한 상황을 해시 충돌이라고 합니다.

해시 충돌을 해결하기 위해 알고리즘은 해시 값에서 몇 비트를 더 가져온 다음 특별한 방법으로 처리하고 오프셋으로 얻은 새 값을 사용하여 해시 테이블에서 테이블 요소를 찾습니다. 테이블 요소가 비어 있으면 KeyError 예외도 발생합니다. 비어 있지 않으면 키를 비교하여 해시 충돌이 있으면 해당 값을 반환합니다. 찾았으면 위의 단계를 반복하세요.

새 요소 추가는 빈 테이블 요소가 발견되면 새 요소가 삽입된다는 점을 제외하면 위 프로세스와 거의 동일합니다. 비어 있지 않으면 해시가 반복되고 검색이 계속됩니다.

가세요 새 요소가 사전에 추가되고 해시 충돌이 발생하면 새 요소가 다른 위치에 저장되도록 배열될 수 있습니다. 따라서 다음과 같은 상황이 발생합니다: dict([key1, value1], [key2, value2]) 및 dict([key2, value2], [key1, value1]) 두 사전은 비교할 때 동일하지만 key1과 key2의 해시가 충돌하는 경우 사전에 있는 두 키의 순서가 다릅니다.

언제든지 가세요 dict, python에 새 키 추가 파서는 사전을 확장하기로 결정할 수 있습니다. 확장의 결과는 더 큰 해시 테이블을 생성하고 사전의 기존 요소를 새 해시 테이블에 추가하는 것입니다. 이 프로세스 중에 새로운 해시 충돌이 발생하여 새 해시 테이블의 키 순서가 변경될 수 있습니다. 새 키를 추가하면서 사전을 반복하면 어떻게 되나요? 아쉽게도 용량이 늘어나서 아쉽게도 키의 순서가 바뀌었습니다. orz.

해시 테이블은 희박해야 하므로 공간 소비가 훨씬 커야 합니다. 이는 전형적인 공간 대 시간 균형입니다.

위 내용은 Python의 사전 및 해시 테이블과 해시 충돌 해결에 대한 간략한 토론의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!