Python字典和集合

字典和集合的定义

字典：字典是由一系列键（key）和值（value）配对组成的元素的集合
集合：和字典基本相同，唯一的区别在于集合没有键和值得配对，它是由一系列无序的、唯一的元素组合。

字典和集合的创建

>>> 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

字典和集合的访问

>>> d = {'name': 'jason', 'age': 20}
>>> d['name']
'jason'
>>> d['location']
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'location'

>>> d = {'name': 'jason', 'age': 20}
>>> d.get('name')
'jason'
>>> d.get('location', 'null')
'null'

# 集合并不支持索引，因为集合本质上是一个哈希表，和列表不一样
>>> s = {1,2,3}
>>> s[0]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'set' object does not support indexing

>>> s = {1,2,3}
>>> 1 in s
True
>>> 10 in s
False
>>> d = {'name': 'jason', 'age': 20}
>>> 'name' in d
True
>>> 'location' in d
False

字典和集合的增加、删除以及更新操作

>>> d = {'name': 'jason', 'age': 20}
>>> d['gender'] = 'male'  # 增加元素对'gender'
>>> d['dob'] = '1999-02-01' # 增加元素对'dob'
>>> d
{'name': 'jason', 'age': 20, 'gender': 'male', 'dob': '1999-02-01'}
>>> d.pop('dob') # 删除键为'dob'的元素
'1999-02-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}

字典和集合的排序

>>> d = {'b':1, 'a':2, 'c':10}
>>> 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)]

>>> s = {3,4,2,1}
>>> sorted(s)
[1, 2, 3, 4]

字典和集合的性能比较

# cat time_test.py 
import time

# 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)

    
# set version
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)

products = [
    (143121312, 100), 
    (432314553, 30),
    (32421912367, 150),
    (937153201, 30)
]

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))
# python time_test.py 
time elapse using list: 3.7122517824172974e-06
time elapse using set: 3.2670795917510986e-06

字典和集合的工作原理

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

• 字典里面，这张表里面存储了哈希值，键以及值这三个元素
• 对集合而言，里面没有键值得配置，只有单一的元素
• 对于插入操作，会首先计算键的哈希值，在得到一个mask = PyDicMinSize - 1，来确定这个元素应该插入哈希表的位置index = hash(key) & mask。如果哈希表中这个位置是空的，那这个元素就被插入。
  如果此位置已经被占用，python会比较两个元素的哈希值和键是否相等。
  如果二者都相等，说明元素已经存在，如果值不相等，则更新值。
  如果二者其中有一个不相等，我们称为哈希冲突（hash collsion），也就是两个元素的键不相等，但是哈希值相等。这种情况下，python会继续寻找表中空余位置，直到找到位置为止。
• 对于查找操作，和插入操作类似，python会根据哈希值，找到其对应位置；然后比较这个位置中元素的哈希值和键，和需要查找的元素是否相等。如果相等，返回；如果不等，继续查找，直到找到空位或者抛出异常为止。
  对于删除操作，python会暂时对这个位置的元素赋予一个特殊值，等到重新调整哈希表的时候，再做删除。
• 出现哈希冲突就会降低字典和集合的操作速度。所以为了保证高效性，它们内部的哈希表通常会至少保留1/3的剩余空间。当元素不停插入，剩余空间小鱼1/3时，python会获得更大的内存空间，扩充哈希表。在这种情况下，表内所有的元素都会被重新排放。