博客

Python字典底层实现原理详解

  • Post category:Python

Python字典底层实现原理详解

本文将深入探讨Python字典的底层实现原理，包括如何实现高效的哈希表及常见的哈希冲突解决方法。

Python字典基本概念

Python中的字典是一种重要的数据结构，它可以存储键值对（key-value）映射关系，提供了O(1)时间（平均）的查找、插入和删除操作。 字典是基于哈希表实现的，哈希表是一种将键（key）映射到对应值（value）的数据结构，它能够以O(1)时间复杂度进行键的查找、插入和删除操作。

哈希表的实现原理

哈希表的实现主要包括两个部分：哈希函数（hash function）和哈希冲突解决方法。

哈希函数

哈希函数是将键映射到一个固定的索引位置的函数。Python使用了MurmurHash算法及一些其他独有的技巧来尽可能节约空间和保证哈希值的不重复性。在Python中，哈希值是用整数表示的，它们可以被用于快速比较字典中的键。由于哈希函数是一个非常重要的因素，其实现的好坏直接影响了哈希表的性能。

哈希冲突解决方法

哈希表的关键问题是如何处理哈希冲突。哈希冲突是指两个不同的键在哈希函数中产生了相同的哈希值。在Python中，有多种处理哈希冲突的方法，最常见的是开放地址法（open addressing）以及链地址法（separate chaining）。

开放地址法

开放地址法是指在哈希表中查找目标键时，如果该键所在的位置已被占用，则继续往后找下一个空位置，直至找到空位置或哈希表被查找一圈。这种方式可以节省内存，但是由于哈希表被占用的位置越多，查找效率会越低。

链地址法

链地址法是指将哈希表中使用哈希函数映射到同一个索引位置的键值对存储在同一个链表中。当发生哈希冲突时，只需要将新的键值对追加到对应链表的尾部即可。链地址法相对于开放地址法，可以更好地处理哈希冲突问题，但是会占用更多的内存空间。

Python字典的实现

Python字典实现主要由”散列表”和”哈希冲突解决”两部分组成。下面结合代码简单讲解一下Python字典的实现原理。

class dict(object):
    ...
    def __setitem__(self, key, value):
        self.store_hashed_item(hash(key), key, value)
    ...

首先看到的是__setitem__方法，它是Python字典实现中最核心的方法之一。它先通过hash(key)得到键的哈希值，然后调用store_hashed_item方法将键值对存储到散列表中。下面是store_hashed_item方法的简单实现：

class dict(object):
    ...
    def store_hashed_item(self, hash, key, value):
        index = hash & (self.mask)
        if self.table[index] is not NULL:
            # 处理哈希冲突
            ...
        else:
            self.table[index] = PyObject(key, value)
    ...

store_hashed_item方法中的index = hash & (self.mask)计算出了键的索引值。它使用了位运算优化了取模运算，相当于对哈希值取模操作的快速实现。

如果目标键值对所在的位置已被占用，那么就需要处理哈希冲突。Python中采用了开放地址法解决哈希冲突，代码如下：

class dict(object):
    ...
    def store_hashed_item(self, hash, key, value):
        index = hash & (self.mask)
        if self.table[index] is not NULL:
            # 处理哈希冲突
            i = 1 
            while True:
                perturb = hash % (self.mask + 1)
                index = (index*5 + perturb + 1) & self.mask
                if self.table[index] is NULL:
                    self.table[index] = PyObject(key, value)
                    break
                elif self.table[index].key == key:
                    # 更新已存在的键
                    ...
                else:
                    i += 1

在处理哈希冲突时，如果散列表中该位置已被占用，则使用perturb计算出一个新的索引值，以此来查找更改的插入位置。perturb是一个随机数，用于增加查找距离，避免陷入一个死循环。插入新的键值对时，在新的位置上存储该键值对，而在旧的位置上存储被占用标志（NULL对象），直到重新调整了所有键值对的位置后才真正释放旧的位置。

示例说明

示例1：使用Python中的字典

# 创建字典
dict1 = {"name": "Tom", "age": 18, "sex": "male"}
# 添加键值对
dict1["address"] = "Beijing"
print(dict1)
# 输出结果: {"name": "Tom", "age": 18, "sex": "male", "address": "Beijing"}
# 查找键 "age" 对应的值
print(dict1["age"])
# 输出结果：18
# 删除键 "sex" 及其对应值
del dict1["sex"]
print(dict1)
# 输出结果：{"name": "Tom", "age": 18, "address": "Beijing"}

通过字典的使用示例，可以看到Python字典的直接操作方式，以及快速的查找、插入和删除操作。

示例2：查看Python字典占用的内存空间

import sys

# 创建字典
dict1 = {"name": "Tom", "age": 18, "sex": "male"}
print(sys.getsizeof(dict1))
# 输出结果：240

通过示例，可以使用Python内置模块sys获取字典变量占用的内存空间大小，进一步了解字典的内存占用特点。

总结

本文对Python字典的底层实现原理进行了详细地介绍，包括哈希表的实现原理、哈希冲突解决方法和Python字典的实现方法。了解Python字典的底层实现原理，对于提高Python代码的效率，优化数据结构设计具有重要的指导意义。

Tags: ,