『Python底层原理』--Python字典的实现机制

在Python中，字典（dict）是一种极为强大且常用的内置数据结构，它以键值对的形式存储数据，并提供了高效的查找、插入和删除操作。

接下来，我们将深入探究 Python 字典背后的实现机制，特别是其与哈希表的关系，以及在 CPython 中的具体实现。

1. 哈希表

字典用于存储 Python 中的键值对，为我们提供了快速访问和存储数据的方法。

哈希表（Hash Table）则是实现字典功能的核心技术之一。

本质上，哈希表是基于哈希函数的数据结构，通过将键映射到特定索引位置，实现快速数据访问。

Python 字典正是利用哈希表这一特性，把键值对存储在哈希表中，让我们能通过键迅速获取对应的值。

2. 实现原理

在Python中，字典通过哈希表实现其功能。

具体来说，字典的键被传递给一个哈希函数，该函数计算出一个哈希值。

然后，这个哈希值被用来确定键值对在内存中的存储位置。

当需要查找某个键对应的值时，字典会再次计算该键的哈希值，并直接定位到存储位置，从而快速返回对应的值。

2.1. 存储方式

Python字典的存储方式基于一个动态数组，其中每个元素是一个键值对的引用。

这个数组的大小会根据字典的负载因子（Load Factor）动态调整。

负载因子是字典中存储的键值对数量与哈希表大小的比值，当负载因子超过一定阈值（如0.66）时，哈希表会扩容，以避免过多的哈希冲突，从而保持高效的查找性能。

2.2. 哈希冲突

哈希冲突是哈希表中不可避免的问题。

在Python字典中，哈希冲突通过“开放寻址法”解决。

当两个键的哈希值映射到同一个存储位置时，字典会寻找下一个空闲的位置来存储冲突的键值对。

这种方法称为“线性探测”，如果连续的位置都被占用，字典会继续寻找，直到找到一个空闲位置。

这种策略虽然简单，但在某些情况下可能会导致性能下降，尤其是在哈希表接近满载时。

2.3. 字典性能

字典的性能主要取决于哈希函数的质量和哈希表的负载因子。

在理想情况下，字典的查找、插入和删除操作的平均时间复杂度为O(1)。

然而，在最坏情况下（如大量哈希冲突），时间复杂度可能会退化到O(n)。

为了避免这种情况，Python字典会动态调整哈希表的大小，以保持较低的负载因子。

python中的字典实现">3. CPython中的字典实现

在CPython的源代码中，字典的实现位于Objects/dictobject.c文件中。

这个文件包含了字典的所有核心操作，如初始化、查找、插入和删除等。

比如字典创建的代码：

static PyObject *
dict_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
{assert(type != NULL);assert(type->tp_alloc != NULL);// dict subclasses must implement the GC protocolassert(_PyType_IS_GC(type));PyObject *self = type->tp_alloc(type, 0);if (self == NULL) {return NULL;}PyDictObject *d = (PyDictObject *)self;d->ma_used = 0;d->_ma_watcher_tag = 0;dictkeys_incref(Py_EMPTY_KEYS);d->ma_keys = Py_EMPTY_KEYS;d->ma_values = NULL;ASSERT_CONSISTENT(d);if (!_PyObject_GC_IS_TRACKED(d)) {_PyObject_GC_TRACK(d);}return self;
}

字典对象由PyDictObject结构体定义（Include/cpython/dictobject.h）：

typedef struct {PyObject_HEAD// 省略...PyDictKeysObject *ma_keys;/* If ma_values is NULL, the table is "combined": keys and valuesare stored in ma_keys.If ma_values is not NULL, the table is split:keys are stored in ma_keys and values are stored in ma_values */PyDictValues *ma_values;
} PyDictObject;

其中，PyDictKeysObject是一个存储键值对的数组。

// 位于文件：Include/cpython/dictobject.h
typedef struct _dictkeysobject PyDictKeysObject;// 位于文件：Include/internal/pycore_dict.h
struct _dictkeysobject {Py_ssize_t dk_refcnt;// 省略...
};

在CPython中，字典的实现采用了紧凑的内存布局，以减少内存浪费。

每个键值对都被存储在一个结构体中，而这些结构体则被存储在一个动态数组中。

当需要扩容时，字典会重新分配一个更大的数组，并将所有键值对重新哈希到新的数组中。

这种实现方式虽然在扩容时会带来一定的性能开销，但通过合理的负载因子控制，可以有效避免频繁的扩容操作。

4. 字典的应用场景

Python字典作为一种高效的数据结构，在实际开发中有着广泛的应用。

下面列举一些从实际项目中摘取的一些使用字典的代码片段。

4.1. 存储配置信息

字典是存储配置信息的理想选择，因为它允许通过键快速访问对应的值。

比如，在一个Web应用程序中，我们经常使用字典来存储数据库配置、API密钥或其他运行时参数：

