파이썬 사전은 포인터의 해시 맵입니다 ... 무엇?

Question

파이썬에서 사전은 키를 해싱하고 배열에 키 - 값 쌍에 대한 포인터를 저장하여 사전이 구현된다는 것을 알고 있습니다. 인덱스는 해시에 의해 결정됩니다.

그러나 키 - 값 쌍 자체는 어떻게 저장됩니까? 그것들은 함께 저장되어 있습니까 (즉, 연속적으로 메모리에 저장되어 있습니까?)? 하나의 키와 하나의 값을 가리키는 터플이나 포인터 배열로 저장되어 있습니까? 아니면 완전히 다른 것입니까?

인터넷 검색은 해싱 및 공개 주소 지정 등에 대한 설명이 많이 나오지만이 질문은 다루지 않았습니다.

Answer 1

대략 함수가 있습니다. F이라고 부르며, 값 배열에 인덱스 F(h)을 계산합니다. 따라서 값은 배열로 저장되며 이들은 F(h)으로 조회됩니다. "대략 말하기"하는 이유는 해시가 서로 다른 객체에 대해 다르게 계산된다는 것입니다. 예를 들어 포인터의 경우 p>>3; 문자열의 경우 해시는 문자열의 모든 바이트를 요약 한 것입니다.

C 코드를 보려면 lookdict_index을 검색하거나 CPython의 소스 코드에서 dictobject.c 파일을 살펴보십시오. C 코드를 읽는 데 익숙하다면 꽤 읽기 쉽습니다.

편집 1 :

/* 
The DictObject can be in one of two forms. 

Either: 
    A combined table: 
    ma_values == NULL, dk_refcnt == 1. 
    Values are stored in the me_value field of the PyDictKeysObject. 
Or: 
    A split table: 
    ma_values != NULL, dk_refcnt >= 1 
    Values are stored in the ma_values array. 
    Only string (unicode) keys are allowed. 
    All dicts sharing same key must have same insertion order. 
.... 
*/ 

값이 하나 저장됩니다

/* If ma_values is NULL, the table is "combined": keys and values 
    are stored in ma_keys. 

    If ma_values is not NULL, the table is splitted: 
    keys are stored in ma_keys and values are stored in ma_values */ 

그리고 dictobject :에서 설명 : 파이썬에서 주석에서 는의가/dictobject.h 포함 3.6.1 「열쇠 오브젝트」의 배열을 따르는 캐릭터 라인의 배열입니다. 또는 각 값의 포인터는 me_valuePyDictKeyEntry에 저장됩니다. 키는 me_key 필드에 PyDictKeyEntry으로 저장됩니다. 키 배열은 실제로 PyDictKeyEntry 구조체의 배열입니다. 파이썬의 소스/dictobject.h 객체/DICT-common.h, 객체/dictobject.c 및 포함 :

typedef struct { 
     /* Cached hash code of me_key. */ 
     Py_hash_t me_hash; 
     PyObject *me_key; 
     PyObject *me_value; /*This field is only meaningful for combined tables*/ 
    } PyDictKeyEntry; 

관련 보는 파일 : 그냥 참고로

, PyDictKeyEntry는 다음과 같이 정의된다 암호.

Objects/dictobject.c는 전체 구성표와 배경 지식을 설명하는 파일의 시작 부분에 주석으로 광범위한 내용을 기록합니다.