Python 사전 대상 실현 원리 상세 설명

사전 형식 은 Python 에서 가장 자주 사용 하 는 데이터 형식 중 하나 입 니 다.키 값 이 맞 는 집합 입 니 다.사전 은 키 를 통 해 색인 을 하고 상대 적 인 값 과 관련 되 며 이론 적 으로 조회 복잡 도 는 O(1)입 니 다.

>>> d = {'a': 1, 'b': 2}
>>> d['c'] = 3
>>> d
{'a': 1, 'b': 2, 'c': 3}

문자열 의 실현 원리 글 에서 사전 대상 이 intern 작업 에 사용 되 었 다 면 사전 의 내부 구 조 는 어 떻 습 니까?PyDictObject 대상 은 dict 의 내부 실현 입 니 다.
해시 시계(HASH TABLES)
해시 표(산 목록 이 라 고도 함)는 키 값 에 따라 직접 접근 하 는 데이터 구조 입 니 다.키 와 value 를 표 의 한 위치 에 비 추어 기록 에 접근 합 니 다.이러한 조회 속 도 는 매우 빠 르 고 업데이트 도 빠 릅 니 다.이 매 핑 함 수 는 해시 함수 라 고 하 는데,값 을 저장 하 는 배열 은 해시 표 라 고 합 니 다.해시 함수 의 실현 방식 은 해시 표 의 검색 효율 을 결정 한다.구체 적 인 조작 과정 은:
1.데이터 추가:키 를 해시 함 수 를 통 해 하나의 정형 숫자 로 변환 한 다음 에 이 숫자 를 배열 의 길 이 를 나머지 로 하고 나머지 결 과 는 배열 의 아래 표 로 삼 아 value 를 아래 표 시 된 배열 공간 에 저장 합 니 다.
2.데이터 조회:해시 함 수 를 다시 사용 하여 key 를 대응 하 는 배열 로 표시 하고 배열 의 위치 로 이동 하여 value 를 가 져 옵 니 다.
그러나 키 에 대해 hash 를 진행 할 때 키 에 따라 hash 가 나 올 수 있 는 결 과 는 같 습 니 다.특히 데이터 양 이 증가 할 때 이 문 제 는 해시 충돌 이 라 고 합 니 다.이런 충돌 상황 을 해결 하면?일반적인 방법 은 두 가지 가 있 는데 하 나 는 링크 법 이 고 다른 하 나 는 주소 지정 법 을 개방 하 며 Python 은 후 자 를 선택한다.
주소 지정 방법 열기(OPEN ADDRESSING)
오픈 주소 지정 법 에 서 는 모든 요 소 를 해시 표 에 저장 합 니 다.해시 충돌 이 발생 했 을 때 하나의 탐측 함 수 를 통 해 다음 후보 위 치 를 계산 합 니 다.다음 선택 위치 가 충돌 하면 탐측 함 수 를 통 해 빈 슬롯 을 찾 아 삽입 할 요 소 를 저장 할 때 까지 계속 찾 습 니 다.
PYDICTENTRY
사전 의 key-value 키 값 은 요 소 를 entry(slots 라 고도 함)라 고 부 릅 니 다.Python 내부 에 대응 하 는 것 은 PyDictEntry 이 고 PyDictObject 는 PyDictEntry 의 집합 입 니 다.PyDictEntry 의 정 의 는:

typedef struct {
/* Cached hash code of me_key. Note that hash codes are C longs.
* We have to use Py_ssize_t instead because dict_popitem() abuses
* me_hash to hold a search finger.
*/
Py_ssize_t me_hash;
PyObject *me_key;
PyObject *me_value;
} PyDictEntry;

