Python 进阶与核心技术 dict & set



dict 是一系列由 key 和 value 配对组成的 item 元素的 set 集合，在Python 3.7+ dict 有序 正式成为语言特性；在 Python 3.6之前是无序的，其长度大小可变，item 可任意地删减或改变。



相对 list 和 tuple ，dict 性能更优，特别是查找、添加、删除操作，dict 都能在常数时间复杂度下完成。



set 是一系列无序的，唯一的 item组合，没有key 和 value 的配对。



Python 中的 dict 和 set ，无论 key 还是value ，item，都可以是混合类型。



当 dict 直接访问 索引 key 当 key 不存在时，会报错，会抛出异常。



还可使用.get("key", "default")函数来进行索引，如果 key 不存在，调用 .get() 函数可返回后面的默认值。



set 本质是一个 hash 哈希表，和列表不一样，set 并不支持索引操作。



判断一个 item 在不在 set 或 dict 中，可以用 value in set/dict 来判断。



set 和 dict 也可以进行新建、删除、更新等操作，也可创建和访问。



dict 增加 item， dict["key"] = "value" 再次输入，可以更新 dict 的 item



dict 删除 item， dict.pop("key")



set 增加 item， set.add("item")； set 删除 item， set.remove("item")



set.pop("item") 删除 set 中的最后一个元素，set 本身是无序的，无法知道是删除的那个 item，这个操作需要谨慎。



我们通常会根据 key 或 value ，对 dict 进行升序或降序排序;

set 和 list 、tuple 类似，直接调用 sorted(set)，就会返回一个排好序的 list。



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



使用 list 方式实现给定某件商品的ID, 找出其价格。

1.遍历list 中的 N 个元素，查找要找到其价格的那一件商品的ID，时间复杂度为O(n)线性阶复杂度；

2.相对 list 排序，然后使用二分查找，也需要 O(logN) 对数阶复杂度的时间复杂度，list 排序 还需要 O(nlogN) 线性对数阶复杂度



如果 使用 dict 存储这些数据，查找也会很高效，只需要 O(1)常数阶复杂度 就可以了。



dict 和 set 能特别高效完成查找、插入和删除等操作，主要和 set 及 dict 内部数据结构密不可分，dict 和 set 的内部结构都是一张哈希表。



对 dict 而言，表里面 存储了 哈希值(hash)、key 和 value 三个 item 元素

而set 来说，只有单一的 item 元素。



随着哈希表扩张，就会变得越来越稀疏。



为了提高存储空间的利用率，现在的 hash 表出了 dict 本身的结构，会把索引 和 hash 值、key 、value 单独分开。



每次向 dict 或 set 插入一个 item 时，Python 会首先计算 key 的哈希值 (hash(value)) ，再和 mask = PyDicminisize - 1 (Python dict mini size)做与 and 操作，计算 item 应插入哈希表的位置 index = hash(value) & mask。当哈希表中此位置是空的，那么 item 就会被插入其中。



如此位置被占用，Python会去比较两个元素的哈希值 hash value 和键 key 是否相等。



若两者都相等，则表示 item 已存在，如 value 不同，则更新 value；

若两者中有一个不相等，这种情况，我们称之为哈希冲突 hash collision，即两个item 的 key不相等，但是 哈希值 hash value相等。在这种情况下，Python会继续在 list 中寻找空余的位置，直到找到位置为止。



针对上述情况，最简单的方式是线性寻找，从这个位置开始，挨个往后寻找空位。



查找操作和上述的插入操作类似，Python 会根据 hash value，找到其应处于的位置，然后比较哈希表这个位置的 item 的 hash value 和 key，与需要查找的 item 是否相等。



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



为保证 dict 和 set 的操作速度高效，dict 和 set 内的 哈希表，通常会保证其至少留有 1/3 的剩余空间。随着 item 不停插入，当剩余空间小于 1/3 时，Python 会更新获取更大的内存空间，扩充哈希表。