Algorithm：每周至少做一个 leetcode 的算法题

因为在重新回顾 <数据结构与算法之美>专栏，所以从该专栏里面提到的算法题开始

1. 基于链表的队列实现

package
com.kaesar.jike_time.shuJvJieGouYuSuanFaZhiMei.chp09;
import
com.kaesar.jike_time.shuJvJieGouYuSuanFaZhiMei.common.Node;
import lombok.extern.slf4j.Slf4j;
import java.util.Scanner;
/**
* 基于链表的队列实现
* 特点：先进先出，新元素插入队尾，出队时从队头取出元素。
*/
@Slf4j
public class NodeQueue {
private Node<String> head, tail; // 队头和队尾
private int count = 0; // 队列中元素个数
private int capacity; // 队列的最大容量
public NodeQueue(int capacity) {
this.head = new Node<>();
this.count = 0;
this.capacity = capacity;
}
public NodeQueue() {
this(Integer.MAX_VALUE);
}
public void enqueue(String item) {
if (count == capacity) {
log.error("队列已满，请稍后重试");
return;
}
Node newNode = new Node(item);
if (count == 0) {
head.next = newNode;
tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
++count;
}
public String dequeue() {
if (count == 0) {
log.error("队列为空，请稍后再试");
return null;
}
Node first = head.next;
head.next = head.next.next;
--count;
return (String) first.item;
}
public static void main(String[] args) {
NodeQueue queue = new NodeQueue(3);
Scanner scanner = new Scanner(System.in);
while (true) {
System.out.print("请输入1或2：1表示存入元素，2表示取出元素。输入 exit 表示退出：");
String flag = scanner.nextLine();
if ("1".equals(flag)) {
System.out.print("请输入要存入的元素；");
String item = scanner.nextLine();
queue.enqueue(item);
} else if ("2".equals(flag)) {
System.out.println(queue.dequeue());
} else if ("exit".equals(flag)) {
break;
}
}
}
}

2. 用数组实现的队列

package
com.kaesar.jike_time.shuJvJieGouYuSuanFaZhiMei.chp09;
/**
* 用数组实现的队列
*/
public class ArrayQueue {
// 数组：items，数组大小：n
private String[] items;
private int n = 0;
private int count = 0; // 队列中元素个数
// head表示队头下标，tail表示队尾下标
private int head = 0;
private int tail = 0;
/**
* 申请一个大小为capacity的数组
*
* @param capacity
*/
public ArrayQueue(int capacity) {
items = new String[capacity];
n = capacity;
}
/**
* 入队
*
* @param item
* @return
*/
public boolean enqueue(String item) {
// 如果tail == n 表示队列已经满了
if (tail == n) return false;
items[tail] = item;
++tail;
++count;
return true;
}
/**
* 出队
*
* @return
*/
public String dequeue() {
// 如果head == tail 表示队列为空
if (head == tail) return null;
String ret = items[head];
++head;
--count;
return ret;
}
}

Review：阅读并点评至少一篇英文技术文章

原文链接：<System Design Interview: An Insider’s Guide> 第五章 <CHAPTER 5: DESIGN CONSISTENT HASHING>

主要内容：

常规的hash算法，使用场景是服务器数量固定且数据均匀分布

一致性哈希概念：一致性哈希是一种特殊的哈希方法，当使用一致性哈希的哈希表重新调整大小时，平均只需重新映射k/n个键，其中k代表键的数量，n代表槽的数量。相比之下，在大多数传统哈希表中，数组槽数量的变化会导致几乎所有的键都需要重新映射

Hash space and hash ring 哈希空间和哈希环

哈希算法的结果是有范围的，这样就可以形成一个哈希环，其中x0表示哈希值的下限，xn表示哈希值的上限

Hash servers 哈希服务器

使用相同的哈希函数f，我们将服务器基于其IP地址或名称映射到环上。图5-5展示了4个服务器被映射到哈希环上的情况。

数据查找：当新数据k0得到哈希值后，顺时针找第一个发现的server，如下图是s0，表示该数据存到s0上

Add a server 添加服务器：当添加一个服务器s4时，如图所示，k0数据按顺时针方向找到的第一个服务器是s4，所以数据需要迁移，迁移范围应该是 s3~s4之间的数据，从s0迁移到s4

Remove a server 删除服务器：如图所示，当s1下线时，k1按照顺时针能找到的第一个服务器是s2，所以需要迁移，迁移数据的范围应该是s0~s1内的数据

简单总结一下，一致性哈希的实现步骤：

• 使用均匀分布的哈希函数将服务器和键映射到环上。
• 要找到一个键映射到了哪个服务器，可以从键的位置开始沿顺时针方向查找，直到遇到环上的第一个服务器。

这是最基本的一致性哈希，会有两个问题：

• 服务器分布不均匀
• 环上的键分配不均匀

Virtual nodes 虚拟节点：每一个真实的server节点对应多个随机的虚拟节点，比如服务器s1实际管理的虚拟节点是s1_0、s1_1、s1_2

查找数据，依旧是顺时针找到最近的虚拟节点，然后得到对应的真实节点

Find affected keys 找到受影响的键（待迁移的数据）

• 新增节点，比如，服务器4被添加到了环上。受影响的范围从新添加的节点s4开始，逆时针绕环移动，直到遇到下一个服务器s3。因此，位于s3和s4之间的所有键需要重新分配到s4。
• 删除节点，比如，当服务器（s1）被移除，受影响的范围从被移除的节点s1开始，逆时针绕环移动，直到找到下一个服务器s0。因此，位于s0和s1之间的所有键必须重新分配到s2。

总结一下，使用一致性哈希的好处：

• 当服务器添加或删除时，密钥的重新分配被最小化。
• 由于数据分布更加均匀，因此很容易实现水平扩展。
• 缓解热点密钥问题。对特定分片的过度访问可能导致服务器过载。想象一下，凯蒂·佩里的数据、贾斯汀·比伯的数据以及Lady Gaga的数据都落在同一个分片上。一致性哈希有助于通过更均匀地分布数据来缓解这个问题。

Tip：学习至少一个技术技巧

这部分想着最近在学习AI，干脆就把记录的学习内容放在这里了，至少对于我来说都是新货、新技巧。

Share：分享一篇有观点和思考的技术文章

平时阅读的一些技术类文章

1. 原文链接：3 分钟讲透什么是 MCP，AI 小白也能懂！

• MCP（Model Context Protocol，模型上下文协议），指的是 AI 和外部工具的通用交互协议。
  MCP与API的区别：MCP 本身并不会取代 API，而是将各种 API 进行封装。AI 只需要和 MCP 这个管家沟通，就能间接调用 API 干活了。
  MCP 导航推荐：
  https://mcp.so/
  https://smithery.ai/
  https://mcps.live/
  总结：再次强化了一下对MCP的理解，准备结合飞书提供的MCP Server来管理下自己的知识库（已完成）。飞书MCP参考文档：https://open.feishu.cn/document/uAjLw4CM/ukTMukTMukTM/mcp_integration/mcp_introduction