me_hash 캐 시 mekey 의 해시 값 은 검색 할 때마다 해시 값 을 계산 하 는 것 을 방지 합 니 다.entry 는 세 가지 상태 가 있 습 니 다.
1.Unused： me_key == me_value == NULL
Unused 는 entry 의 초기 상태 이 며,key 와 value 는 모두 NULL 입 니 다.요 소 를 삽입 할 때 Unused 상 태 를 Active 상태 로 변환 합 니 다.이것 은 me키 가 NULL 인 유일한 경우 입 니 다.
2. Active： me_key != NULL and me_key != dummy 그리고 mevalue != NULL
요 소 를 삽입 하면 entry 는 Active 상태 가 됩 니 다.이것 은 me 입 니 다.value 가 NULL 이 아 닌 유일한 경우 요 소 를 삭제 할 때 Active 상태 에서 Dummy 상태 로 변 환 됩 니 다.
3. Dummy： me_key===dummy 그리고 mevalue == NULL
이 곳 의 Dummy 대상 은 실제 PyStringObject 대상 으로 표시 표지 로 만 사 용 됩 니 다.Dummy 상태의 요 소 는 요 소 를 삽입 할 때 활성 상태 로 바 꿀 수 있 지만 더 이상 Unused 상태 로 바 꿀 수 없습니다.
왜 entry 에 Dummy 상태 가 있 죠?이 는 개방 주소 지정 법 에서 해시 충돌 이 발생 했 을 때 다음 적당 한 위 치 를 찾 을 수 있 기 때 문 입 니 다.예 를 들 어 특정한 요소 가 해시 계산 을 통 해 A 에 삽입 되 어야 합 니 다.그러나 이때 A 에 요소 가 있 는 경우 탐측 함수 계산 을 통 해 다음 위치 B 를 얻 을 수 있 고 위치 C 를 찾 을 때 까지 요소 가 있 습 니 다.이때 ABC 는 탐측 체인 을 구성 하고 요 소 를 찾 을 때 hash 값 이 같 으 면그러면 이 탐측 체인 을 따라 계속 뒤 를 찾 습 니 다.탐측 체인 중의 특정한 요 소 를 삭제 할 때 예 를 들 어 B.만약 에 B 를 해시 표 에서 직접 제거 하면 Unused 상태 가 되 고 C 는 다시 찾 을 수 없습니다.AC 사이 에 끊 어 지 는 현상 이 나타 나 기 때문에 세 번 째 상태 인 Dummy,Dummy 는 비슷 한 위조 삭제 방식 입 니 다.탐지 체인 의 연속 성 을 확보 하 다.

PYDICTOBJECT
PyDictObject 는 PyDictEntry 대상 의 집합 이 고 PyDictObject 의 구 조 는:

typedef struct _dictobject PyDictObject;
struct _dictobject {
PyObject_HEAD
Py_ssize_t ma_fill; /* # Active + # Dummy */
Py_ssize_t ma_used; /* # Active */
/* The table contains ma_mask + 1 slots, and that's a power of 2.
* We store the mask instead of the size because the mask is more
* frequently needed.
*/
Py_ssize_t ma_mask;
/* ma_table points to ma_smalltable for small tables, else to
* additional malloc'ed memory. ma_table is never NULL! This rule
* saves repeated runtime null-tests in the workhorse getitem and
* setitem calls.
*/
PyDictEntry *ma_table;
PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
PyDictEntry ma_smalltable[PyDict_MINSIZE];
};

ma_fill:Active 및 Dummy 에 있 는 모든 요소 갯 수

ma_used:모든 Active 상태 에 있 는 요소 의 갯 수

ma_mask:모든 entry 요소 개수(Active+Dummy+Unused)

ma_smalltable:사전 대상 을 만 들 때 PyDict 크기 로 만 듭 니 다.MINSIZE==8 의 PyDictEntry 배열..

ma_table:entry 수량 이 PyDict 보다 적 을 때MINSIZE，ma_table 지향 masmalltable 의 첫 주 소 는 entry 수량 이 8 보다 많 을 때 Python 은 큰 사전 으로 처리 합 니 다.이 때 추가 메모리 공간 을 신청 하고 matable 은 이 공간 을 가리 키 고 있 습 니 다

ma_lookup:사전 요소 의 검색 전략

PyDictObject 사용 PyObjectPyObject 가 아 닌 HEADVar_HEAD,사전 도 길 어 지 는 대상 이지 만,이곳 은 ob 를 통 해size 는 사전 에 있 는 요소 의 길 이 를 저장 하 는 것 이 아니 라 ma 를 통 해used 필드.
PYDICTOBJECT 생 성 과정

PyObject *
PyDict_New(void)
{
register PyDictObject *mp;
if (dummy == NULL) { /* Auto-initialize dummy */
dummy = PyString_FromString("<dummy key>");
if (dummy == NULL)
return NULL;
}
if (numfree) {
mp = free_list[--numfree];
assert (mp != NULL);
assert (Py_TYPE(mp) == &PyDict_Type);
_Py_NewReference((PyObject *)mp);
if (mp->ma_fill) {
EMPTY_TO_MINSIZE(mp);
} else {
/* At least set ma_table and ma_mask; these are wrong
if an empty but presized dict is added to freelist */
INIT_NONZERO_DICT_SLOTS(mp);
}
assert (mp->ma_used == 0);
assert (mp->ma_table == mp->ma_smalltable);
assert (mp->ma_mask == PyDict_MINSIZE - 1);
} else {
mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
if (mp == NULL)
return NULL;
EMPTY_TO_MINSIZE(mp);
}
mp->ma_lookup = lookdict_string;
return (PyObject *)mp;
}

Dummy 대상 초기 화

