list 对象 list 对象的定义
list对象内部是使用数组实现，在数组中存储的是指针，指向要保存的对象。
allocated是list中数组的大小，ob_size是当前已经使用的数组大小。
typedef struct { // 可变长对象中有 ob_size，保存当前已经使用的数组大小 PyObject_VAR_HEAD PyObject **ob_item; // 数组的指针 Py_ssize_t allocated; // 分配的数组长度 } PyListObject; list 对象的缓存list对象有缓存机制，对象在释放时会保存到空闲缓存池，待下一次申请的时候使用。 缓存池可以缓存80个list对象，缓存池满的时候list对象直接释放。
从list对象的创建和销毁过程了解它的缓存机制（为了关注重点，代码被简化过）。
// 缓存池的大小定义 #define PyList_MAXFREELIST 80 // 创建新的list对象 PyObject* PyList_New(Py_ssize_t size) { PyListObject *op; size_t nbytes = size * sizeof(PyObject *); // 如果缓存有空闲，直接从缓存中分配list对象的内存 if (numfree) { numfree--; op = free_list[numfree]; _Py_NewReference((PyObject *)op); } else { op = PyObject_GC_New(PyListObject, &PyList_Type); if (op == NULL) return NULL; } if (size <= 0) op->ob_item = NULL; else { op->ob_item = (PyObject **) PyMem_MALLOC(nbytes); if (op->ob_item == NULL) { Py_DECREF(op); return PyErr_NoMemory(); } memset(op->ob_item, 0, nbytes); } Py_SIZE(op) = size; op->allocated = size; _PyObject_GC_TRACK(op); return (PyObject *) op; } // 销毁list对象 static void list_dealloc(PyListObject *op) { Py_ssize_t i; PyObject_GC_UnTrack(op); Py_TRASHCAN_SAFE_BEGIN(op) if (op->ob_item != NULL) { i = Py_SIZE(op); while (--i >= 0) { Py_XDECREF(op->ob_item[i]); } PyMem_FREE(op->ob_item); } // 保存list对象到空闲的缓存 if (numfree < PyList_MAXFREELIST && PyList_CheckExact(op)) free_list[numfree++] = op; else Py_TYPE(op)->tp_free((PyObject *)op); Py_TRASHCAN_SAFE_END(op) } list 的插入，删除，添加操作list的内部实现是数组，所以在插入和删除的操作会引起内部元素的移动。在添加操作时，如果目前list对象分配的内存没有使用完，则直接在尾部追加。
看下list的插入和添加操作。
// 插入操作 int PyList_Insert(PyObject *op, Py_ssize_t where, PyObject *newitem) { if (!PyList_Check(op)) { PyErr_BadInternalCall(); return -1; } return ins1((PyListObject *)op, where, newitem); } static int ins1(PyListObject *self, Py_ssize_t where, PyObject *v) { Py_ssize_t i, n = Py_SIZE(self); PyObject **items; if (v == NULL) { PyErr_BadInternalCall(); return -1; } if (n == PY_SSIZE_T_MAX) { PyErr_SetString(PyExc_OverflowError, "cannot add more objects to list"); return -1; } // 判断是否重新分配长度 if (list_resize(self, n+1) == -1) return -1; // 寻找插入点 if (where < 0) { where += n; if (where < 0) where = 0; } if (where > n) where = n; // 移动元素 items = self->ob_item; for (i = n; --i >= where; ) items[i+1] = items[i]; Py_INCREF(v); items[where] = v; return 0; } // 添加操作 int PyList_Append(PyObject *op, PyObject *newitem) { if (PyList_Check(op) && (newitem != NULL)) return app1((PyListObject *)op, newitem); PyErr_BadInternalCall(); return -1;}static int app1(PyListObject *self, PyObject *v){ Py_ssize_t n = PyList_GET_SIZE(self); assert (v != NULL); if (n == PY_SSIZE_T_MAX) { PyErr_SetString(PyExc_OverflowError, "cannot add more objects to list"); return -1; } if (list_resize(self, n+1) == -1) return -1; Py_INCREF(v); PyList_SET_ITEM(self, n, v); return 0; } list对象总结
list对象内部有定量的缓存，提高创建list对象的速度
list对象的插入，删除操作成本较高，不适宜频繁操作。
append操作速度较快。
dict 对象 dict对象的定义dict对象的实现内部是散列表，散列函数采用的开放地址法，理论上算法的时间复杂度是 O(1) 。
dict对象在散列表小于8的时候，使用对象内部数组 ma_smalltable 的内存。
// 内部数组空间，创建长度较小的散列时使用 #define PyDict_MINSIZE 8 // 散列表的数据项 typedef struct { Py_ssize_t me_hash; PyObject *me_key; PyObject *me_value;} PyDictEntry;// dict 对象struct _dictobject { PyObject_HEAD Py_ssize_t ma_fill; // 使用的计数 + 伪删除的dummy计数 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]; // 内部优化，散列表较小时的内存 }; dict对象的缓存dict对象也有缓存机制，对象释放时保存到缓存池中，待下一次申请的时候使用。缓存池可以缓存80个dict对象，缓存池满的时候dict对象直接释放。
从dict对象的创建和销毁过程了解它的缓存机制（为了关注重点，代码被简化过）。
// 缓存池的大小定义 #define PyDict_MAXFREELIST 80 // 创建 dict 对象 PyObject* PyDict_New(void) { register PyDictObject *mp; // 创建 dummy对象，在删除的时候占位使用 if (dummy == NULL) { /* Auto-initialize dummy */ dummy = PyString_FromString("<dummy key>"); if (dummy == NULL) return NULL; } // 判断如果缓存有空闲，使用缓存中的 dict对象 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 { 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; } // 释放dict的函数 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); // 如果缓存还有空闲空间，则缓存释放的 dict 对象 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) } 开放地址散列表的主要查找算法dict 对象散列查找算法，首先比较key是否相同，不相同则探测下一个位置，一直到找到元素，或者查找失败。在查找失败的时候，返回第一个可用的位置。
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 { // 散列hash匹配，进一步查找 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 { return lookdict(mp, key, hash); } } freeslot = NULL; } // 在探测链上寻找匹配项 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 { return lookdict(mp, key, hash); } } else if (ep->me_key == dummy && freeslot == NULL) freeslot = ep; } return 0; } dict 对象总结
dict对象采用开放地址散列法。
dict对象内部有定量的缓存，提高创建dict对象的速度。
对于长度较小的dict对象，直接使用对象内部的内存，无需二次分配内存，性能较好。