字典和集合与列表性能比较

左手的ㄟ右手 2022-09-05 05:25 145阅读 0赞

字典和集合是进行过性能高度优化的数据结构，特别是对于查找、添加和删除操作。那接下来，我们就来看看，它们在具体场景下的性能表现，以及与列表等其他数据结构的对比。

# 字典和集合与列表的性能对比 #

**比如电商企业的后台，存储了每件产品的 ID、名称和价格。现在的需求是，给定某件商品的 ID，我们要找出其价格。**

如果我们用列表来存储这些数据结构，并进行查找，相应的代码如下：

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

假设列表有 n 个元素，而查找的过程要遍历列表，那么时间复杂度就为 O(n)。即使我们先对列表进行排序，然后使用二分查找，也会需要 O(logn) 的时间复杂度，更何况，列表的排序还需要 O(nlogn) 的时间。

用字典来存储这些数据，那么查找就会非常便捷高效，只需 O(1) 的时间复杂度就可以完成。原因也很简单，刚刚提到过的，字典的内部组成是一张哈希表，你可以直接通过键的哈希值，找到其对应的值

products = { 
        143121312: 100,
        432314553: 30,
        32421912367: 150
    }
    print('The price of product 432314553 is {}'.format(products[432314553]))
    # 输出 The price of product 432314553 is 30

**现在需求变成，要找出这些商品有多少种不同的价格。我们还用同样的方法来比较一下:**

选择使用列表，对应的代码如下，其中，A 和 B 是两层循环。同样假设原始列表有 n 个元素，那么，在最差情况下，需要 O(n^2) 的时间复杂度。

# list version
    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)
    
    
    products = [
        (143121312, 100),
        (432314553, 30),
        (32421912367, 150),
        (937153201, 30)
    ]
    print('number of unique price is: {}'.format(find_unique_price_using_list(products)))
    # 输出 number of unique price is: 3

选择使用集合这个数据结构，由于集合是高度优化的哈希表，里面元素不能重复，并且其添加和查找操作只需 O(1) 的复杂度，那么，总的时间复杂度就只有 O(n)。

def find_unique_price_using_set(products):
        unique_price_set = set()
        for _, price in products:  # A
            unique_price_set.add(price)
        return len(unique_price_set)
    
    
    products = [
        (143121312, 100),
        (432314553, 30),
        (32421912367, 150),
        (937153201, 30)
    ]
    print('number of unique price is: {}'.format(find_unique_price_using_set(products)))
    # 输出 number of unique price is: 3

举一个实际工作场景中的例子，来感受一下二者的区别：  
下面的代码，初始化了含有 100,000 个元素的产品，并分别计算了使用列表和集合来统计产品价格数量的运行时间：

import time
    
    
    def find_unique_price_using_set(products):
        unique_price_set = set()
        for _, price in products:  # A
            unique_price_set.add(price)
        return len(unique_price_set)
    
    
    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))
    
    # 计算集合版本的时间
    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))

运行结果：  
![在这里插入图片描述][2449f9ee94b44bc3ad830b00aa55ef40.png]  
可以看到，仅仅十万的数据量，两者的速度差异就如此之大。事实上，大型企业的后台数据往往有上亿乃至十亿数量级，如果使用了不合适的数据结构，就很容易造成服务器的崩溃，不但影响用户体验，并且会给公司带来巨大的财产损失。

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

经过上面的例子，我们可以看出字典和集合与列表相比具有高效性，这与字典和集合的内部数据结构哈希表相关，那么接下来具体看一下字典和集合的工作原理：

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

老版本 Python 的哈希表结构如下所示  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70]  
随着哈希表的扩张，它会变得越来越稀疏。  
比如：对于这样一个dict `{'name': 'mike', 'dob': '1999-01-01', 'gender': 'male'}`  
它会存储为类似下面的形式  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70 1]  
老版本的哈希表的寻址过程是这样的：通过key计算哈希值，然后再通过哈希值计算数组的索引，然后通过索引以O(1)时间的复杂度访问到entries里面存储的哈希值、key和value；但是老版本的哈希表存储结构有个问题，就是为了保证通过计算所得的索引都能够正确的访问到地址，需要给entries分配连续的存储空间，这样一来，中间空闲的空间就太多了，造成了空间浪费。

