Python 사전 대상 실현 원리 상세 설명
>>> 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];
};
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 대상 초기 화
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 와 mevaluePYDICTOBJECT 대상 버퍼
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)
}
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
로마 숫자를 정수로 또는 그 반대로 변환그 중 하나는 로마 숫자를 정수로 변환하는 함수를 만드는 것이었고 두 번째는 그 반대를 수행하는 함수를 만드는 것이었습니다. 문자만 포함합니다'I', 'V', 'X', 'L', 'C', 'D', 'M' ; 문자열이 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.