目录链接：https://www.jianshu.com/p/e1e201bea601
字典和集合基础
字典是一系列由键（key） 和值（value） 配对组成的元素的集合。
字典是以 关键字 为索引的，关键字可以是任意不可变类型，通常是字符串或数字。如果一个元组只包含字符串、数字或元组，那么这个元组也可以用作关键字。但如果元组直接或间接地包含了可变对象，那么它就不能用作关键字。
相比于列表和元组， 字典的性能更优， 特别是对于查找、 添加和删除操作， 字典都能在常数时间复杂度内完成。
集合（set）是一个无序的不重复元素序列。
字典和集合的创建
通常有下面这几种方式：
d1 = {'Name': 'Runoob', 'Age': 7, 'Class': 'First'}
d2 = dict({'Name': 'Runoob', 'Age': 7, 'Class': 'First'})
d3 = dict([('Name', 'Runoob'), ('Age', 7), ('Class', 'First')])
d4 = dict(Name='Runoob', Age=7, Class='First')
print(d1 == d2 == d3 ==d4)
s1 = {1, 2, 3}
s2 = set([1, 2, 3])
print(s1 == s2)
result.png
元素访问
字典:
直接索引键，如果不存在， 就会抛出异常：
dict01.png
使用get(key, default) 函数来索引。 如果键不存在， 调用get() 函数可以返回默认值。
dict02.png
集合并不支持索引操作， 因为集合本质上是一个哈希表。
set01.png
value in dict/set 来判断元素在不在字典或集合内
valuein.png
增加、 删除、 更新等操作
字典
dict.png
集合
set.png
排序
字典
dict.png
集合
set.png
字典和集合的工作原理
不同于其他数据结构， 字典和集合的内部结构都是张哈希表。
- 对字典来说， 这张表存储了哈希值（hash） 、 键和值这 3 个元素。
- 对集合来说， 区别就是哈希表内没有键和值的配对， 只有单一的元素了。
可参看：https://www.cnblogs.com/pengsixiong/p/5326893.html
老版本 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']
]
插入操作
每次向字典或集合插入一个元素时
1、先计算键的哈希值（hash(key)）
2、再和 mask =PyDicMinSize - 1 做与操作， 计算这个元素应该插⼊哈希表的位置 index = hash(key) & mask。
位置是空的：
3、这个元素就会被插⼊其中。
位置已被占用：
3、Python 比较两个元素的哈希值和键是否相等
若两者都相等， 则表明这个元素已经存在， 如果值不同， 则更新值。
若两者中有一个不相等， 这种情况我们通常称为哈希冲突（hash collision），意思是两个元素的键不相等， 但是哈希值相等。 这种情况下， Python 便会继续寻找表中空余的位置，直到找到位置为⽌。
查找操作
Python 会根据哈希值， 找到其应该处于的位置；然后， 比较哈希表这个位置中元素的哈希值和键， 与需要查找的元素是否相等。 如果相等， 则直接返回；如果不等， 则继续查找， 直到找到空位或者抛出异常为⽌。
删除操作
对于删除操作， Python 会暂时对这个位置的元素， 赋于一个特殊的值， 等到重新调整哈希表的大小时， 再将其删除。
参考资料：
极客时间 Python核心技术与实战学习
Python核心技术与实战（极客时间）链接：
http://gk.link/a/103Sv
Python3 字典：
http://www.runoob.com/python3/python3-dictionary.html
Python3 集合：
http://www.runoob.com/python3/python3-set.html
python 下的数据结构与算法---8：哈希一下【dict与set的实现】：
https://www.cnblogs.com/pengsixiong/p/5326893.html
GitHub链接：
https://github.com/lichangke/LeetCode
个人Blog:
https://lichangke.github.io/
欢迎大家来一起交流学习
网友评论