config = {"database": {"host": "localhost","port": 3306,"user": "root","password": "password"},"api_keys": {"google_maps": "YOUR_GOOGLE_MAPS_API_KEY","weather": "YOUR_WEATHER_API_KEY"}
}# 访问配置
db_host = config["database"]["host"]
api_key = config["api_keys"]["google_maps"]

这种方式不仅清晰易懂，还便于后续的修改和扩展。

4.2. 缓存数据

字典的高效查找特性使其非常适合用作缓存机制。通过将计算结果存储在字典中，可以避免重复计算，从而显著提高程序的性能。

例如，以下代码展示了如何使用字典缓存斐波那契数列的计算结果：

cache = {}def fibonacci(n):if n in cache:return cache[n]if n <= 1:return ncache[n] = fibonacci(n - 1) + fibonacci(n - 2)return cache[n]# 使用缓存
print(fibonacci(30))  # 计算速度快，且避免了重复计算

在上述代码中，cache字典存储了已经计算过的斐波那契数，从而避免了重复计算，显著提高了程序的运行效率。

4.3. 对象属性存储

在某些场景下，字典可以用来模拟对象的属性存储，特别是当需要动态添加或删除属性时。

例如，可以使用字典来实现一个简单的动态对象：

class DynamicObject:def __init__(self):self.__dict__ = {}def __getattr__(self, name):return self.__dict__.get(name)def __setattr__(self, name, value):self.__dict__[name] = value# 使用动态对象
obj = DynamicObject()
obj.name = "Alice"
obj.age = 25print(obj.name)  # 输出: Alice
print(obj.age)   # 输出: 25

这种方式允许在运行时动态地添加和访问属性，提供了极大的灵活性。

4.4. 计数器

字典可以用来统计元素的出现次数，例如在文本处理中统计单词的频率。

以下代码展示了如何使用字典实现一个简单的单词计数器：

text = "hello world hello Python world"
word_count = {}for word in text.split():if word in word_count:word_count[word] += 1else:word_count[word] = 1print(word_count)  # 输出: {'hello': 2, 'world': 2, 'Python': 1}

通过字典的键值对结构，可以轻松地统计每个单词的出现次数，并且查找和更新操作都非常高效。

4.5. 状态管理

在复杂的应用程序中，字典可以用来管理状态信息。

例如，在一个游戏开发场景中，可以使用字典来存储玩家的状态：

player_state = {"health": 100,"score": 0,"inventory": ["sword", "shield", "potion"]
}# 更新玩家状态
player_state["health"] -= 10
player_state["score"] += 50
player_state["inventory"].append("magic wand")print(player_state)
# 输出: {'health': 90, 'score': 50, 'inventory': ['sword', 'shield', 'potion', 'magic wand']}

这种方式使得状态管理清晰且易于维护。

4.6. 数据映射

字典可以用来实现数据映射，例如将用户ID映射到用户信息。

以下代码展示了如何使用字典存储和访问用户信息：

users = {1: {"name": "Alice", "email": "alice@example.com"},2: {"name": "Bob", "email": "bob@example.com"},3: {"name": "Charlie", "email": "charlie@example.com"}
}# 访问用户信息
user_id = 2
user_info = users.get(user_id)
print(user_info)  # 输出: {'name': 'Bob', 'email': 'bob@example.com'}

通过字典的键值对结构，可以快速地根据用户ID获取用户信息，而无需遍历整个数据集。

4.7. 配置路由

在Web开发中，字典可以用来配置路由，将URL路径映射到对应的处理函数。

以下是一个简单的路由配置示例：

routes = {"/home": home_page,"/about": about_page,"/contact": contact_page
}def home_page():return "Welcome to the Home Page!"def about_page():return "About Us"def contact_page():return "Contact Information"# 处理请求
def handle_request(path):handler = routes.get(path)if handler:return handler()else:return "404 Not Found"print(handle_request("/home"))  # 输出: Welcome to the Home Page!

通过字典的映射关系，可以快速地根据路径找到对应的处理函数，从而实现高效的路由管理。

5. 总结

总之，Python 字典凭借高效的存储和检索特性，成为 Python 编程不可或缺的数据结构。

深入了解 Python 字典，能让我们更好地利用这一强大的数据结构，编写出更高效、简洁的 Python 代码。

无论是小型脚本，还是大型项目开发，字典都将发挥重要作用。

行业拓展

分享一个面向研发人群使用的前后端分离的低代码软件——JNPF，适配国产化，支持主流数据库和操作系统。

提供五十几种高频预制组件，包括表格、图表、列表、容器、表单等，内置常用的后台管理系统使用场景和基本需求，配置了流程引擎、表单引擎、报表引擎、图表引擎、接口引擎、门户引擎、组织用户引擎等可视化功能引擎，超过数百种功能控件以及大量实用模板，使得在拖拉拽的简单操作下，也能完成开发。

对于工程师来说，灵活的使用高质量预制组件可以极大的节省时间，将更多精力花费在更有创造性和建设性的代码上。