Python—哈希表的应用（字典与集合）

什么是哈希表

散列表（Hash table，也叫哈希表），是根据关键码值(Key和value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

Python 将哈希表用于字典和集合。 哈希表是键值对的无序集合，其中每个键都是唯一的。 哈希表提供了有效的查找，插入和删除操作的组合。 这些是数组和链接列表的最佳属性。

字典（dict）与 集合（set）

字典（dict）和集合（set）在 Python 被广泛使用，并且性能进行了高度优化，其重要性不言而喻。

字典是一系列由键（key）和值（value）配对组成的元素的集合。python3.7之后，字典底层是2个数组，一个为一维数组，存放hash(key)取余后的值作为数组的索引，对应索引位置存放键值对在二维数组的索引位置。因此二维数组是一个有序的数组。

相比于列表和元组，字典的性能更优，特别是对于查找、添加和删除操作，字典都能在常数时间复杂度内完成。

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

字典和集合的创建方式通常有以下几种：

###字典的创建
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}

字典和集合的访问

字典访问可以直接索引键，如果不存在，就会抛出异常

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

使用 get(key, default) 函数来进行索引。

如果键不存在，调用 get() 函数可以返回一个默认值。

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

集合不支持索引操作
因为集合本质上是一个哈希表，和列表不一样。
所以，下面这样的操作是错误的，Python 会抛出异常。

s = {1, 2, 3}
s[0]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'set' object does not support indexing

要判断一个元素在不在字典或集合内，我们可以用value in dict/set来判断（对于字典，只能使用key in dict 来判断）。

##集合元素存在判断
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': '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}

字典—判断键、值和键值对是否在字典中

1.判断键是否在字典中

<键> in <字典名>   #（最快）
<键> in <字典名>.keys()

2.判断值是否在字典中

<值> in <字典名>.values()

3.判断键值对是否在字典中

(<键>，<值>) in <字典名>.items()

Python判断列表中是否存在某元素

成员判断

运算符	描述
in	如果在指定的序列中找到值返回 True，否则返回 False
not in	如果在指定的序列中没有找到值返回 True，否则返回 False

同级身份判断

运算符	描述
is	判断两个标识符是不是引用自一个对象
is not	判断两个标识符是不是引用自不同对象

时间复杂度

in list : o(n)
in set  : o(1)
in dict : o(1)

参考：
https://blog.csdn.net/qq_41485273/article/details/114031568
https://www.jianshu.com/p/191de68488b4
https://blog.csdn.net/wycgi/article/details/85063342