Python dictionary implementation

해당 글은 http://www.laurentluce.com/posts/python-dictionary-implementation/의 글을 번역한 것입니다.

해당 글의 소스는 python2를 기준으로 작성되었으며 python버전에 따라 다를 수 있습니다.

dictionary은 키로 색인되며 연관 배열로 표시될 수 있습니다. dictionary에 3 개의 키 / 값 쌍을 추가해 봅시다 :

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

이 방법으로 값에 액세스 할 수 있습니다.

>>> d['a']
1
>>> d['b']
2
>>> d['c']
3
>>> d['d']
Traceback (most recent call last)
  File "<stdin>", line 1, in <module>
KeyError: 'd'

키 'd'가 존재하지 않으므로 KeyError 예외가 발생합니다.

해시 테이블

파이썬 dictionary은 해시 테이블을 사용하여 구현됩니다. 키의 해시 함수를 사용하여 인덱스를 얻는 배열입니다. 해시 함수의 목표는 배열에 키를 균등하게 분배하는 것입니다. 좋은 해시 기능은 충돌 횟수를 최소화합니다 (예 : 동일한 해시를 갖는 다른 키). 파이썬에는 이런 종류의 해시 함수가 없습니다. 가장 중요한 해시 함수 (문자열 및 정수)는 일반적인 경우 매우 규칙적입니다.

>>> map(hash, (0, 1, 2, 3))
[0, 1, 2, 3]
>>> map(hash, ("namea", "nameb", "namec", "named"))
[-1658398457, -1658398460, -1658398459, -1658398462]

이 게시물의 나머지 부분에서 문자열을 키로 사용한다고 가정합니다. 파이썬에서 문자열의 해시 함수는 다음과 같이 정의됩니다

arguments: string object
returns: hash
function string_hash:
    if hash cached:
        return it
    set len to string's length
    initialize var p pointing to 1st char of string object
    set x to value pointed by p left shifted by 7 bits
    while len >= 0:
        set var x to (1000003 * x) xor value pointed by p
        increment pointer p
    set x to x xor length of string object
    cache x as the hash so we don't need to calculate it again
    return x as the hash

Python에서 hash ( 'a')를 실행하면 string_hash()가 실행되고 12416037344(python 3.3 이상부터는 해시 값이 일정하지 않고 계속 바뀝니다. )가 반환됩니다. 여기에서는 64 비트 컴퓨터를 사용한다고 가정합니다.

크기 x의 배열을 사용하여 키 / 값 쌍을 저장하는 경우 x-1과 같은 마스크를 사용하여 배열에서 쌍의 슬롯 인덱스를 계산합니다. 이것은 슬롯 인덱스의 계산을 빠르게 합니다. 빈 슬롯을 찾을 확률은 아래 설명된 크기 조정 메커니즘으로 인해 높습니다. 이는 대부분의 경우 간단한 계산을 하는 것이 의미가 있음을 의미합니다. 배열의 크기가 8이면 'a'에 대한 색인은 hash ( 'a') & 7 = 0입니다. 'b'에 대한 색인은 3이고 'c'에 대한 색인은 2이고 'z'는 3이며 'b'와 같습니다. 여기서 충돌이 있습니다.

우리는 키가 연속적 일 때 파이썬 해시 함수가 잘 작동한다는 것을 알 수 있습니다. 이 유형의 데이터를 다루는 것이 일반적이기 때문에 좋습니다. 그러나 키 'z'를 추가하면 연속적이지 않기 때문에 충돌이 발생합니다.

연결된 해시를 사용하여 동일한 해시를 가진 쌍을 저장할 수는 있지만 더 이상 O(1) 평균이 아닌 조회 시간이 늘어납니다. 다음 섹션에서는 Python dictionary에 사용되는 충돌 해결 방법에 대해 설명합니다.

열린 주소 지정

열린 주소 지정은 프로빙이 사용되는 충돌 해결 방법입니다. 'z'의 경우 슬롯 인덱스 3이 이미 배열에 사용되었으므로 아직 사용되지 않은 인덱스를 찾으려면 다른 인덱스를 검사해야 합니다. 키 / 값 쌍을 추가하면 평균 O (1) 및 조회 작업도 수행됩니다.

2 차 프로빙 시퀀스는 빈 슬롯을 찾는 데 사용됩니다. 코드는 다음과 같습니다.

j = (5*j) + 1 + perturb;
perturb >>= PERTURB_SHIFT;
use j % 2**i as the next table index;

5 * j + 1에서 초기 인덱스에 영향을 미치지 않는 비트의 작은 차이가 빠르게 확대됩니다. 변수 "perturb"는 해시 코드의 다른 비트를 재생합니다.

테이블 크기가 32이고 j = 3 일 때 프로빙 시퀀스를 살펴보겠습니다. 3-> 11-> 19-> 29-> 5-> 6-> 16-> 31-> 28-> 13 -> 2…

