笔记大全

Python数据容器dict如何实现

更新时间：2023-11-11

1. Python中dict的定义及基本操作

dict是Python中内置且极为常用的一种数据容器类型，它可以存储任意数量、任意类型的Python对象，其中每个对象都有一个唯一的键。dict采用哈希表的数据结构实现，因此它的查找、插入、删除等操作都非常快速。

定义一个dict对象:

{'name': 'Tom', 'age': 23, 'gender': 'male'}

访问dict中的值:

person_info = {'name': 'Tom', 'age': 23, 'gender': 'male'}
print(person_info['name'])   # 输出：Tom

修改dict的值：

person_info = {'name': 'Tom', 'age': 23, 'gender': 'male'}
person_info['age'] = 25
print(person_info)   # 输出：{'name': 'Tom', 'age': 25, 'gender': 'male'}

添加元素到dict：

person_info = {'name': 'Tom', 'age': 23, 'gender': 'male'}
person_info['address'] = 'USA'
print(person_info)   # 输出：{'name': 'Tom', 'age': 23, 'gender': 'male', 'address': 'USA'}

2. dict的哈希表实现

dict采用哈希表实现，它的查找、插入和删除操作都可以在O(1)的时间复杂度内完成，因此dict是非常高效的数据容器。在dict中，所有的键都必须是可哈希的对象，从而可以通过哈希函数计算键在哈希表中对应的位置。

以下是一个简单的哈希函数实现：

def hash_function(key):
    """
    a simple hash function, sum the ascii values of the key
    """
    if isinstance(key, int):
        return key
    return sum([ord(ch) for ch in key])

由于哈希函数并不是完美的，可能会出现哈希冲突，即两个键计算出的哈希值相同。在dict中，我们采用开放地址法解决哈希冲突，当发生冲突时，尝试向哈希表中的下一个空位置插入数据，这个过程需要重复进行直到没有冲突。

3. dict的性能特征及注意事项

dict具有以下性能特征：

插入、删除、查找元素的时间复杂度均为O(1)，即不会随着元素数量的增加而变慢。
dict的内存占用比较大，因为字典在某些情况下需要浪费空间来保证查询效率。
在使用dict时，需要注意键是可哈希的对象。比如，列表、字典等可变对象并不是可哈希的，因此不能作为键使用。

另外，如果需要对dict进行遍历操作，建议使用.items()，.keys(), .values()方法来获取键值对、键或值的迭代器。

person_info = {'name': 'Tom', 'age': 23, 'gender': 'male'}
for key, value in person_info.items():
    print(key, value)

4. 自定义实现Python的dict

由于dict是Python内置的数据类型之一，可以非常方便地应用于我们的编程工作中。然而，了解它的实现机制有助于我们深入理解Python的内部运行机制。

以下是一个简单的dict实现：

class MyDict:
    def __init__(self):
        self.items = []
    
    def __getitem__(self, key):
        for k, v in self.items:
            if k == key:
                return v
        raise KeyError(key)
    
    def __setitem__(self, key, value):
        for i, kv in enumerate(self.items):
            if kv[0] == key:
                self.items[i] = (key, value)
                break
        else:
            self.items.append((key, value))
    
    def __delitem__(self, key):
        for i, kv in enumerate(self.items):
            if kv[0] == key:
                del self.items[i]
                return
        raise KeyError(key)

这里我们自定义了一个MyDict类，实现了类似于Python内置dict的基本操作。其中，__getitem__、__setitem__、__delitem__分别为访问元素、插入元素和删除元素的操作，它们是Python中的魔术方法。在使用MyDict时，可以像使用Python内置dict一样进行操作。

总结

Python的dict是一种非常常用的数据容器，它采用哈希表的数据结构实现，因此具有查找、插入、删除元素快速、时间复杂度为O(1)的优点。当然，dict的内存占用比较大，并且对键的可哈希要求比较高。同时，也可以自定义实现Python的dict，以了解它的内部运行机制。

c语言编程笔录