因此为了提高存储空间的利用率，现在的哈希表除了字典本身的结构，会把索引和哈希值、键、值单独分开，也就是下面这样新的结构：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70 2]  
刚才那个例子，此时会存储成如下的形式：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70 3]  
新的哈希表存储结构，其寻址方式是这样的：通过key计算哈希值，然后再通过哈希值计算索引，但是这个索引不是entries的索引了，而是新建的indices数组的索引（此时由原来要求entries空间连续变为indices空间连续，造成的空间浪费由原来的空白存储空间的哈希值、key和value三个值的存储空间变为了空白存储仅一个索引值的空间），需要先通过计算出的这个索引在indices中寻址来取到entries中对应内容的索引（entries是连续空间，并且连续存储字典的哈希值、key和value，entries没有空间浪费），然后通过新获取到的索引值再去entries中寻址获取最终需要的内容。

新的哈希存储结构多加了一个indices转换数组来存储entries数组的索引，这使得entries数组中的条目可以紧密排列，**其思想就是将整条数据内容空闲的空间转换为单个索引空闲的空间**，确实很划算，而且每次查询也只是多了一次在indices中的O(1)复杂度的寻址，查询性能影响不大。

对于插入操作：  
每次向字典或集合插入一个元素时，Python 会首先计算键的哈希值（hash(key)），再和mask = PyDicMinSize - 1 做与操作，计算这个元素应该插入哈希表的位置 index =hash(key) & mask。如果哈希表中此位置是空的，那么这个元素就会被插入其中。  
而如果此位置已被占用，Python 便会比较两个元素的哈希值和键是否相等。

*  若两者都相等，则表明这个元素已经存在，如果值不同，则更新值。
 *  若两者中有一个不相等，这种情况我们通常称为哈希冲突（hash collision），意思是两个元素的键不相等，但是哈希值相等。这种情况下，Python 便会继续寻找表中空余的位置，直到找到位置为止。  
    值得一提的是，通常来说，遇到这种情况，最简单的方式是线性寻找，即从这个位置开始，挨个往后寻找空位。当然，Python 内部对此进行了优化，让这个步骤更加高效。

对于查找操作：  
和前面的插入操作类似，Python 会根据哈希值，找到其应该处于的位置；然后，比较哈希表这个位置中元素的哈希值和键，与需要查找的元素是否相等。如果相等，则直接返回；如果不等，则继续查找，直到找到空位或者抛出异常为止。

对于删除操作：  
Python 会暂时对这个位置的元素，赋于一个特殊的值，等到重新调整哈希表的大小时，再将其删除。

不难理解，哈希冲突的发生，往往会降低字典和集合操作的速度。因此，为了保证其高效性，字典和集合内的哈希表，通常会保证其至少留有 1/3 的剩余空间。随着元素的不停插入，当剩余空间小于 1/3 时，Python 会重新获取更大的内存空间，扩充哈希表。不过，这种情况下，表内所有的元素位置都会被重新排放。

虽然哈希冲突和哈希表大小的调整，都会导致速度减缓，但是这种情况发生的次数极少。所以，平均情况下，这仍能保证插入、查找和删除的时间复杂度为 O(1)。

总结：

*  字典和集合操作的高效性主要归功于其内部结构都是一张哈希表，对于字典而言，这张表存储了哈希值（hash）、键和值这 3 个元素。而对集合来说，区别就是哈希表内没有键和值的配对，只有单一的元素了。
 *  字典和集合通常运用在对元素的高效查找、去重等场景。
 *  在使用这些数据结构时一定要考虑性能的优劣，要从日常的练习中就养成这样的习惯。

[2449f9ee94b44bc3ad830b00aa55ef40.png]: /images/20220829/618741ba5d144450b0e8268f15d752b0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70]: /images/20220829/ce7a6bc84e2543719103603f43327434.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70 1]: /images/20220829/a689382806b44380b5650f1bee0844cc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70 2]: /images/20220829/4346d92a08564497b1a98d4adf76b0cb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MDQ4NzU2_size_16_color_FFFFFF_t_70 3]: /images/20220829/dd901c73f59c4ffc990f62cbcfe86074.png