Spotify
ohayashi
Ichiko Aoba · Windswept Adan · Song · 2020
🔑 并查集为什么适合“连通性”问题，却不适合“路径”问题
并查集（Union-Find / Disjoint Set Union, DSU）解决的核心不是“怎么走”，而是“是不是一伙的”。当图上的边会不断加入，而你反复想问两个点当前是否连通时，如果每次都重新跑一次 BFS 或 DFS，代价会越来越高；并查集的设计思路更直接：它不关心整条路径长什么样，只维护每个点属于哪个集合。
它之所以高效，关键在两个优化。一个是 path compression：每次
但并查集的“快”，是靠主动丢弃大量路径细节换来的。它只告诉你两个点最后是不是在同一个集合里，却不会保留“经过了哪些边”“路径长度是多少”“谁是父谁是子”的真实图结构。所以它特别适合回答 connectivity，却不适合回答 shortest path、具体路径恢复、拓扑先后关系 这类问题。很多人一看到图连起来了，就下意识想用并查集一路做到底，结果在需要距离、方向、层次的时候才发现信息早就没被保存下来。
真正容易踩坑的地方，恰恰在这里：你以为自己维护的是一棵“树”，其实维护的只是一个“集合代表关系”。例如在 Kruskal 中，并查集只负责判断“加这条边会不会成环”，真正决定最小生成树权值的是排序后的贪心过程，不是并查集本身；再比如有些题要求删除边后的动态连通性，普通并查集不支持高效删除，很多时候要改成离线倒序处理，而不是硬在原结构上减边。换句话说，并查集很强，但它强在边界明确：只管合并与查询连通，不管路径语义。
🧪 课后一题：无向图有 6 个点，初始互不连通。依次执行1 和 5 连通，因为 1-2-3 与 4-5 在 后合并成同一集合；6 和 1 不连通，因为 6 从未参与任何合并。
💡 易混淆点：并查集维护的是“属于同一个集合”而不是“图上的父子关系”或“实际路径”，
#CS
并查集（Union-Find / Disjoint Set Union, DSU）解决的核心不是“怎么走”，而是“是不是一伙的”。当图上的边会不断加入，而你反复想问两个点当前是否连通时，如果每次都重新跑一次 BFS 或 DFS，代价会越来越高；并查集的设计思路更直接：它不关心整条路径长什么样，只维护每个点属于哪个集合。
union(x, y) 把两个集合合并，find(x) 找到 x 所在集合的代表元，于是“x 和 y 是否连通”就变成比较 find(x) == find(y)。它之所以高效，关键在两个优化。一个是 path compression：每次
find 时，把沿途节点直接挂到根上，后面再找就更快；另一个是 union by rank/size：总把更小或更浅的树挂到更大或更高的树下面，避免结构退化。两者一起使用后，单次操作的均摊复杂度接近 O(1)，严格地说是 O(α(n))，这里的 α 是反 Ackermann 函数，在实际规模里几乎可以当常数看待。这也是为什么 Kruskal 最小生成树、离线连通性判断、朋友圈合并、岛屿归类这类题几乎都会优先想到并查集。但并查集的“快”，是靠主动丢弃大量路径细节换来的。它只告诉你两个点最后是不是在同一个集合里，却不会保留“经过了哪些边”“路径长度是多少”“谁是父谁是子”的真实图结构。所以它特别适合回答 connectivity，却不适合回答 shortest path、具体路径恢复、拓扑先后关系 这类问题。很多人一看到图连起来了，就下意识想用并查集一路做到底，结果在需要距离、方向、层次的时候才发现信息早就没被保存下来。
真正容易踩坑的地方，恰恰在这里：你以为自己维护的是一棵“树”，其实维护的只是一个“集合代表关系”。例如在 Kruskal 中，并查集只负责判断“加这条边会不会成环”，真正决定最小生成树权值的是排序后的贪心过程，不是并查集本身；再比如有些题要求删除边后的动态连通性，普通并查集不支持高效删除，很多时候要改成离线倒序处理，而不是硬在原结构上减边。换句话说，并查集很强，但它强在边界明确：只管合并与查询连通，不管路径语义。
🧪 课后一题：无向图有 6 个点，初始互不连通。依次执行
union(1,2)、union(2,3)、union(4,5)、union(3,5) 之后，1 和 5 是否连通？6 和 1 是否连通？答案：union(3,5)💡 易混淆点：并查集维护的是“属于同一个集合”而不是“图上的父子关系”或“实际路径”，
find 出来的根只是代表元，不等于原图里的起点、终点或最近公共祖先。#CS
🔐 哈希长度扩展：拼接式签名为什么一文不值
很多系统做消息完整性校验时，图省事会这么干：把密钥和消息直接拼起来，再算个哈希当签名。比如
SHA-256 这类 Merkle-Damgård 系哈希是分块处理的：消息被切成 64 字节的块逐块喂入，每块的输出作为内部状态继续参与下一块计算。于是出现一个致命特性：知道某个消息的哈希值，就等于拿到了处理完该消息后的内部状态。拿到状态就能假装"我已经算到这儿了"，继续往后面追加任意内容并算出新哈希，全程不需要知道 secret。唯一要猜的是 secret 的长度，因为它决定中间那段填充怎么写，而枚举几十种长度对工具来说毫无压力。这就是哈希长度扩展攻击（Hash Length Extension）。
现实中最出名的受害者是 2009 年的 Flickr API：签名方案就是
为什么 HMAC 不怕？HMAC 不是简单拼接，它把密钥派生出两个掩码，一个垫在消息前面算内层哈希，一个垫在结果前面算外层哈希，密钥被两层结构封住，长度扩展无从下手。防御口径很朴素：完整性校验一律用 HMAC，或者干脆用 SHA-3 这类海绵结构哈希；永远不要自己发明
🧪 场景分析：某订单接口用
答案：可以。SHA-256 是 Merkle-Damgård 结构，已知 H(secret m) 就能从内部状态继续追加。用 hashpump 这类工具，枚举猜出 secret 长度后，算出 H(secret原消息 补齐填充&discount=90) 作为新签名；把追加部分（含二进制填充）URL 编码后拼到参数串末尾，服务器 URL 解码得到的就是原消息加新参数，校验通过。这也解释了为什么修复不能靠给消息加随机盐了事，必须换成 HMAC。
💡 核心记忆：
#Security
很多系统做消息完整性校验时，图省事会这么干：把密钥和消息直接拼起来，再算个哈希当签名。比如
sig = SHA-256(secret + message)，服务器收到请求后自己重算一遍比对，一致就认定是可信来源发的。乍看没毛病，secret 藏在里面，攻击者不知道密钥就算不出合法签名。问题出在哈希算法自身的结构上。SHA-256 这类 Merkle-Damgård 系哈希是分块处理的：消息被切成 64 字节的块逐块喂入，每块的输出作为内部状态继续参与下一块计算。于是出现一个致命特性：知道某个消息的哈希值，就等于拿到了处理完该消息后的内部状态。拿到状态就能假装"我已经算到这儿了"，继续往后面追加任意内容并算出新哈希，全程不需要知道 secret。唯一要猜的是 secret 的长度，因为它决定中间那段填充怎么写，而枚举几十种长度对工具来说毫无压力。这就是哈希长度扩展攻击（Hash Length Extension）。
现实中最出名的受害者是 2009 年的 Flickr API：签名方案就是
md5(secret + 参数)，攻击者用一个合法请求的签名就能伪造出带额外参数的请求签名。今天仍能看到不少自研 Webhook 签名、游戏防作弊校验在用这种拼串哈希，几乎一测一个准。为什么 HMAC 不怕？HMAC 不是简单拼接，它把密钥派生出两个掩码，一个垫在消息前面算内层哈希，一个垫在结果前面算外层哈希，密钥被两层结构封住，长度扩展无从下手。防御口径很朴素：完整性校验一律用 HMAC，或者干脆用 SHA-3 这类海绵结构哈希；永远不要自己发明
hash(secret + message) 的变体。正经平台的 Webhook 签名（比如 Stripe）用的就是 HMAC-SHA256，不是没有原因的。🧪 场景分析：某订单接口用
sign = sha256(secret + "user=alice&price=100") 做签名，你截获了一个合法请求，参数和 sign 都可见。能否在不知道 secret 的情况下，伪造出追加 &discount=90（打一折）的请求并算出合法签名？💡 核心记忆：
hash(secret + message) 会把哈希内部状态整个交出去，消息完整性校验请认准 HMAC。#Security
📚 「を踏まえて」不是万能“基于”：它和「に基づいて」差在哪？
技术报告里很常见一种误用：明明想表达“看了前面的结果之后，做了判断和调整”，却一律写成「〜に基づいて」。其实这时更自然的往往是「〜を踏まえて」。它特别适合安全审计、实验复盘、论文讨论、需求修订这类场景：先有事实或前提，再据此做判断、改写设计、调整方案。
边界要抓清。「に基づいて」强调“有明确依据”，后面常接规则、定义、法令、规格、正式数据，语气像“依照……来做”。「を踏まえて」则不是机械照搬，而是“把前提情况考虑进去之后，再往下决定怎么做”，后面常接判断、改善、提案、设计变更。至于「をもとに」，语气更宽，偏“以……为素材/基础加工而成”，没有「を踏まえて」那种“考虑之后作判断”的味道。
所以，「先行研究に基づいて手法を設計した」更像“设计直接建立在既有理论或文献依据上”；而「先行研究の限界を踏まえて手法を設計した」则是在“看清前人不足之后”做出改进，这两个句子在研究写作里不能随便互换。
例如可以直接这样套用：
脅威分析の結果を踏まえて、認証フローにデバイス証明を追加した。
基于威胁分析结果并结合其含义，我们在认证流程中加入了设备证明。
先行研究の限界を踏まえて、本研究では評価指標にロバスト性を加えた。
鉴于先行研究的局限，本研究在评价指标中加入了鲁棒性。
ベンチマークの測定誤差を踏まえて、結果には95%信頼区間を併記した。
考虑到基准测试的测量误差，结果部分同时标注了 95% 置信区间。
反过来，如果你要写的是「仕様書に基づいて実装する」「法令に基づいてデータを管理する」，这里就别换成「を踏まえて」，因为重点不是“综合考虑后调整”，而是“按明确依据执行”。
💡 記憶ポイント：后面有判断、修正、提案、改善，用「を踏まえて」；后面是依照规则、定义、规格执行，用「に基づいて」 。如果你脑子里想的是“考虑到……之后，我们决定……”，大概率就是「を踏まえて」。
#日本語
技术报告里很常见一种误用：明明想表达“看了前面的结果之后，做了判断和调整”，却一律写成「〜に基づいて」。其实这时更自然的往往是「〜を踏まえて」。它特别适合安全审计、实验复盘、论文讨论、需求修订这类场景：先有事实或前提，再据此做判断、改写设计、调整方案。
边界要抓清。「に基づいて」强调“有明确依据”，后面常接规则、定义、法令、规格、正式数据，语气像“依照……来做”。「を踏まえて」则不是机械照搬，而是“把前提情况考虑进去之后，再往下决定怎么做”，后面常接判断、改善、提案、设计变更。至于「をもとに」，语气更宽，偏“以……为素材/基础加工而成”，没有「を踏まえて」那种“考虑之后作判断”的味道。
所以，「先行研究に基づいて手法を設計した」更像“设计直接建立在既有理论或文献依据上”；而「先行研究の限界を踏まえて手法を設計した」则是在“看清前人不足之后”做出改进，这两个句子在研究写作里不能随便互换。
例如可以直接这样套用：
脅威分析の結果を踏まえて、認証フローにデバイス証明を追加した。
基于威胁分析结果并结合其含义，我们在认证流程中加入了设备证明。
先行研究の限界を踏まえて、本研究では評価指標にロバスト性を加えた。
鉴于先行研究的局限，本研究在评价指标中加入了鲁棒性。
ベンチマークの測定誤差を踏まえて、結果には95%信頼区間を併記した。
考虑到基准测试的测量误差，结果部分同时标注了 95% 置信区间。
反过来，如果你要写的是「仕様書に基づいて実装する」「法令に基づいてデータを管理する」，这里就别换成「を踏まえて」，因为重点不是“综合考虑后调整”，而是“按明确依据执行”。
💡 記憶ポイント：
#日本語
Spotify
mostly chimes
Adrianne Lenker · instrumentals · Song · 2020
🔑 布隆过滤器为什么只能说“可能存在”
当系统需要判断一个元素是否见过，直接保存完整集合可能很占内存。布隆过滤器用一个位数组和多个哈希函数代替它：插入元素时，把多个哈希结果对应的位置设为 1；查询时，只要发现其中一个位置是 0，就能确定元素一定不存在。
但如果所有位置都是 1，也不能断言元素一定存在，因为这些 1 可能是其他元素共同设置的。这就是布隆过滤器的核心取舍：用很少的内存换取极快的查询，但允许出现“误报存在”。增加位数组长度或调整哈希函数数量，可以降低误报率；然而，简单地把某个位置改回 0 又可能误伤其他元素，所以普通布隆过滤器不支持安全删除。需要删除能力时，通常改用计数布隆过滤器等变体。
🧪 课后一题：如果布隆过滤器查询结果为“不存在”，这个结论是否绝对可靠？为什么？可靠。在没有哈希错误和数据损坏的前提下，查询路径中只要有一个位为 0，插入该元素时就不可能把它设置为 1，因此它一定没有被插入；布隆过滤器只会误报“存在”，不会误报“不存在”。
💡 易混淆点：布隆过滤器的“存在”是可能存在，而“不存在”才是确定不存在；同时，普通布隆过滤器不能直接删除元素。
#CS
当系统需要判断一个元素是否见过，直接保存完整集合可能很占内存。布隆过滤器用一个位数组和多个哈希函数代替它：插入元素时，把多个哈希结果对应的位置设为 1；查询时，只要发现其中一个位置是 0，就能确定元素一定不存在。
但如果所有位置都是 1，也不能断言元素一定存在，因为这些 1 可能是其他元素共同设置的。这就是布隆过滤器的核心取舍：用很少的内存换取极快的查询，但允许出现“误报存在”。增加位数组长度或调整哈希函数数量，可以降低误报率；然而，简单地把某个位置改回 0 又可能误伤其他元素，所以普通布隆过滤器不支持安全删除。需要删除能力时，通常改用计数布隆过滤器等变体。
🧪 课后一题：如果布隆过滤器查询结果为“不存在”，这个结论是否绝对可靠？为什么？
💡 易混淆点：布隆过滤器的“存在”是可能存在，而“不存在”才是确定不存在；同时，普通布隆过滤器不能直接删除元素。
#CS
🔐 SSRF：你的服务器，可能成了攻击者的内网跳板
SSRF（Server-Side Request Forgery，服务器端请求伪造）发生在应用允许用户提交 URL，并由服务器代为访问时。攻击者不一定需要直接进入内网，只要诱导服务器请求
这类漏洞常见于图片抓取、网页预览、Webhook、PDF 生成和远程文件导入功能。问题的根源不是“请求了一个危险 URL”这么简单，而是服务器把用户输入当成了可信的网络目标，并且往往只检查初始域名，忽略了重定向、特殊 IP 表示方式和解析后的真实地址。
防护时不要只维护一个“禁止访问的域名列表”，更可靠的做法是采用严格的目标白名单，只允许必要的协议、域名和端口；解析域名后检查 IPv4、IPv6 及 IPv4-mapped IPv6 地址，拒绝环回地址、私有地址、链路本地地址和云元数据地址；每次重定向后重新校验，并尽量关闭自动重定向。应用之外，还应通过出站防火墙限制服务器只能访问真正需要的网络，即使应用层校验被绕过，也不能直接触达内网。
🧪 某图片抓取接口只允许
漏洞在于把用户可控 URL 的服务端请求当成普通抓取功能，且只做初始主机名检查、允许跨域跳转；优先进行目标解析和每次跳转后的 IP 校验，再用出站防火墙阻断内网及云元数据地址。
💡 核心记忆：凡是服务器替用户访问 URL，就必须同时验证“访问谁”和“能否连到那里”。
#Security
SSRF（Server-Side Request Forgery，服务器端请求伪造）发生在应用允许用户提交 URL，并由服务器代为访问时。攻击者不一定需要直接进入内网，只要诱导服务器请求
127.0.0.1、云平台元数据地址或内部管理接口，就可能读取敏感信息、调用高权限服务，甚至进一步控制主机。这类漏洞常见于图片抓取、网页预览、Webhook、PDF 生成和远程文件导入功能。问题的根源不是“请求了一个危险 URL”这么简单，而是服务器把用户输入当成了可信的网络目标，并且往往只检查初始域名，忽略了重定向、特殊 IP 表示方式和解析后的真实地址。
防护时不要只维护一个“禁止访问的域名列表”，更可靠的做法是采用严格的目标白名单，只允许必要的协议、域名和端口；解析域名后检查 IPv4、IPv6 及 IPv4-mapped IPv6 地址，拒绝环回地址、私有地址、链路本地地址和云元数据地址；每次重定向后重新校验，并尽量关闭自动重定向。应用之外，还应通过出站防火墙限制服务器只能访问真正需要的网络，即使应用层校验被绕过，也不能直接触达内网。
🧪 某图片抓取接口只允许
https://，并检查 URL 主机名不包含 localhost。攻击者提交一个外部 URL，服务端跟随 302 跳转到 http://169.254.169.254/，随后返回云主机临时凭证。最关键的漏洞点是什么，优先修哪两层？💡 核心记忆：凡是服务器替用户访问 URL，就必须同时验证“访问谁”和“能否连到那里”。
#Security