python set dict实现原理
标签：其他 复杂度 end 包含 下标 head pre string 添加
Python数据结构总结
dict与set的实现原理
两者的原理都是哈希表。
dict与set实现原理是一样的，都是将实际的值放到list中。唯一不同的在于hash函数操作的对象，对于dict，hash函数操作的是其key，而对于set是直接操作的它的元素，假设操作内容为x，其作为因变量，放入hash函数，通过运算后取list的余数，转化为一个list的下标，此下标位置对于set而言用来放其本身，而对于dict则是创建了两个list，一个list该下表放此key，另一个list中该下标方对应的value。
其中，我们把实现set的方式叫做Hash Set，实现dict的方式叫做Hash Map/Table(注：map指的就是通过key来寻找value的过程)。
下面是常用数据结构和时间复杂度分析。
string
不可变。
| 方法 |
解释 |
| str.count(‘a’) |
返回str中字符a的个数 |
| str.lower() |
返回str的小写形式 |
| str.upper() |
返回str的大写形式 |
| str.strip() |
去除str首尾\n和空白字符，也可取任意字符 |
| str.replace(‘a’, ‘z’) |
替换全部a为z |
| str.find(‘a’) |
返回str中第一个a的位置下标 |
| str.ljust(10, ‘0’) |
输出str左对齐，右边补字符0，共10位 |
| str.rjust(10, ‘0’) |
输出str右对齐，左边补字符0，共10位 |
list
可变。
| 方法 |
解释 |
时间复杂度 |
| l.append(30) |
末尾添加30 |
O(1) |
| l.extend([30, 40, 50]) |
合并一个列表到l尾部 |
|
| l.pop() |
删除l最后一个元素 |
O(1) |
| l.pop(index) |
删除l下标为index的元素 |
O(n) |
| l.insert(index, x) |
在index位置插入元素x |
O(n) |
| l.sort() |
原地排序，升序 |
O(nlogn) |
| l.reverse() |
反转列表 |
O(n) |
| l.index() |
返回x在列表中的第一个位置 |
O(1) |
| l.count(x) |
列表中x存在的个数 |
O(n) |
| l.remove() |
删除列表中元素x，只删除第一个 |
O(n) |
| del l[2] |
删除下标为2的元素 |
O(n) |
| x in l |
x是否存在于列表 |
O(n) |
tuple
不可变。一旦创建不可更改，不能添加、删除元素，不能存储可变类型的数据。
| 方法 |
解释 |
| t = (1, 2, 3, 1, 5, 1, 6) |
定义 |
| t.count(1) |
元组中数字1的个数 |
| t[2] # 3 |
可用下标访问 |
set
可变。集合是无序的、没有重复值。
只能包含不可变的（可哈希化的）数据类型。列表和字典甚至另一个集合都不能作为集合的元素，但是元组可以（因为元组是不可变的）。
| 方法 |
解释 |
时间复杂度 |
s1 = {1, 2, 3}
s2 = {1, 3, 4, 5} |
定义 |
|
| s1 - s2 # {2} |
s1独有 |
|
| s1 | s2 # {1, 2, 3, 4, 5} |
并集 |
O(n) |
| s1 & s2 # {1, 3} |
交集 |
O(n) |
| s1.add(9) # {1, 2, 3, 9} |
添加元素 |
O(1) |
| s1.pop() |
随机删除一个 |
O(1) |
| s1.remove(2) |
s1删除元素2 |
O(1) |
| s1.clear() |
清空 |
O(1) |
| s1.union(s2) |
并集，相当于 | |
O(n) |
| s1.intersection(s2) |
交集，相当于 & |
O(n) |
| s1.issubset(s2) |
s1是否为s2子集 |
|
| x in s1 |
x 是否存在于s1 |
O(1) , set原理为哈希表 |
由于集合本身是可变的，因此，要想在一个集合中嵌入另一个集合，需要用frozenset创建一个不可变的集合。
a = frozenset([1, 2, 3])
b = set([1, 2, a]) # b为{frozenset({1, 2, 3}), 1, 2}
为什么使用集合？
- 集合内元素是不重复的，因此可以将list或其他类型的数据转换成集合，从而过滤掉其中的重复元素。
dict
key：value，key不可变，value可变。
| 方法 |
解释 |
|
| d.keys() |
dict_keys列表 |
|
| d.values() |
dict_values列表 |
|
| d.items() |
[(key, value), (key, value), ..]，列表元组 |
|
| d.get(key) |
无值返回None |
O(1) |
| d.get(key, default_value) |
无值返回设定的默认值default_value |
O(1) |
| del d[key] |
删除key-value |
O(1) |
| d[key] = value |
增加 |
O(1) |
| x in d |
判断x是否在d.keys()中 |
O(1)，dict原理为哈希表 |
python set dict实现原理
标签：其他 复杂度 end 包含 下标 head pre string 添加
原文地址：https://www.cnblogs.com/ldy-miss/p/12849647.html
评论