`
lantian_123
  • 浏览: 1368176 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

Python字典对象实现原理

阅读更多

原文链接:http://foofish.net/blog/92/python_dict_implements

字典类型是Python中最常用的数据类型之一,它是一个键值对的集合,字典通过键来索引,关联到相对的值,理论上它的查询复杂度是 O(1) :

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

字符串的实现原理文章中,曾经出现过字典对象用于intern操作,那么字典的内部结构是怎样的呢?PyDictObject对象就是dict的内部实现。

哈希表 (hash tables)

哈希表(也叫散列表),根据关键值对(Key-value)而直接进行访问的数据结构。它通过把key和value映射到表中一个位置来访问记录,这种查询速度非常快,更新也快。而这个映射函数叫做哈希函数,存放值的数组叫做哈希表。 哈希函数的实现方式决定了哈希表的搜索效率。具体操作过程是:

  1. 数据添加:把key通过哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里。
  2. 数据查询:再次使用哈希函数将key转换为对应的数组下标,并定位到数组的位置获取value。

但是,对key进行hash的时候,不同的key可能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用于缓存me_key的哈希值,防止每次查询时都要计算哈希值,entry有三种状态。

  1. Unused: me_key == me_value == NULL

    Unused是entry的初始状态,key和value都为NULL。插入元素时,Unused状态转换成Active状态。这是me_key为NULL的唯一情况。

  2. Active: me_key != NULL and me_key != dummy 且 me_value != NULL

    插入元素后,entry就成了Active状态,这是me_value唯一不为NULL的情况,删除元素时Active状态刻转换成Dummy状态。

  3. Dummy: me_key == dummy 且 me_value == NULL

    此处的dummy对象实际上一个PyStringObject对象,仅作为指示标志。Dummy状态的元素可以在插入元素的时候将它变成Active状态,但它不可能再变成Unused状态。

为什么entry有Dummy状态呢?这是因为采用开放寻址法中,遇到哈希冲突时会找到下一个合适的位置,例如某元素经过哈希计算应该插入到A处,但是此时A处有元素的,通过探测函数计算得到下一个位置B,仍然有元素,直到找到位置C为止,此时ABC构成了探测链,查找元素时如果hash值相同,那么也是顺着这条探测链不断往后找,当删除探测链中的某个元素时,比如B,如果直接把B从哈希表中移除,即变成Unused状态,那么C就不可能再找到了,因为AC之间出现了断裂的现象,正是如此才出现了第三种状态---Dummy,Dummy是一种类似的伪删除方式,保证探测链的连续性。
python_entry_status

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指向ma_smalltable的首地址,当entry数量大于8时,Python把它当做一个大字典来处理,此刻会申请额外的内存空间,同时将ma_table指向这块空间。
  • ma_lookup:字典元素的搜索策略

PyDictObject使用PyObject_HEAD而不是PyObject_Var_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;
}

  1. 初始化dummy对象
  2. 如果缓冲池还有可用的对象,则从缓冲池中读取,否则,执行步骤3
  3. 分配内存空间,创建PyDictObject对象,初始化对象
  4. 指定添加字典元素时的探测函数,元素的搜索策略

字典搜索策略

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和me_value

PyDictObject对象缓冲池

PyDictObject对象缓冲池和PyListObject对象缓冲池的原理是类似的,都是在对象被销毁的时候把该对象添加到缓冲池中去,而且值保留PyDictObject对象本身,如果ma_table维护的时从系统堆中申请的空间,那么Python会释放这块内存,如果ma_table维护的是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)
}
2
3
分享到:
评论

相关推荐

    Python字典对象实现原理详解

    ### Python字典对象实现原理详解 #### 一、引言 Python字典是Python编程语言中一种非常重要的数据结构,其基本特征是以键值对的形式存储数据。与列表或元组不同,字典中的元素是无序的,通过键来进行快速检索。...

    Python 的字典(Dict)是如何存储的

    在深入探讨Python字典的存储原理之前,我们先来明确几个概念。字典是Python中的一种内置数据结构,它以键值对的形式存储数据。由于其高效的数据查找性能,字典被广泛应用于各种场景。那么,究竟是什么使得Python字典...

    049.Python字典_核心底层原理_内存分析_查找值对象过程.mp4

    049.Python字典_核心底层原理_内存分析_查找值对象过程.mp4

    Python字符串对象实现原理详解

    Python字符串对象的实现原理涉及到内存管理、对象结构和性能优化等多个方面。首先,我们要了解Python中的对象分类。在Python的世界里,对象分为两类:定长对象和变长对象。定长对象如整数,它们在创建时即确定了所需...

    Python字典的核心底层原理讲解

    字典对象的核心是散列表。散列表是一个稀疏数组(总是有空白元素的数组),数组的每个单元叫做 bucket。每个 bucket 有两部分:一个是键对象的引用,一个是值对象的引用。所有 bucket 结构和大小一致,我们可以通过...

    02-python-字典-集合-不可变集合-赋值机制

    在Python编程语言中,字典、集合和不可变集合是三种重要的数据结构,它们各自具有独特的特性和用途。本篇文章将深入探讨这些概念,并详细解释它们的赋值机制。 首先,我们来了解一下**字典(Dictionary)**。字典是...

    Python3-廖雪峰.rar

    同时,Python3还提供了字典和集合这两种无序的数据结构,它们在处理关联数据和去重场景下非常有用。 此外,Python3的文件操作简单易懂,教程会涵盖读写文件、追加内容以及处理二进制文件等内容。Python3还支持高级...

    Python字典数据对象拆分的简单实现方法

    ### Python字典数据对象拆分的简单实现方法 在Python编程中,字典是一种非常重要的数据类型,它允许我们以键值对的形式存储数据。字典的灵活性使其成为处理复杂数据结构的理想选择。本文将详细介绍如何对特定类型的...

    python利用拉链法实现字典方法示例

    实际的Python字典实现会使用更高级的数据结构和优化技术,如开放寻址法、动态调整哈希表大小等,以确保高效的性能。 总结来说,拉链法是一种解决哈希冲突的有效策略,它通过在每个哈希桶内维护一个链表来存储冲突的...

    深入源码解析Python中的对象与类型

    Python中对象分为两类:定长对象(如整数`int`)和非定长对象(如列表`list`和字典`dict`)。这些对象的内部表示通过`PyObject`和`PyVarObject`等结构来实现。 **PyObject结构体定义** ```c typedef struct _object...

    社团检测经典算法实现 python

    通过学习和理解`python-louvain`的实现,你不仅可以掌握Louvain算法,还能深入研究社团检测的原理,这对理解复杂网络的结构和动态有着重要意义。同时,Python的实现使得这一过程更加易于理解和应用。因此,无论你是...

    好玩的python程序的实现(有注释,80多个)

    "好玩的python程序的实现(有注释,80多个)"这个压缩包文件就提供了这样一个丰富的资源库,适合Python初学者深入理解和实践。下面我们将详细探讨这些程序可能包含的知识点。 首先,基础语法是Python学习的核心部分...

    python实现LR_0分析器(带ui界面)

    Python字典可以用来存储状态之间的关系,键为当前状态,值为下一个状态的集合。 5. **生成分析表**:分析表由动作(ACTION)和 goto(GOTO)两部分组成。ACTION表指示在遇到特定标记时应执行的操作,如接受、移进或...

    数据结构概念、栈、队列、链表与数组、字典与对象实现原理(详细的代码)

    python中字典对象实现原理 数组 一. 数据结构中的一些概念 1、数据结构是什么 简单来说,数据结果就是设计数据以何种方式存储在计算机中 比如:列表,集合,与字典等都是一种数据结构 程序 = 数据结构 + 算法 2、...

    Python动态类型实现原理及过程解析

    Python内部维护了一个引用计数器,当对象的引用计数变为0时,该对象的内存会被自动回收,这是Python垃圾回收机制的一部分。 Python中的对象分为可变类型和不可变类型。不可变类型包括数字、字符串和元组,它们的...

    详细探究Python中的字典容器

    Python字典还提供了多种方法,如`keys()`返回所有键组成的列表,`values()`返回所有值组成的列表,`items()`返回键值对的列表,以及`get(key, default)`方法,它允许安全地获取键的值,如果键不存在,会返回指定的...

    基于python的英汉电子词典软件源码数据库.zip

    本文将详细探讨该软件的核心技术、设计原理以及实现细节。 首先,我们要明确的是,Python是一种高级编程语言,以其简洁明了的语法和强大的库支持,在Web开发领域有着广泛的应用。Django是Python的一个著名Web框架,...

    Python源码剖析

    PyDictObject是Python字典的基础,文档可能涵盖了哈希表的实现、查找算法、扩容策略等,这些内容对于优化字典操作和理解Python的动态键值存储机制非常有帮助。 5. **Pyc文件解析**:Python源码剖析16探讨了Pyc文件...

Global site tag (gtag.js) - Google Analytics