Skip to content

Commit 340c3a1

Browse files
committed
📖redis
1 parent c371562 commit 340c3a1

File tree

5 files changed

+161
-27
lines changed

5 files changed

+161
-27
lines changed
0 Bytes
Binary file not shown.

docs/data-structure-algorithms/algorithm/Double-Pointer.md

Lines changed: 57 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,8 @@ title: 双指针
33
date: 2023-05-17
44
tags:
55
- pointers
6-
categories: LeetCode
6+
- algorithms
7+
categories: algorithms
78
---
89

910
![](https://img.starfish.ink/leetcode/two-pointer-banner.png)
@@ -378,7 +379,7 @@ public boolean hasCycle(ListNode head) {
378379
379380
2. **找到环的起点**:
380381
- 当快慢指针相遇时,我们已经确认链表中存在环。
381-
382+
382383
- 从相遇点开始,慢指针保持不动,快指针回到链表头部,此时两个指针每次都走一步。两个指针会在环的起点再次相遇。
383384
384385
```java
@@ -617,6 +618,15 @@ public int findLengthOfLCIS(int[] nums) {
617618

618619
滑动窗口,就是两个指针齐头并进,好像一个窗口一样,不断往前滑。
619620

621+
滑动窗口算法通过维护一个动态调整的窗口范围,高效解决子串、子数组、限流等场景问题。其核心逻辑可概括为以下步骤:
622+
623+
1. **初始化窗口** 使用双指针 `left``right` 定义窗口边界,初始状态均指向起点。
624+
2. **扩展右边界** 移动 `right` 指针,将新元素加入窗口,并根据问题需求更新状态(如统计字符频率或请求计数)。
625+
3. **收缩左边界** 当窗口满足特定条件(如达到限流阈值或包含冗余元素),逐步移动 `left` 指针缩小窗口,直至不满足条件为止。
626+
4. **记录结果** 在窗口状态变化的每个阶段,捕获符合要求的解(如最长子串长度或限流通过状态)。
627+
628+
629+
620630
子串问题,几乎都是滑动窗口。滑动窗口算法技巧的思路,就是维护一个窗口,不断滑动,然后更新答案,该算法的大致逻辑如下:
621631

622632
```java
@@ -635,7 +645,49 @@ while (right < s.size()) {
635645
}
636646
```
637647

638-
648+
> 以下是适用于字符串处理、限流等场景的通用框架:
649+
>
650+
> ```java
651+
> public class SlidingWindow {
652+
>
653+
> // 核心双指针定义
654+
> int left = 0, right = 0;
655+
> // 窗口状态容器(如哈希表、数组)
656+
> Map<Character, Integer> window = new HashMap<>();
657+
> // 结果记录
658+
> List<Integer> result = new ArrayList<>();
659+
>
660+
> public void slidingWindow(String s, String target) {
661+
> // 初始化目标状态(如字符频率)
662+
> Map<Character, Integer> need = new HashMap<>();
663+
> for (char c : target.toCharArray()) {
664+
> need.put(c, need.getOrDefault(c, 0) + 1);
665+
> }
666+
>
667+
> while (right < s.length()) {
668+
> char c = s.charAt(right);
669+
> right++;
670+
> // 更新窗口状态
671+
> window.put(c, window.getOrDefault(c, 0) + 1);
672+
>
673+
> // 窗口收缩条件
674+
> while (window.get(c) > need.getOrDefault(c, 0)) {
675+
> char d = s.charAt(left);
676+
> left++;
677+
> // 更新窗口状态
678+
> window.put(d, window.get(d) - 1);
679+
> }
680+
>
681+
> // 记录结果(如最小覆盖子串长度)
682+
> if (right - left == target.length()) {
683+
> result.add(left);
684+
> }
685+
> }
686+
> }
687+
> }
688+
> ```
689+
>
690+
>
639691
640692
### 3.1 同向交替移动的两个变量
641693
@@ -696,28 +748,6 @@ public static double getMaxAverage(int[] nums, int k) {
696748
- 如何移动?我们只要把队列的左边的元素移出就行了,直到满足题目要求!
697749
- 一直维持这样的队列,找出队列出现最长的长度时候,求出解!
698750
699-
```java
700-
public static int lengthOfLongestSubstring(String s){
701-
HashMap<Character, Integer> map = new HashMap<>();
702-
int result = 0;
703-
int left = 0;
704-
//为了有左右指针的思想,我把我们常用的 i 写成了 right
705-
for (int right = 0; right < s.length(); right++) {
706-
//当前字符包含在当前有效的子段中,如:abca,当我们遍历到第二个a,当前有效最长子段是 abc,我们又遍历到a,
707-
//那么此时更新 left 为 map.get(a)+1=1,当前有效子段更新为 bca;
708-
//相当于左指针往前移动了一位
709-
char c = s.charAt(right);
710-
if (map.containsKey(s.charAt(right))) {
711-
left = Math.max(left, map.get(c) + 1);
712-
}
713-
//右指针一直往前移动
714-
map.put(c, right);
715-
result = Math.max(result, right - left + 1);
716-
}
717-
return result;
718-
}
719-
```
720-
721751
```java
722752
int lengthOfLongestSubstring(String s) {
723753
Map<Character, Integer> window = new HashMap<>();
@@ -729,14 +759,14 @@ int lengthOfLongestSubstring(String s) {
729759
right++;
730760
// 进行窗口内数据的一系列更新
731761
window.put(c, window.getOrDefault(c, 0) + 1);
732-
// 判断左侧窗口是否要收缩
762+
// 判断左侧窗口是否要收缩,字符串重复时收缩,注意这里是 while 不是 if
733763
while (window.get(c) > 1) {
734764
char d = s.charAt(left);
735765
left++;
736766
// 进行窗口内数据的一系列更新
737767
window.put(d, window.get(d) - 1);
738768
}
739-
// 在这里更新答案
769+
// 在这里更新答案,我们窗口是左闭右开的,所以窗口实际包含的字符数是 right - left,无需 +1
740770
res = Math.max(res, right - left);
741771
}
742772
return res;

docs/interview/Linux-FAQ.md

Lines changed: 91 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -488,6 +488,97 @@ echo never > /sys/kernel/mm/transparent_hugepage/enabled
488488

489489

490490

491+
### poll select epoll 稍微详细的说一下
492+
493+
在 Linux 的 I/O 多路复用设计中,**select****poll****epoll** 是三种核心机制,它们在实现原理、性能特性和适用场景上有显著差异。以下从内核设计角度详细分析:
494+
495+
**一、select:基于轮询的原始模型**
496+
497+
1. **数据结构**
498+
- 使用固定大小的位图(`fd_set`)管理文件描述符(FD),默认支持 1024 个 FD 。
499+
- 每个 FD 对应一个 bit(如 `FD_SET(fd, &readfds)`),通过 `FD_ISSET` 检查就绪状态 。
500+
2. **工作流程**
501+
- 调用 `select` 时,内核将用户空间的 `fd_set` 拷贝到内核空间,遍历所有 FD 检查可读/可写状态(时间复杂度 **O(n)**)。
502+
- 每次调用需重置 FD 集合,导致多次用户态-内核态拷贝开销 。
503+
3. **局限性**
504+
- **FD 数量限制**:受限于 `FD_SETSIZE`(通常 1024),无法扩展 。
505+
- **性能瓶颈**:遍历所有 FD,高并发场景下效率低 。
506+
507+
**二、poll:链表结构的改进版**
508+
509+
1. **数据结构**
510+
511+
- 使用动态链表(`struct pollfd`数组)替代位图,支持无上限的 FD 数量 。
512+
513+
```C
514+
struct pollfd {
515+
int fd; // 文件描述符
516+
short events; // 关注的事件(如 POLLIN)
517+
short revents; // 实际发生的事件
518+
};
519+
```
520+
521+
2. **工作流程**
522+
523+
- 类似 select,内核遍历所有 FD 检查状态(时间复杂度仍为 **O(n)**)。
524+
- 通过 `pollfd` 数组传递 FD,避免重复初始化 。
525+
526+
3. **优化与不足**
527+
528+
- **优势**:突破 FD 数量限制,适合中等并发场景 。
529+
- **劣势**:大量 FD 时,遍历开销仍然显著;需频繁拷贝用户态-内核态数据 。
530+
531+
**三、epoll:事件驱动的高效模型**
532+
533+
1. **数据结构**
534+
- **红黑树**:管理所有注册的 FD(`epoll_ctl` 添加),实现 O(log n) 的查找效率 。
535+
- **就绪队列**:仅存储活跃 FD,`epoll_wait` 直接返回就绪列表(时间复杂度 **O(1)**)。
536+
2. **核心机制**
537+
- 注册-回调模式:
538+
1. **`epoll_ctl`**:注册 FD 及其关注事件(如 `EPOLLIN`),内核通过回调函数跟踪状态变化 。
539+
2. **`epoll_wait`**:阻塞等待就绪事件,仅返回活跃 FD 列表,无需遍历全部 FD 。
540+
- **共享内存**:内核与用户空间共享就绪队列,避免数据拷贝 。
541+
3. **触发模式**
542+
- **水平触发(LT)**:只要 FD 可读/可写,持续通知(类似 select/poll 行为)。
543+
- **边缘触发(ET)**:仅在 FD 状态变化时通知一次,需一次处理完所有数据(减少无效唤醒)。
544+
4. **性能优势**
545+
- **零拷贝**:通过 `mmap` 共享就绪队列,减少用户态-内核态切换 。
546+
- **高效回调**:仅关注活跃 FD,避免无效遍历,适合数万级高并发场景 。
547+
548+
**四、对比总结**
549+
550+
| **特性** | select | poll | epoll |
551+
| --------------- | -------------------- | --------------------- | --------------------------------- |
552+
| **数据结构** | 位图(`fd_set`| 链表(`pollfd` 数组) | 红黑树+就绪队列 |
553+
| **FD 数量限制** | 1024(固定) | 无限制 | 无限制(受系统内存限制) |
554+
| **时间复杂度** | O(n) | O(n) | O(1)(就绪队列) |
555+
| **数据拷贝** | 每次调用拷贝 FD 集合 | 同 select | 注册时拷贝一次,后续共享内存 |
556+
| **触发模式** | 仅水平触发 | 同 select | 支持 LT 和 ET 模式 |
557+
| **适用场景** | 低并发、兼容性要求高 | 中低并发、FD 数量较多 | 高并发(如 Web 服务器、实时系统) |
558+
559+
**五、内核实现细节**
560+
561+
1. **select 的 `do_select`**
562+
- 遍历所有 FD,调用每个 FD 的 `poll` 方法检查状态(如 socket 的 `tcp_poll`)。
563+
- 若无就绪 FD,进程进入睡眠,被唤醒后重新遍历 。
564+
2. **epoll 的回调机制**
565+
- 每个 FD 注册时绑定回调函数(如 `ep_ptable_queue_proc`),状态变化时触发回调,将 FD 加入就绪队列 。
566+
- 就绪队列通过 `ep_item_poll` 关联到红黑树节点 。
567+
3. **性能瓶颈突破**
568+
- **红黑树**:快速查找和插入(对比 select/poll 的线性结构)。
569+
- **事件驱动**:避免轮询,仅处理活跃事件 。
570+
571+
**六、典型应用场景**
572+
573+
1. select/poll:旧系统兼容、FD 数量少(如嵌入式设备)。
574+
2. epoll:
575+
- Nginx(高并发连接)、Redis(高性能事件驱动)。
576+
- 实时通信系统(如 WebSocket 服务器)。
577+
578+
通过以上设计差异,epoll 成为 Linux 高并发网络编程的核心工具,而 select/poll 因历史兼容性仍存在于特定场景中。
579+
580+
581+
491582
### **情景模拟题**
492583

493584
**场景**:服务器响应缓慢,SSH 连接困难,请描述排查思路

docs/interview/MySQL-FAQ.md

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1764,6 +1764,15 @@ UPDATE table_name SET column_a = 1 WHERE id = 1;
17641764
- 最左匹配原则是指在复合索引中,只有当前面的列匹配后,才能继续向后匹配。换句话说,只有当前一个列的值已经确定,才能利用下一个列的索引。
17651765
- 例如,如果你有一个 (`col1`, `col2`, `col3`) 的复合索引,那么只有当 `col1` 的值确定后,`col2` 的索引才会被使用;同样,只有当 `col1` 和 `col2` 的值都确定后,`col3` 的索引才会被使用。
17661766
1767+
> 在 MySQL 中,**联合索引 (a, b, c)** 的最左匹配原则使用情况如下:
1768+
>
1769+
> | **查询条件** | **是否使用索引** | **使用索引的字段** | **底层原因** |
1770+
> | --------------------------- | -------------------- | ------------------ | -------------------------------------------- |
1771+
> | `WHERE a=1 AND b=2 AND c=3` | ✅ 完全使用 | `a, b, c` | 严格遵循最左顺序,B+ 树逐层定位 |
1772+
> | `WHERE c=3 AND b=2 AND a=1` | ✅ 完全使用 | `a, b, c` | 优化器调整顺序后等价于 `a=1 AND b=2 AND c=3` |
1773+
> | `WHERE a=1 AND c=3` | ⚠️ 部分使用(仅 `a`) | `a` | 跳过 `b`,`c` 无法直接通过索引定位 |
1774+
> | `WHERE b=2 AND c=3` | ❌ 索引失效 | 无 | 未包含最左列 `a`,无法触发索引路径 |
1775+
17671776
17681777
17691778
### MySQL常见性能分析手段?

docs/interview/Redis-FAQ.md

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1430,6 +1430,10 @@ Redis 定期检查键的过期时间并删除过期键。这个过程是通过 R
14301430
14311431
### 一组曾经是热点数据,后面不是了,对于lru和lfu处理时会有什么区别?
14321432
1433+
> **LRU(Least Recently Used)**:基于**时间维度**,淘汰最久未被访问的数据。
1434+
>
1435+
> **LFU(Least Frequently Used)**:基于**频率维度**,淘汰一定时期内访问次数最少的数据。
1436+
14331437
**曾经是热点数据,后来不再是热点,对于 LRU 和 LFU 的处理区别**
14341438
14351439
- **对于 LRU 策略**

0 commit comments

Comments
 (0)