dictobject.c의 소스 코드에서 이 프로빙 시퀀스에 대한 자세한 내용을 읽을 수 있습니다.

자, 파이썬 내부 코드와 예제를 보자.

Dictionary c 구조

dictionary 항목을 저장하는 데 다음 c 구조가 사용됩니다 : 키 / 값 쌍. 해시, 키 및 값이 저장됩니다. PyObject는 Python 객체의 기본 클래스입니다.

typedef struct {
    Py_ssize_t me_hash;
    PyObject *me_key;
    PyObject *me_value;
} PyDictEntry;

다음 구조는 dictionary을 나타냅니다. ma_fill은 사용된 슬롯 수 + 더미 슬롯입니다. 키 페어를 제거하면 슬롯이 더미로 표시됩니다. ma_used는 사용 된 슬롯 수 (활성)입니다. ma_mask는 배열의 크기에서 1을 뺀 것과 같으며 슬롯 인덱스를 계산하는 데 사용됩니다. ma_table은 배열이고 ma_smalltable은 크기 8의 초기 배열입니다.

/* python2 */

typedef struct _dictobject PyDictObject;
struct _dictobject {
    PyObject_HEAD
    Py_ssize_t ma_fill;
    Py_ssize_t ma_used;
    Py_ssize_t ma_mask;
    PyDictEntry *ma_table;
    PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
    PyDictEntry ma_smalltable[PyDict_MINSIZE];
};


/* python3 */

typedef struct {
    PyObject_HEAD
    uint64_t ma_version_tag;
    PyDictKeysObject *ma_keys;
    PyObject **ma_values;
} PyDictObject;

dictionary 초기화

dictionary을 처음 만들면 PyDict_New() 함수가 호출됩니다. 몇 가지 줄을 제거하고 핵심 개념에 집중하기 위해 C 코드를 의사 코드로 변환했습니다.

returns new dictionary object
function PyDict_New:
    allocate new dictionary object
    clear dictionary's table
    set dictionary's number of used slots + dummy slots (ma_fill) to 0
    set dictionary's number of active slots (ma_used) to 0
    set dictionary's mask (ma_value) to dictionary size - 1 = 7
    set dictionary's lookup function to lookdict_string
    return allocated dictionary object

아이템 추가

새로운 키 / 값 쌍이 추가되면 PyDict_SetItem()이 호출됩니다. 이 함수는 dictionary 객체와 키 / 값 쌍에 대한 포인터를 사용합니다. 키가 문자열인지 확인하고 해시를 계산하거나 캐시 된 키가 있으면 이를 재사용합니다. 새로운 키 / 값 쌍을 추가하기 위해 insertdict()가 호출되며 사용 된 슬롯 수 + 더미 슬롯 수가 배열 크기의 2/3보다 큰 경우 사전의 크기가 조정됩니다.

왜 2/3일까요? 프로빙 시퀀스가 빈 슬롯을 충분히 빨리 찾을 수 있도록 하는 것입니다. 나중에 크기 조정 기능을 살펴보겠습니다.

arguments: dictionary, key, value
returns: 0 if OK or -1
function PyDict_SetItem:
    if key's hash cached:
        use hash
    else:
        calculate hash
    call insertdict with dictionary object, key, hash and value
    if key/value pair added successfully and capacity over 2/3:
        call dictresize to resize dictionary's table

inserdict()는 조회 함수 lookdict_string()을 사용하여 빈 슬롯을 찾습니다. 이것은 키를 찾는 데 사용된 것과 동일한 기능입니다. lookdict_string()은 해시와 마스크 값을 사용하여 슬롯 인덱스를 계산합니다. 슬롯 인덱스 = 해시 및 마스크에서 키를 찾을 수 없으면 사용 가능한 슬롯을 찾을 때까지 위에서 설명한 루프를 사용하여 프로빙을 시작합니다. 첫 번째 탐색 시도에서 키가 null이면 첫 번째 조회 중에 발견되면 더미 슬롯을 반환합니다. 이전에 삭제 한 슬롯을 다시 사용하는 것이 우선합니다.

