数据结构和算法(2)
散列表、栈、队列
数据结构和算法(2)
散列表
- 散列表（Hash Table，又称哈希表）是一种高效的数据结构(可以简单的理解为一种高效的数组)，用于实现键值对（Key-Value）的存储和快速查找。
- 查找的平均效率为O(1)
原理
举个简单的例子
A = 1
B = 2
C = 3
D = 4
通过将字符串转化为数字串的过程就是散列,用于对照的密码叫做散列函数。既然是函数，一定是通过某种法则。例如BAD会转化为214，通过数字求和的函数我们可以得到哈希值2 + 1 + 4 = 7，通过求积的函数我们可以得到哈希值2 x 1 x 4 = 8。但是散列函数必须满足调用同一字符串时，返回的哈希值相同的条件，否则就会出问题。
定义:将任意大小的键（如字符串、对象等）转换为固定大小的整数值（哈希值）
处理冲突
有时候我们会遇到一些问题。在前面散列表的一个键BAD返回的哈希值(乘法散列函数)为8，现在我们想加入DAB，我们会发现返回的哈希值仍然是8，这会造成冲突。
解决散列冲突的方法有两种:
开放寻址法(open addressing)和链表法(chaining)
开放寻址法:
如果出现了散列冲突,我们就重新探测一个空闲位置,将其插入。
负载因子: 散列表中一定比例的空闲槽位。公式: 散列表的负载因子 = 填入表中的元素个数 / 散列表的长度
装载因子越大,说明空闲位置越少,冲突越多,散列表的性能会下降。
链表法:
链表法是一种更加常用的散列冲突解决办法,相比开放寻址法,它要简单很多。在散列表中,每个”桶(bucket) “或者”槽(slot) “会对应一条链表,所有散列值相同的元素我们都放到相同槽位对应的链表中。
总结
一般的编程语言都自带散列表的管理机制(Python的字典),会帮我们自动决定散列表的大小、散列函数的逻辑以及扩展的时机。接下来我们要学的就是需要在合适的时机使用散列表来优化算法。
栈和队列
栈（Stack）
储存方式和数组一样，只是有多的规则限制。
1、只能在末尾插入数据
2、只能在末尾读取数据
3、只能在末尾删除数据
后进先出（LIFO, Last In First Out），类似一摞盘子，最后放入的盘子最先取出。
我们习惯把栈的末尾叫做栈顶，把栈的开头称为栈尾
既然有这个机制，一定有它存在的道理。
几个常见的应用场景：
1、函数调用栈
程序执行时，函数调用和返回通过栈管理（后调用的函数先返回）。
2、括号匹配
检查表达式中的括号是否成对（如 {[()]}）。
3、撤销操作（Undo）
编辑器中的撤销功能用栈存储操作历史（最后操作的先撤销）。
4、浏览器历史记录
访问的页面按栈存储，后退时弹出最近访问的页面。
队列
储存方式和数组一样，也有多的规则限制。
1、只能在末尾插入数据
2、只能读取开头数据
3、只能移除开头数据
先进先出（FIFO, First In First Out），类似排队，先来的人先服务。
对于开头和末尾并没有明确的叫法。
几个常见的应用场景：
1、任务调度
CPU 处理进程时，按先来先服务（FIFO）的顺序执行。
2、消息队列
系统间异步通信（如 RabbitMQ、Kafka），消息按顺序处理。
3、广度优先搜索（BFS）
遍历树或图时，用队列存储待访问的节点
4、打印机任务管理
多个打印请求按提交顺序排队处理。
做到这里本该结束，但一提到异步通信，我就来兴趣了，我并不了解异步通信，所以就去查了查AI
异步通信（Asynchronous Communication）
异步通信是一种消息传递模式，其中发送方（生产者）和接收方（消费者）不需要同时在线或立即响应，而是通过**中间媒介（如队列、事件总线）**解耦，实现非阻塞的数据交换。
1. 核心特点
| 特性 | 说明 |
|---|---|
| 非阻塞 | 发送方发出消息后无需等待接收方处理，可继续执行其他任务。 |
| 解耦 | 生产者和消费者不直接依赖彼此，通过中间层（如消息队列）通信。 |
| 可靠性 | 消息可持久化存储，确保即使系统崩溃也不会丢失。 |
| 伸缩性 | 可通过增加消费者实例横向扩展处理能力。 |
2. 同步 vs 异步通信
| 对比维度 | 同步通信 | 异步通信 |
|---|---|---|
| 耦合性 | 强耦合（直接调用） | 松耦合（通过中间件） |
| 响应方式 | 实时等待响应 | 无需立即响应 |
| 性能 | 受被调用方性能影响（可能阻塞） | 高吞吐量（发送即返回） |
| 适用场景 | 需要即时结果的场景（如支付验证） | 耗时任务、流量削峰（如订单处理） |
3. 异步通信的实现方式
(1) 消息队列（Message Queue）
- 原理：生产者将消息发送到队列，消费者从队列拉取消息。
- 中间件：RabbitMQ、Kafka、RocketMQ、AWS SQS。
- 示例：
- 电商系统：用户下单后，订单消息进入队列，库存服务异步扣减库存。
- 日志处理：应用日志发送到Kafka，由日志分析服务消费。
(2) 事件驱动（Event-Driven）
- 原理：通过发布/订阅（Pub-Sub）模式，生产者发布事件，消费者订阅并处理。
- 中间件：Redis Pub/Sub、Apache Pulsar、MQTT。
- 示例：
- 用户注册成功后，发布“用户已注册”事件，触发邮件服务和推荐系统。
(3) 回调（Callback）
- 原理：发送方在消息中附带回调地址，接收方处理完成后通知发送方。
- 示例：
- 支付网关异步通知商户支付结果。
4. 异步通信的优缺点
优点
✅ 提高系统响应速度：发送方无需等待，快速返回。
✅ 解耦系统组件：服务间依赖降低，易于维护和扩展。
✅ 流量削峰：突发流量由队列缓冲，避免系统过载。
✅ 容错性：消息持久化可防止数据丢失。
缺点
❌ 复杂性增加：需引入中间件，维护消息可靠性（如重试、死信队列）。
❌ 延迟问题：消息处理可能延迟，不适合实时性要求高的场景。
❌ 一致性挑战：需额外设计保证最终一致性（如分布式事务）。
5. 典型应用场景
- 微服务架构：服务间通过消息队列通信（如订单服务通知物流服务）。
- 大数据处理：日志、指标数据异步收集（如Flume + Kafka + Spark）。
- 任务调度：耗时任务（如视频转码）放入队列后台处理。
- 物联网（IoT）：设备数据异步上报（如MQTT协议）。
总结
异步通信通过解耦和缓冲提升了系统的伸缩性和可靠性，但需权衡一致性与实时性。现代分布式系统（如电商、社交平台）广泛依赖消息队列（Kafka、RabbitMQ）实现异步化。