Python 进阶与核心技术 dict & set

用户头像
Bonaparte
关注
发布于: 2020 年 05 月 30 日



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 会更新获取更大的内存空间,扩充哈希表。

用户头像

Bonaparte

关注

还未添加个人签名 2017.11.23 加入

还未添加个人简介

评论

发布
暂无评论
Python 进阶与核心技术 dict & set