python3学习笔记之字典和集合

红太狼 2023-01-03 01:24 178阅读 0赞

**目录**

字典,集合基础

字典,集合性能

字典,集合的工作原理

总结

# 字典,集合基础 #

字典是一系列由键（key）和值（value）配对组成的元素的集合。相比于列表和元组，字典的性能更优，特别是对于查找、添加和删除操作，字典都能在常数时间复杂度内完成。（在 Python3.7+，字典被确定为有序）

集合和字典基本相同，唯一的区别，就是集合没有键和值的配对，是一系列无序的、唯一的元素组合

1.  **字典集合的创建**
    
        d1 = {'name': 'jason', 'age': 20, 'gender': 'male'}
        d2 = dict({'name': 'jason', 'age': 20, 'gender': 'male'})
        d3 = dict([('name', 'jason'), ('age', 20), ('gender', 'male')])
        d4 = dict(name='jason', age=20, gender='male') 
        d1 == d2 == d3 ==d4
        True
        
        s1 = {1, 2, 3}
        s2 = set([1, 2, 3])
        s1 == s2
        True
        
        #Python 中字典和集合，无论是键还是值，都可以是混合类型
        s = {1, 'hello', 5.0}
2.  **字典集合的元素访问**
    
    1.  **字典**
        
        1.  直接索引键，如果不存在，就会抛出异常
            
                d = {'name': 'jason', 'age': 20}
                d['name']
                'jason'
                d['location']
                Traceback (most recent call last):
                  File "<stdin>", line 1, in <module>
                KeyError: 'location'
        2.  get(key, default) 函数来进行索引。如果键不存在，调用 get() 函数可以返回一个默认值
            
                d = {'name': 'jason', 'age': 20}
                d.get('name')
                'jason'
                d.get('birthday','unKnown')
                'unknown'
        3.  想要判断一个元素在不在字典内，我们可以用 value in dic 来判断
            
                d = {'name': 'jason', 'age': 20}
                'name' in d
                True
                'location' in d
                False
    2.  **集合**：
        
        1.  集合并不支持索引操作，因为集合本质上是一个哈希表，和列表不一样。
            
                s = {1, 2, 3}
                s[0]
                Traceback (most recent call last):
                  File "<stdin>", line 1, in <module>
                TypeError: 'set' object does not support indexing
        2.  想要判断一个元素在不在集合内，我们可以用 value in set 来判断
            
                s = {1, 2, 3}
                1 in s
                True
                10 in s
                False
3.  **字典集合的增加、删除、更新等操作**
    
        #字典的增，删，改
        d = {'name': 'jason', 'age': 20}
        d['gender'] = 'male' # 增加元素对'gender': 'male'
        d['dob'] = '1999-02-01' # 增加元素对'dob': '1999-02-01'
        d
        {'name': 'jason', 'age': 20, 'gender': 'male', 'dob': '1999-02-01'}
        d['dob'] = '1998-01-01' # 更新键'dob'对应的值 
        d.pop('dob') # 删除键为'dob'的元素对
        '1998-01-01'
        d
        {'name': 'jason', 'age': 20, 'gender': 'male'}
        
        #集合的增，删，改
        s = {1, 2, 3}
        s.add(4) # 增加元素4到集合
        s
        {1, 2, 3, 4}
        s.remove(4) # 从集合中删除元素4
        s
        {1, 2, 3}
    
    **PS:**集合的\*\*pop（）操作是删除集合中最后一个元素，但集合本身无序，无法确认删除哪个元素，该操作谨用
4.  **字典集合的排序**
    
    1.  字典通常会根据键或值，进行升序或降序排序
        
            d = {'b': 1, 'a': 2, 'c': 10}
            d_sorted_by_key = sorted(d.items(), key=lambda x: x[0]) # 根据字典键的升序排序
            d_sorted_by_value = sorted(d.items(), key=lambda x: x[1]) # 根据字典值的升序排序
            d_sorted_by_key
            [('a', 2), ('b', 1), ('c', 10)]
            d_sorted_by_value
            [('b', 1), ('a', 2), ('c', 10)]
    2.  集合，其排序和前面讲过的列表、元组很类似，直接调用 sorted(set) 即可，结果会返回一个排好序的列表
        
            s = {3, 4, 2, 1}
            sorted(s) # 对集合的元素进行升序排序
            [1, 2, 3, 4]

# 字典,集合性能 #

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

**应用场景1**：电商企业的后台，存储了每件产品的 ID、名称和价格。现在的需求是，给定某件商品的 ID，我们要找出其价格。假设有n个产品

1.  列表存储数据：先对列表进行排序，在用二分查找：列表排序需要O(nlogn)时间，二分查找需要O(logn) 的时间复杂度
2.  字典存储数据：因为字典的内部组成是一张哈希表，你可以直接通过键的哈希值，找到其对应的值。查找会非常便捷高效，只需 O(1) 的时间复杂度

**应用场景2:**在场景1的情况下，找出这些商品有多少不通的价格

1.  列表存储数据：在n个商品的情况下，最差需要O(n^2) 的时间复杂度
2.  集合存储数据：集合是高度优化的哈希表，里面元素不能重复，并且其添加和查找操作只需 O(1) 的复杂度，那么，总的时间复杂度就只有 O(n)

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

字典和集合的内部结构都是一张哈希表

老版本 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']
    ]

# 总结 #

字典在 Python3.7+ 是有序的数据结构，而集合是无序的，其内部的哈希表存储结构，保证了其查找、插入、删除操作的高效性。所以，字典和集合通常运用在对元素的高效查找、去重等场景