Python dict를 구현하는 방법

Python의 dict 객체는 키-값 쌍의 형태로 저장되는 원시 Python 데이터 유형임을 나타냅니다. 이름에서 알 수 있듯이 해당 중국어 이름이 사전으로 번역됩니다. 키 이름을 통해 값을 계산하지만 시간이 많이 걸립니다. 상수 수준에서 정도는 O(1)입니다.

dict의 기본 구현(권장 학습: Python 비디오 튜토리얼)

Python2에서는 dict의 최하위 레이어가 해시 테이블(Hash Table)로 구현됩니다. 예, 충돌을 해결하려면 주소 공개 방법을 사용하세요.

그러므로 검색의 시간 복잡도는 O(1)이 됩니다.

작업 Dict의 구현 원리(삽입, 삭제 및 버퍼 풀 등 포함)

먼저 소개: PyDictObject 개체에 대한 요소 검색 전략:

lookdict와 lookdict_string이라는 두 가지 검색 전략이 있습니다. Lookdict_string은 Lookdict의 특수한 형태입니다. PyStringObject를 검색할 때 일반 검색 전략 Lookdict의 주요 논리는 다음과 같습니다.

(1) 첫 번째 항목 검색:

a) 해시 값을 기반으로 항목의 인덱스를 얻습니다.

b) 항목이 미사용 상태이면 검색이 종료되고, 해당 항목이 가리키는 키가 검색된 키와 동일하면 검색 성공

c) 현재 항목이 더미 상태이면 freeslot을 설정합니다(여기서는 freeslot을 설정합니다). 항목을 저장하기 위해 즉시 사용 가능한 다음 주소로 반환될 수 있음)

d) 활성 상태의 항목을 확인하고 해당 키가 가리키는 값이 검색된 값과 동일한 경우 값이 동일한 경우 검색이 성공했습니다

(2) 나머지 감지 체인의 요소에 대한 순회 검색:

a) 사용된 감지 기능에 따라 감지 체인에서 확인할 다음 항목을 얻습니다.

b) 확인 사용되지 않은 항목으로 검색 실패를 나타내는 항목:

빈 슬롯이 비어 있지 않으면 빈 슬롯을 반환하고, 그렇지 않으면 사용하지 않은 항목을 반환합니다.

c) 항목의 키가 검색 중인 키의 참조와 동일한지 확인합니다. 동일하면 검색 성공, 입력 복귀

d) 입력된 키와 검색 중인 키의 값이 동일한지 확인하여 동일하면 검색 성공 및 입력 반환

e) 중. 순회 프로세스에서 더미 상태의 항목이 발견되고 freeslot이 설정되지 않은 경우 freeslot을 설정하세요

다음 단계는: PyDictObject 객체의 요소를 삽입하고 삭제하는 전략:

먼저 검색 전략을 사용해야 합니다. 검색에 성공하면 값이 직접 교체됩니다. 검색에 실패하면 사용되지 않은 상태 또는 더미 상태의 항목이 반환되고 키, 값 및 해시 값이 설정됩니다. 현재 삽입된 요소에 따라 ma_table(조정은 로딩 속도를 기반으로 하며 2/3보다 큰지 여부에 따라 조정됨) 삭제도 유사하며 먼저 해시 값을 계산한 다음 해당 항목을 검색합니다. , 검색이 성공하면 항목에 유지되는 요소를 삭제하고 항목을 Active 상태에서 더미 상태로 변경합니다

PyDictObject 구현 과정에서 버퍼 풀이 사용되며 버퍼 풀은 PyDictObject 객체가 소멸될 때만 사용됩니다. 버퍼링된 PyDictObject 객체의 경우 정의된 버퍼 풀이 수용할 수 있는 객체 수는 80개입니다. 새 PyDictObject 객체를 생성할 때 버퍼 풀에 객체가 있으면 직접 꺼낼 수 있습니다. 버퍼 풀을 사용하여

더 많은 Python 관련 기술 기사를 알아보려면 Python Tutorial 칼럼을 방문하세요!

위 내용은 Python dict를 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!