다음 키 / 값 쌍을 추가하려고 합니다 : { 'a': 1, 'b': 2 ', 'z ': 26, 'y ': 25, 'c ': 5, 'x ': 24}.

dictionary 구조는 내부 테이블 크기가 8로 할당됩니다.

PyDict_SetItem : 키 = 'a', 값 = 1
- 해시 ( 'a') = 12416037344
- 삽입
  - lookdict_string
    - 슬롯 인덱스 = 해시 및 마스크 = 12416037344 및 7 = 0
    - 슬롯 0은 사용되지 않으므로 반환
  - 키, 값 및 해시를 사용하여 인덱스 0에서 초기화 항목
  - ma_used = 1, ma_fill = 1
PyDict_SetItem : 키 = 'b', 값 = 2
- 해시 ( 'b') = 12544037731
- 삽입
  - lookdict_string
    - 슬롯 인덱스 = 해시 및 마스크 = 12544037731 및 7 = 3
    - 슬롯 3은 사용되지 않으므로 반환
  - 키, 값 및 해시를 사용하여 인덱스 3에서 초기화 항목
  - ma_used = 2, ma_fill = 2
PyDict_SetItem : 키 = 'z', 값 = 26
- 해시 ( 'z') = 15616046971
- 삽입
  - lookdict_string
    - 슬롯 인덱스 = 해시 및 마스크 = 15616046971 및 7 = 3
    - 슬롯 3이 사용되므로 다른 슬롯에 대한 프로브 5는 비어 있습니다
  - 키, 값 및 해시를 사용하여 인덱스 5에서 초기화 항목
  - ma_used = 3, ma_fill = 3
PyDict_SetItem : 키 = 'y', 값 = 25
- 해시 ( 'y') = 15488046584
- 삽입
  - lookdict_string
    - 슬롯 인덱스 = 해시 및 마스크 = 15488046584 및 7 = 0
    - 슬롯 0이 사용되므로 다른 슬롯에 대한 프로브 : 1은 비어 있습니다.
  - 키, 값 및 해시를 사용하여 인덱스 1의 초기화 항목
  - ma_used = 4, ma_fill = 4
PyDict_SetItem : 키 = 'c', 값 = 3
- 해시 ( 'c') = 12672038114
- 삽입
  - lookdict_string
    - 슬롯 인덱스 = 해시 및 마스크 = 12672038114 및 7 = 2
    - 슬롯 2는 비어 있으므로 반환
  - 키, 값 및 해시로 인덱스 2에서 초기화 항목
  - ma_used = 5, ma_fill = 5
PyDict_SetItem : 키 = 'x', 값 = 24
- 해시 = 해시 ( 'x') = 15360046201
- 삽입
  - lookdict_string
    - 슬롯 인덱스 = 해시 및 마스크 = 15360046201 & 7 = 1
    - 슬롯 1이 사용되므로 다른 슬롯에 대한 프로브 : 7은 비어 있습니다
  - 키, 값 및 해시를 사용하여 인덱스 7에서 초기화 항목
  - ma_used = 6, ma_fill = 6

8의 6 개 슬롯이 이제 사용되므로 array용량의 2/3 이상입니다. 더 큰 배열을 할당하기 위해 dictresize()가 호출됩니다. 이 함수는 또한 이전 테이블 항목을 새 테이블로 복사하는 작업도 수행합니다.

dictresize()는 4 * ma_used 인 경우 마이너스 = 24로 호출됩니다. 2 * ma_used는 사용된 슬롯 수가 매우 많을 때 (50000보다 큰 경우) 사용됩니다. 사용 된 슬롯 수의 4배인 이유는 크기 조정 단계의 수를 줄이고 sparseness를 증가시킵니다.

새로운 테이블 크기는 24보다 커야 하며 24보다 커질 때까지 현재 크기를 1 비트 왼쪽으로 이동하여 계산됩니다. 8-> 16-> 32가 됩니다.

이것은 크기 조정 중 테이블에서 발생하는 것입니다. 크기가 32 인 새 테이블이 할당됩니다. 기존 테이블 항목은 새 마스크 값인 31을 사용하여 새 테이블에 삽입됩니다. 다음과 같이 끝납니다.

아이템 제거

항목을 제거하기 위해 PyDict_DelItem()이 호출됩니다. 이 키의 해시가 계산되고 항목을 반환하기 위해 조회 기능이 호출됩니다. 슬롯은 이제 더미 슬롯입니다.

사전에서 키 'c'를 제거하고 싶습니다. 우리는 다음 배열로 끝납니다.

사용된 슬롯 수가 총 슬롯 수보다 훨씬 적은 경우 항목 삭제 작업은 배열 크기 조정을 트리거하지 않습니다. 그러나 키 / 값 쌍이 추가되면 크기 조정의 필요성은 사용 된 슬롯 수 + 더미 슬롯을 기반으로 하므로 배열도 축소할 수 있습니다.

저작자표시

'app > python' 카테고리의 다른 글

The internals of Python string interning (0)	2020.04.01
wsgi를 왜 쓰나요 (3)	2020.03.31
python list implementation (0)	2020.03.20
Python string objects implementation (0)	2020.03.19
Python integer objects implementation (0)	2020.03.18

조아하는모든것

Python dictionary implementation

해시 테이블

열린 주소 지정

Dictionary c 구조

dictionary 초기화

아이템 추가

아이템 제거

'app > python' 카테고리의 다른 글

티스토리툴바

Python dictionary implementation

해시 테이블

열린 주소 지정

Dictionary c 구조

dictionary 초기화

아이템 추가

아이템 제거

'app > python' 카테고리의 다른 글

'app/python' Related Articles

티스토리툴바