Python 가상 머신에서 사전의 구현 원리는 무엇입니까?

사전 데이터 구조 분석

/* The ma_values pointer is NULL for a combined table
 * or points to an array of PyObject* for a split table
 */
typedef struct {
    PyObject_HEAD
    Py_ssize_t ma_used;
    PyDictKeysObject *ma_keys;
    PyObject **ma_values;
} PyDictObject;
 
struct _dictkeysobject {
    Py_ssize_t dk_refcnt;
    Py_ssize_t dk_size;
    dict_lookup_func dk_lookup;
    Py_ssize_t dk_usable;
    PyDictKeyEntry dk_entries[1];
};
 
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;

위의 각 필드의 의미는 다음과 같습니다.

• ob_refcnt, 개체의 참조 횟수.

• ob_type, 객체의 데이터 유형입니다.

• ma_used, 현재 해시 테이블의 데이터 수입니다.

• ma_keys는 키-값 쌍을 포함하는 배열을 가리킵니다.

• ma_values, 이것은 값을 가리키는 배열이지만, 이 값은 cpython의 특정 구현에서 반드시 사용되지는 않습니다. 왜냐하면 _dictkeysobject의 PyDictKeyEntry 배열에 있는 객체도 값을 저장할 수 있기 때문입니다. 키는 모두 문자열입니다. 이 기사에서는 PyDictKeyEntry의 값이 주로 사전 구현을 논의하는 데 사용되므로 이 변수를 무시할 수 있습니다.

• dk_refcnt, 이는 참조 카운팅을 나타내는 데에도 사용됩니다. 이는 사전 뷰와 관련이 있으므로 여기서는 지금은 신경 쓰지 않겠습니다.

• dk_size는 해시 테이블의 크기를 나타내며 2n이어야 합니다. 이 경우 모듈식 연산은 비트별 AND 연산으로 바뀔 수 있습니다.

• dk_lookup, 이는 해시 테이블의 조회 함수를 나타내며 함수 포인터입니다.

• dk_usable은 현재 배열에서 사용 가능한 키-값 쌍 수를 나타냅니다.

• dk_entries, 키-값 쌍이 실제로 저장되는 해시 테이블입니다.

전체 해시 테이블의 레이아웃은 대략 아래 그림과 같습니다.

새 사전 개체 만들기

이 기능은 비교적 간단합니다. 먼저 메모리 공간을 적용한 다음 몇 가지 초기화 작업을 수행합니다. 키-값 쌍 저장을 위한 해시 테이블을 신청하세요.

static PyObject *
dict_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
{
    PyObject *self;
    PyDictObject *d;
 
    assert(type != NULL && type->tp_alloc != NULL);
    // 申请内存空间
    self = type->tp_alloc(type, 0);
    if (self == NULL)
        return NULL;
    d = (PyDictObject *)self;
 
    /* The object has been implicitly tracked by tp_alloc */
    if (type == &PyDict_Type)
        _PyObject_GC_UNTRACK(d);
    // 因为还没有增加数据 因此哈希表当中 ma_used = 0
    d->ma_used = 0;
    // 申请保存键值对的数组  PyDict_MINSIZE_COMBINED 是一个宏定义 值为 8 表示哈希表数组的最小长度
    d->ma_keys = new_keys_object(PyDict_MINSIZE_COMBINED);
    // 如果申请失败返回 NULL
    if (d->ma_keys == NULL) {
        Py_DECREF(self);
        return NULL;
    }
    return self;
}
 
// new_keys_object 函数如下所示
static PyDictKeysObject *new_keys_object(Py_ssize_t size)
{
    PyDictKeysObject *dk;
    Py_ssize_t i;
    PyDictKeyEntry *ep0;
 
    assert(size >= PyDict_MINSIZE_SPLIT);
    assert(IS_POWER_OF_2(size));
    // 这里是申请内存的位置真正申请内存空间的大小为 PyDictKeysObject 的大小加上 size-1 个PyDictKeyEntry的大小
    // 这里你可能会有一位为啥不是 size 个 PyDictKeyEntry 的大小 因为在结构体 PyDictKeysObject 当中已经申请了一个 PyDictKeyEntry 对象了
    dk = PyMem_MALLOC(sizeof(PyDictKeysObject) +
                      sizeof(PyDictKeyEntry) * (size-1));
    if (dk == NULL) {
        PyErr_NoMemory();
        return NULL;
    }
    // 下面主要是一些初始化的操作 dk_refcnt 设置成 1 因为目前只有一个字典对象使用 这个 PyDictKeysObject 对象
    DK_DEBUG_INCREF dk->dk_refcnt = 1;
    dk->dk_size = size; // 哈希表的大小
    // 下面这行代码主要是表示哈希表当中目前还能存储多少个键值对 在 cpython 的实现当中允许有 2/3 的数组空间去存储数据 超过这个数则需要进行扩容
    dk->dk_usable = USABLE_FRACTION(size); // #define USABLE_FRACTION(n) ((((n) << 1)+1)/3)
    ep0 = &dk->dk_entries[0];
    /* Hash value of slot 0 is used by popitem, so it must be initialized */
    ep0->me_hash = 0;
    // 将所有的键值对初始化成 NULL
    for (i = 0; i < size; i++) {
        ep0[i].me_key = NULL;
        ep0[i].me_value = NULL;
    }
    dk->dk_lookup = lookdict_unicode_nodummy;
    return dk;
}

