【Python】深入了解字典和集合的本质

深藏阁楼爱情的钟 2023-01-23 09:52 158阅读 0赞

### 深入了解字典和集合的本质 ###

*  概述
 *  事例对比
 *  字典和集合的工作原理
 *   *  哈希表插入数据
     *  哈希表查找数据
     *  哈希表删除元素

# 概述 #

字典和集合是进行过性能高度优化的数据结构，特别是对于查找、添加和删除操作。

# 事例对比 #

例如，有一个存储产品信息（`产品 ID`、`名称`、`价格`）的列表，现在的需求是，借助某件产品的`ID`找出其`价格`。则实现代码如下：

def find_product_price(products, product_id):
        for id, price in products:
            if id == product_id:
                return price
        return None
    products = [
        (111, 100),
        (222, 30),
        (333, 150)
    ]
    print('The price of product 222 is {}'.format(find_product_price(products, 222)))
    
    输出：The price of product 222 is 30

在上面程序的基础上，如果列表`有 n 个元素`，因为查找的过程需要遍历列表，那么最坏情况下的时间复杂度就为 `O(n)`。

即使先对列表进行排序，再使用二分查找算法，也需要 `O(logn)` 的时间复杂度，更何况列表的排序还需要 `O(nlogn)` 的时间。

但如果用字典来存储这些数据，那么查找就会非常便捷高效，只需 `O(1)` 的时间复杂度就可以完成，因为可以直接通过键的哈希值，找到其对应的值，而不需要对字典做遍历操作，实现代码如下：

products = {
        
      111: 100,
      222: 30,
      333: 150
    }
    print('The price of product 222 is {}'.format(products[222]))
    
    输出：The price of product 222 is 30

可能对时间复杂度并没有直观的认识，再给列举一个实例。下面的代码中，初始化了含有 `100,000` 个元素的产品，并分别计算出了使用`列表`和`集合`来统计产品价格数量的运行时间：

#统计时间需要用到 time 模块中的函数，了解即可
    import time
    def find_unique_price_using_list(products):
        unique_price_list = []
        for _, price in products: # A
            if price not in unique_price_list: #B
                unique_price_list.append(price)
        return len(unique_price_list)
    id = [x for x in range(0, 100000)]
    price = [x for x in range(200000, 300000)]
    products = list(zip(id, price))
    # 计算列表版本的时间
    start_using_list = time.perf_counter()
    find_unique_price_using_list(products)
    end_using_list = time.perf_counter()
    print("time elapse using list: {}".format(end_using_list - start_using_list))
    
    【输出：time elapse using list: 68.78650900000001】
    
    #使用集合完成同样的工作
    def find_unique_price_using_set(products):
        unique_price_set = set()
        for _, price in products:
            unique_price_set.add(price)
        return len(unique_price_set)
    # 计算集合版本的时间
    start_using_set = time.perf_counter()
    find_unique_price_using_set(products)
    end_using_set = time.perf_counter()
    print("time elapse using set: {}".format(end_using_set - start_using_set))
    
    【输出：time elapse using set: 0.010747099999989018】

可以看到，仅仅十万的数据量，两者的速度差异就如此之大。

而往往企业的后台数据都有上亿乃至十亿数量级，因此如果使用了不合适的数据结构，很容易造成服务器的崩溃，不但影响用户体验，并且会给公司带来巨大的财产损失。

那么，字典和集合为什么能如此高效，特别是查找、插入和删除操作呢？

# 字典和集合的工作原理 #

字典和集合能如此高效，和它们内部的数据结构密不可分。不同于其他数据结构，字典和集合的内部结构都是一张哈希表：

*  对于字典而言，这张表存储了`哈希值（hash）`、`键`、`值`这 3 个元素。
 *  对集合来说，哈希表内只存储单一的元素。

对于之前版本的 Python 来说，它的哈希表结构如下所示：

| 哈希值 (hash)  键 (key)  值 (value)
    . |           ...
    0 |    hash0      key0    value0
    . |           ...
    1 |    hash1      key1    value1
    . |           ...
    2 |    hash2      key2    value2
    . |           ...

这种结构的弊端是，随着哈希表的扩张，它会变得越来越稀疏。比如，有这样一个字典：

{
        'name': 'mike', 'dob': '1999-01-01', 'gender': 'male'}

那么它会存储为类似下面的形式：

entries = [
    ['--', '--', '--']
    [-230273521, 'dob', '1999-01-01'],
    ['--', '--', '--'],
    ['--', '--', '--'],
    [1231236123, 'name', 'mike'],
    ['--', '--', '--'],
    [9371539127, 'gender', 'male']
    ]

显然，这样非常浪费存储空间。为了提高存储空间的利用率，现在的哈希表除了字典本身的结构，会把索引和哈希值、键、值单独分开，也就是采用如下这种结构：

Indices
    ----------------------------------------------------
    None | index | None | None | index | None | index ...
    ----------------------------------------------------
    
    Entries
    --------------------
    hash0   key0  value0
    ---------------------
    hash1   key1  value1
    ---------------------
    hash2   key2  value2
    ---------------------
            ...
    ---------------------

在此基础上，上面的字典在新哈希表结构下的存储形式为：

indices = [None, 1, None, None, 0, None, 2]
    entries = [
    [1231236123, 'name', 'mike'],
    [-230273521, 'dob', '1999-01-01'],
    [9371539127, 'gender', 'male']
    ]

通过对比可以发现，空间利用率得到很大的提高。

清楚了具体的设计结构，接下来再分析一下如何使用哈希表完成对数据的插入、查找和删除操作。

## 哈希表插入数据 ##

当向字典中插入数据时，Python 会首先根`据键（key）`计算出对应的哈希值（通过 hash(key) 函数）

而向集合中插入数据时，Python会根据该`元素本身`计算对应的哈希值（通过 hash(valuse) 函数）。

dic = {
        "name":1}
    print(hash("name"))
    输出：8230115042008314683
    
    setDemo = {
        1}
    print(hash(1))
    输出：1

得到哈希值（例如为 hash）之后，再结合字典或集合要存储数据的个数（例如 n），就可以得到该元素应该插入到哈希表中的位置（比如，可以用 hash%n 的方式）。

如果哈希表中此位置是空的，那么此元素就可以直接插入其中；

反之，如果此位置已被其他元素占用，那么 Python 会比较这两个元素的哈希值和键是否相等：

*  如果相等，则表明该元素已经存在，再比较他们的值，不相等就进行更新；
 *  如果不相等，这种情况称为哈希冲突（即两个元素的键不同，但求得的哈希值相同）。这种情况下，Python 会使用`开放定址法`、`再哈希法`等继续寻找哈希表中空余的位置，直到找到位置。

> 具体遇到哈希冲突时，各解决方法的具体含义可阅读《哈希表详解》。

## 哈希表查找数据 ##