버퍼 에 사용 가능 한 대상 이 있 으 면 버퍼 에서 읽 습 니 다.그렇지 않 으 면 실행 절차 3

메모리 공간 을 분배 하고 PyDictObject 대상 을 만 들 며 대상 을 초기 화 합 니 다

4.567917.사전 요 소 를 추가 할 때의 탐측 함수,요소 의 검색 전략 을 지정 합 니 다사전 검색 정책

static PyDictEntry *
lookdict(PyDictObject *mp, PyObject *key, register long hash)
{
register size_t i;
register size_t perturb;
register PyDictEntry *freeslot;
register size_t mask = (size_t)mp->ma_mask;
PyDictEntry *ep0 = mp->ma_table;
register PyDictEntry *ep;
register int cmp;
PyObject *startkey;

i = (size_t)hash & mask;
ep = &ep0[i];
if (ep->me_key == NULL || ep->me_key == key)
return ep;

if (ep->me_key == dummy)
freeslot = ep;
else {
if (ep->me_hash == hash) {
startkey = ep->me_key;
Py_INCREF(startkey);
cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
Py_DECREF(startkey);
if (cmp < 0)
return NULL;
if (ep0 == mp->ma_table && ep->me_key == startkey) {
if (cmp > 0)
return ep;
}
else {
/* The compare did major nasty stuff to the
* dict: start over.
* XXX A clever adversary could prevent this
* XXX from terminating.
*/
return lookdict(mp, key, hash);
}
}
freeslot = NULL;
}

/* In the loop, me_key == dummy is by far (factor of 100s) the
least likely outcome, so test for that last. */
for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
i = (i << 2) + i + perturb + 1;
ep = &ep0[i & mask];
if (ep->me_key == NULL)
return freeslot == NULL ? ep : freeslot;
if (ep->me_key == key)
return ep;
if (ep->me_hash == hash && ep->me_key != dummy) {
startkey = ep->me_key;
Py_INCREF(startkey);
cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
Py_DECREF(startkey);
if (cmp < 0)
return NULL;
if (ep0 == mp->ma_table && ep->me_key == startkey) {
if (cmp > 0)
return ep;
}
else {
/* The compare did major nasty stuff to the
* dict: start over.
* XXX A clever adversary could prevent this
* XXX from terminating.
*/
return lookdict(mp, key, hash);
}
}
else if (ep->me_key == dummy && freeslot == NULL)
freeslot = ep;
}
assert(0); /* NOT REACHED */
return 0;
}

사전 은 요소 와 검색 요 소 를 추가 할 때 사전 검색 정책 을 사용 해 야 합 니 다.검색 할 때 이 key 가 존재 하지 않 으 면 Unused 상태의 entry 로 돌아 갑 니 다.이 key 가 존재 하지만 key 가 Dummy 대상 이 라면 Dummy 상태의 entry 로 돌아 갑 니 다.다른 경우 Active 상태의 entry 가 존재 한 다 는 뜻 입 니 다.사전 삽입 작업 은상황 에 따라 조작 하 는 것 도 다르다.Active entry 에 대해 서 는 me 를 직접 교체 합 니 다.value 값 이면 됩 니 다.Unused 또는 Dummy 의 entry 에 me 를 동시에 설정 해 야 합 니 다.key，me_hash 와 mevalue
PYDICTOBJECT 대상 버퍼
PyDictObject 대상 버퍼 와 PyListObject 대상 버퍼 의 원 리 는 유사 합 니 다.대상 이 삭 제 될 때 이 대상 을 버퍼 에 추가 하고 PyDictObject 대상 자 체 를 유지 합 니 다.만약 matable 유지 보수 시 시스템 더미 에서 신청 한 공간 입 니 다.Python 은 이 메모 리 를 방출 합 니 다.만약 matable 은 ma 를 유지 합 니 다.smalltable,그러면 smalltable 에 있 는 요소 의 인용 수 를 줄 이면 됩 니 다.

static void
dict_dealloc(register PyDictObject *mp)
{
register PyDictEntry *ep;
Py_ssize_t fill = mp->ma_fill;
PyObject_GC_UnTrack(mp);
Py_TRASHCAN_SAFE_BEGIN(mp)
for (ep = mp->ma_table; fill > 0; ep++) {
if (ep->me_key) {
--fill;
Py_DECREF(ep->me_key);
Py_XDECREF(ep->me_value);
}
}
if (mp->ma_table != mp->ma_smalltable)
PyMem_DEL(mp->ma_table);
if (numfree < PyDict_MAXFREELIST && Py_TYPE(mp) == &PyDict_Type)
free_list[numfree++] = mp;
else
Py_TYPE(mp)->tp_free((PyObject *)mp);
Py_TRASHCAN_SAFE_END(mp)
}

이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.