集合型结构
十九世纪末集合论的出现让百家争鸣的近代数学得以形式化的统一, 集合论的强大之处就在于大部分现实问题都可以抽象为集合之间的运算.
在离散数学中,
确定性: 互异性: 无序性:
可散列结构: 不可变类型
特点: 空间换时间
现代计算机编程语言中的集合型结构都是基于哈希算法实现的 理想情况下, 哈希算法应该保证所有不同的输入都能映射出唯一确定的 更多关于哈希表
可以参考哈希表中的数学原理
集合
Python中的集合包括可变集合（set）和不可变集合（frozenset）,
集合的运算
设$A$和$B$为集合, 则由属于
\[A \cup B = \{x|x \in A 或 x \in B \}\]并运算,
集合中提供了union(*sets)方法用于计算多个集合的并集. 此外, 集合重载了__or__和__ior__运算符,
1
2
3
4
5
A | B
A |= B
A.union(B, C)
A | B | C
字典
字典是Python中最重要的数据结构, 所有对象的属性字段方法都以字典的形式存储在内存中,
key-value存储, 菲关系型数据库
字典的键必须是可哈希对象, 不可变对象才可以被hash
字典推导式, 过滤字典的部分内容形成新字典
1
字典合并
1
2
3
4
5
6
7
8
9
10
11
a = {'x': 1, 'z': 3 }
b = {'y': 2, 'z': 4 }
# 字典拆包会变为键值对, 可以被字典的构造函数接受
c = {**a, **b} # {'x': 1, 'z': 4, 'y': 2}
# 合并的结果与输入顺序有关, 执行覆盖原则
d = {**b, **a} # {'y': 2, 'z': 3, 'x': 1}
# 也可以使用实例方法 update 实现原地更新
a.update(b) # {'x': 1, 'z': 4, 'y': 2}
通过collections模块中的ChainMap方法可以建立多个映射的逻辑组合,
ChainMap方法本质上是新建了类似字典结构的容器
字典排序
字典分组 itertools.groupby()
字典在Python中的应用, 如何实现动态添加删除属性与字段
collections模块中的Counter, 可以解决的问题
collections模块中的UserDict, 继承
有序字典, 3.7之后默认为有序字典, 实现方式与之前不同
双向链表加哈希表
引入链表
链状结构
与序列型结构显著不同的是, 链状结构的内存模型是离散的,
与数组的区别 适用场景区别
数组: 地址连续 支持随机访问 扩展性差 插入删除成本高
链表: 地址分散 不支持随机访问 访问需要遍历 不支持二分法 扩展性强 插入删除成本低
与数组不同,我们无法在常量时间内访问单链表中的随机元素。 如果我们想要获得第 i 个元素,我们必须从头结点逐个遍历。 我们按索引来访问元素平均要花费 O(N) 时间,其中 N 是链表的长度。
例如,在上面的示例中,头结点是 23。访问第 3 个结点的唯一方法是使用头结点中的“next”字段到达第 2 个结点（结点 6）; 然后使用结点 6 的“next”字段,我们能够访问第 3 个结点。
你可能想知道为什么链表很有用,尽管它在通过索引访问数据时（与数组相比）具有如此糟糕的性能。 在接下来的两篇文章中,我们将介绍插入和删除操作,你将了解到链表的好处。
单向链表
判断环
双向链表
LRU cache
跳表
快慢指针
案例1: 设计LRU缓存
参考内容
网络
socket
TCP/IP TIMEWAIT 滑动窗口
DNS
url浏览器
HTTP/HTTPS
nginx
nio/Aio
REDIS 实现方式 布隆过滤器 一致性哈希 哈希槽 淘汰策略 持久化 消息队列
linux 乐观锁 悲观锁
Java基础 JVM JUC/AQS/多线程 Dubbo Redis MySQL ZK 算法 Netty