해시 테이블 확장 메커니즘

우선 사전 구현 시 해시 테이블의 확장 메커니즘을 이해해 보겠습니다. 계속해서 사전에 새 데이터를 추가하면 사전에 있는 데이터가 곧 배열 길이에 도달하게 됩니다. 23. 이때 확장이 필요합니다. 확장 후 배열 크기는 다음과 같이 계산됩니다.

#define GROWTH_RATE(d) (((d)->ma_used*2)+((d)->ma_keys->dk_size>>1))

새 배열의 크기는 원래 키-값 쌍 수에 2를 곱하고 원래 배열 길이의 절반을 더한 값과 같습니다. .

일반적으로 확장에는 세 가지 주요 단계가 있습니다.

• 새 배열의 크기를 계산합니다.

• 새 배열을 만듭니다.

• 원본 해시 테이블의 데이터를 새 배열에 추가합니다(즉, 재해싱 프로세스).

구체적인 구현 코드는 다음과 같습니다.

static int
insertion_resize(PyDictObject *mp)
{
    return dictresize(mp, GROWTH_RATE(mp));
}
 
static int
dictresize(PyDictObject *mp, Py_ssize_t minused)
{
    Py_ssize_t newsize;
    PyDictKeysObject *oldkeys;
    PyObject **oldvalues;
    Py_ssize_t i, oldsize;
    // 下面的代码的主要作用就是计算得到能够大于等于 minused 最小的 2 的整数次幂
/* Find the smallest table size > minused. */
    for (newsize = PyDict_MINSIZE_COMBINED;
         newsize <= minused && newsize > 0;
         newsize <<= 1)
        ;
    if (newsize <= 0) {
        PyErr_NoMemory();
        return -1;
    }
    oldkeys = mp->ma_keys;
    oldvalues = mp->ma_values;
    /* Allocate a new table. */
   // 创建新的数组
    mp->ma_keys = new_keys_object(newsize);
    if (mp->ma_keys == NULL) {
        mp->ma_keys = oldkeys;
        return -1;
    }
    if (oldkeys->dk_lookup == lookdict)
        mp->ma_keys->dk_lookup = lookdict;
    oldsize = DK_SIZE(oldkeys);
    mp->ma_values = NULL;
    /* If empty then nothing to copy so just return */
    if (oldsize == 1) {
        assert(oldkeys == Py_EMPTY_KEYS);
        DK_DECREF(oldkeys);
        return 0;
    }
    /* Main loop below assumes we can transfer refcount to new keys
     * and that value is stored in me_value.
     * Increment ref-counts and copy values here to compensate
     * This (resizing a split table) should be relatively rare */
    if (oldvalues != NULL) {
        for (i = 0; i < oldsize; i++) {
            if (oldvalues[i] != NULL) {
                Py_INCREF(oldkeys->dk_entries[i].me_key);
                oldkeys->dk_entries[i].me_value = oldvalues[i];
            }
        }
    }
    /* Main loop */
    // 将原来数组当中的元素加入到新的数组当中
    for (i = 0; i < oldsize; i++) {
        PyDictKeyEntry *ep = &oldkeys->dk_entries[i];
        if (ep->me_value != NULL) {
            assert(ep->me_key != dummy);
            insertdict_clean(mp, ep->me_key, ep->me_hash, ep->me_value);
        }
    }
    // 更新一下当前哈希表当中能够插入多少数据
    mp->ma_keys->dk_usable -= mp->ma_used;
    if (oldvalues != NULL) {
        /* NULL out me_value slot in oldkeys, in case it was shared */
        for (i = 0; i < oldsize; i++)
            oldkeys->dk_entries[i].me_value = NULL;
        assert(oldvalues != empty_values);
        free_values(oldvalues);
        DK_DECREF(oldkeys);
    }
    else {
        assert(oldkeys->dk_lookup != lookdict_split);
        if (oldkeys->dk_lookup != lookdict_unicode_nodummy) {
            PyDictKeyEntry *ep0 = &oldkeys->dk_entries[0];
            for (i = 0; i < oldsize; i++) {
                if (ep0[i].me_key == dummy)
                    Py_DECREF(dummy);
            }
        }
        assert(oldkeys->dk_refcnt == 1);
        DK_DEBUG_DECREF PyMem_FREE(oldkeys);
    }
    return 0;
}

사전에 데이터 삽입

사전에 데이터를 계속 삽입하면 해시 충돌이 발생할 가능성이 높습니다. 사전의 해시 충돌 처리 방법은 기본적으로 집합입니다. 해시 충돌을 처리하는 방법은 모두 개발 주소 방법을 사용하지만 이 공개 주소 방법의 구현은 다음과 같습니다.

위 내용은 Python 가상 머신에서 사전의 구현 원리는 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!