主题

会议围绕「超大数据量（100亿/100G级）无法直接加载内存」的共性问题，展开三大算法思想的应用讲解，每个思想对应具体每个思想对应具体题目、解法细节及拓展延伸，同时明确各环节重难点。关键逻辑通过图片注释直观呈现，辅助理解核心流程。

 

一、哈希切割：大文件拆分与同元素聚合

核心思想

通过哈希函数将大文件中的相同元素映射到同一个小文件，解决 “大文件无法加载内存” 和 “均分文件导致统计失真” 的问题，本质是 “分而治之 + 同元素聚合”。

问题 1：100G IP 文件找出现次数最多的 IP 及 Top K IP

问题描述

给定 1 个 100G 大小的 IP 地址文件，内存无法一次性加载，需设计算法：①找出出现次数最多的 IP；②找出 Top K 出现次数的 IP。

关键前提

• 100G 数据远超内存容量，无法直接用 “KV 结构统计次数”（如 HashMap）；
• 目标是保证 “整体最多的 IP 在某个小文件中仍是最多”，否则统计失效。

解法详情

1. 文件拆分逻辑：
   • 确定拆分份数：按 “每份可加载内存” 为标准（如 500M / 份），100G 文件拆分为 200 份（100G=102400M，102400M÷500M≈200 份）；
   • 哈希映射规则：① 将 IP 字符串通过哈希函数（如 MD5、自定义哈希）转换为整数（哈希值）；② 用哈希值对 “拆分份数（200）” 取模，得到文件下标（index = 哈希值 %200）；③ 按下标将该 IP 写入对应小文件，确保相同 IP 的哈希值相同，必然写入同一小文件。
   • 【图片注释 1：哈希切割拆分流程图】

     plaintext

     [100G大文件（含海量IP）]
            ↓
     遍历每个IP → 哈希函数 → 得到整数哈希值
            ↓
     哈希值 % 200（拆分份数）→ 得到文件下标（0-199）
            ↓
     按下标写入对应小文件（0.txt-199.txt，每份500M）
            ↓
     结果：相同IP必然在同一个小文件中
     

2. 统计与结果整合：
   • 逐个加载 200 个小文件（每份 500M，内存可承载），用 KV 结构（如 HashMap）统计每个小文件中 IP 的出现次数；
   • ① 找出 “每个小文件中出现次数最多的 IP”，再对比这 200 个 IP 的次数，最大值即为整体最多 IP；
   • ② 收集所有小文件中 IP 的（IP - 次数）键值对，用堆排序（小顶堆 / 大顶堆）筛选 Top K。
   • 【图片注释 2：结果整合逻辑图】

     plaintext

     [小文件0] → 统计 → 最多IP：A（次数：1000）
     [小文件1] → 统计 → 最多IP：B（次数：800）
     ...
     [小文件199] → 统计 → 最多IP：C（次数：1200）
            ↓
     对比所有小文件的“最多IP次数” → 整体最多IP：C（1200次）
            ↓
     收集所有（IP-次数）→ 小顶堆筛选 → Top K IP
     

重难点提炼

重点	难点
哈希切割的核心是 “同元素聚合”，而非单纯拆分	理解 “均分文件为何不可行”：【图片注释 3：均分 vs 哈希切割对比图】```
均分方案：
[大文件] → 均分 → 小文件 1（含 IPX：1 次）、小文件 2（含 IPX：1 次）... 小文件 10（含 IPX：1 次）
统计 → 每个小文件最多 IP 为其他 IP（如 IPY：5 次）→ 误判整体最多 IP 为 IPY

哈希切割方案：[大文件] → 哈希映射 → 小文件 3（含 IPX：10 次）、其他小文件无 IPX统计 → 小文件 3 最多 IP 为 IPX（10 次）→ 正确识别整体最多 IP

|

| 拆分份数的计算逻辑（按“单文件内存承载量”反向推导） | 哈希函数的选择：需保证相同IP映射到同一文件，且哈希值分布均匀（避免小文件大小失衡） |

### 问题2：100亿整数文件（40G）找出现一次的整数（哈希切割解法）
#### 解法复用
1. 拆分逻辑：将40G文件按“每份500M”拆分为80份（40G=40960M÷500M≈80份）；
2. 哈希映射：将每个整数哈希后对80取模，写入对应小文件（相同整数必在同一文件）；
   - 【图片注释4：整数哈希切割示意图】

[40G 大文件（100 亿整数）]↓遍历每个整数 → 哈希函数 → 整数哈希值↓哈希值 % 80 → 文件下标（0-79）↓写入对应小文件（0.txt-79.txt，每份 500M）

plaintext

3. 统计筛选：逐个加载小文件，用KV结构统计整数出现次数，筛选出“出现次数=1”的整数，汇总即为结果。

#### 重难点
- 重点：哈希切割的通用性（可解决“任意大文件的同元素统计问题”）；
- 难点：无需关注整数的重复特性，仅需保证“同元素聚合”，降低单文件处理压力。

### 问题3：两个100亿整数文件（各40G）求交集（哈希切割解法）
#### 问题描述
两个文件各含100亿个整数（各40G），内存仅1G，需找出两个文件的共同整数（交集）。

#### 解法详情
1. 拆分阶段：
- 对文件A、文件B使用**相同的哈希函数和拆分份数**（如200份），分别拆分为A1-A200、B1-B200小文件；
- 核心保证：若整数x在A中属于Ai，在B中必属于Bi（同一哈希函数+同一取模份数）；
- 【图片注释5：双文件哈希切割示意图】

[文件 A（40G）] → 哈希函数 H + 取模 200 → A1、A2...A200[文件 B（40G）] → 哈希函数 H + 取模 200 → B1、B2...B200↓关键：整数 x 在 A 中映射到 Ai → 在 B 中必映射到 Bi

plaintext

2. 交集计算：
- 逐个对（A1&B1）、（A2&B2）…（A200&B200）求交集（每份小文件500M，1G内存可同时加载两个）；
- 用HashSet存储Ai中的整数，遍历Bi，判断元素是否在HashSet中，存在则为交集元素，汇总所有交集即为结果；
- 【图片注释6：对应小文件求交集流程图】

[A1] → 加载到 HashSet（内存可承载）[B1] → 遍历每个元素 → 检查是否在 HashSet 中↓存在 → 存入交集文件不存在 → 跳过↓依次处理（A2&B2）...（A200&B200）→ 最终交集文件

plaintext

#### 重难点
- 重点：两个文件的“拆分规则完全一致”是交集计算的前提；
- 难点：避免拆分后小文件大小失衡（需保证哈希函数的均匀性）。

---

## 二、位图（BitSet）：极致压缩内存的位运算应用
### 核心思想
用**1个比特位（bit）表示1个数据的存在状态**（0=不存在，1=存在），内存占用极致压缩（如42亿个整数仅需512M内存），可通过多位图组合或位运算扩展功能。

### 关键内存计算（必记）
- 1个bit表示1个数据状态；
- 1字节（Byte）=8bit，1G=1024M=1024×1024KB=1024×1024×1024Byte=8.589934592×10^9 bit；
- 无符号int最大值为42亿（≈4.2×10^9），需4.2×10^9 bit内存 → 4.2×10^9 ÷8 ÷1024 ÷1024≈512M；
- 【图片注释7：位图内存占用对比图】

传统存储（int 类型）：42 亿个整数 → 42 亿 ×4Byte=16.8G位图存储（bit 类型）：42 亿个整数 → 42 亿 ×1bit=512M内存压缩比：32:1（4Byte=32bit）

plaintext

### 问题1：100亿整数文件（40G）找出现一次的整数（位图解法）
#### 解法1：双位图（推荐，简单易懂）
1. 设计逻辑：用两个位图（BitSet1、BitSet2）的“两位组合”表示整数出现次数：
 | 组合（BitSet1, BitSet2） | 含义 |
 |--------------------------|------|
 | 00 | 整数未出现 |
 | 01 | 整数出现1次（目标） |
 | 10 | 整数出现2次 |
 | 11 | 整数出现3次及以上 |
 - 【图片注释8：双位图状态映射示意图】

整数 x 的状态记录：

• 未出现 → BitSet1 [x] = 0，BitSet2 [x] = 0（00）
• 出现 1 次 → BitSet1 [x] = 0，BitSet2 [x] = 1（01）
• 出现 2 次 → BitSet1 [x] = 1，BitSet2 [x] = 0（10）
• 出现≥3 次 → BitSet1 [x] = 1，BitSet2 [x] = 1（11）

plaintext

2. 操作步骤：
- 遍历100亿整数，对每个整数x：
① 若（00）→ 设为01（BitSet1=0，BitSet2=1）；
② 若（01）→ 设为10（BitSet1=1，BitSet2=0）；
③ 若（10）或（11）→ 保持不变（无需记录超过2次的状态）；
- 遍历两个位图，找出所有“组合为01”的整数，即为结果；
- 【图片注释9：双位图遍历筛选示意图】

遍历整数 0~42 亿：对每个整数 i，检查（BitSet1 [i], BitSet2 [i]）：

• 01 → 加入结果集
• 其他组合 → 跳过

plaintext

#### 解法2：单位图（进阶，节省内存）
1. 设计逻辑：用1个位图的“2个比特位”表示1个整数的出现次数（而非1个比特位表示1个整数），即1字节（8bit）可表示4个整数的状态；
- 【图片注释10：单位图比特位分配示意图】

1 字节（8bit）：bit0 bit1 bit2 bit3 bit4 bit5 bit6 bit7对应整数： 0 号 0 号 1 号 1 号 2 号 2 号 3 号 3 号每个整数占用 2bit：0 号整数（bit0+bit1）、1 号整数（bit2+bit3）...状态映射：00 = 未出现，01=1 次，10=2 次，11=≥3 次

plaintext

2. 操作步骤：
- 位图操作修改：将原“x÷8（找字节下标）、x%8（找bit下标）”改为“x÷4（找字节下标）、(x%4)×2（找起始bit位）”；
- 状态表示：每个整数占用2bit，对应00（未出现）、01（1次）、10（2次）、11（≥3次）；
- 遍历位图时，按2bit为单位解析状态，筛选出01组合的整数。

#### 重难点提炼
| 重点 | 难点 |
|------|------|
| 双位图的“两位组合”逻辑（用位状态表示次数，而非仅表示存在） | 单位图的比特位分配：理解“1个整数占2bit”的映射规则（÷4、×2的计算逻辑） |
| 位图的内存压缩优势（512M解决40G数据问题） | 状态转换的边界条件（如出现次数从1→2时，两位的翻转逻辑） |

### 问题2：两个100亿整数文件求交集（位图解法）
#### 解法详情
1. 初始化两个位图（BitSetA、BitSetB），分别存储文件A、文件B的整数（存在则设为1，不存在为0）；
- 【图片注释11：位图存储文件数据示意图】

文件 A 中的整数：5、8、12 → BitSetA [5]=1，BitSetA [8]=1，BitSetA [12]=1（其余为 0）文件 B 中的整数：8、12、15 → BitSetB [8]=1，BitSetB [12]=1，BitSetB [15]=1（其余为 0）

plaintext

2. 位运算计算目标集合：
- 交集：BitSetA & BitSetB（两位均为1时结果为1，即两文件均存在的整数）；
- 并集：BitSetA | BitSetB（任意一位为1时结果为1，即两文件所有不重复整数）；
- 差集：BitSetA ^ BitSetB（两位不同时结果为1，即仅在一个文件中存在的整数）；
- 【图片注释12：位图位运算结果示意图】

BitSetA：0 0 0 0 0 1 0 0 1 0 0 0 1 ...BitSetB：0 0 0 0 0 0 0 0 1 0 0 0 1 ...交集（&）：0 0 0 0 0 0 0 0 1 0 0 0 1 ... → 整数 8、12并集（|）：0 0 0 0 0 1 0 0 1 0 0 0 1 ... → 整数 5、8、12、15差集（^）：0 0 0 0 0 1 0 0 0 0 0 0 0 ... → 整数 5、15

plaintext

3. 遍历运算后的位图，提取所有值为1的整数，即为对应集合结果。

#### 重难点
- 重点：位图位运算的特性（&、|、^对应集合运算）；
- 难点：理解“位图存储的是存在性，而非次数”，适用于集合关系计算（交集/并集/差集）。

### 问题3：100亿整数文件找出现次数不超过2次的整数
#### 解法详情
1. 复用双位图逻辑（BitSet1、BitSet2），状态定义不变（00=未出现，01=1次，10=2次，11=≥3次）；
- 【图片注释13：目标状态筛选示意图】

遍历两个位图，筛选组合为 “01” 或 “10” 的整数：

• 01 → 出现 1 次（符合条件）
• 10 → 出现 2 次（符合条件）
• 00/11 → 不符合条件（跳过）

plaintext

2. 遍历位图，筛选出“组合为01或10”的整数（即出现1次或2次的整数），汇总即为结果。

#### 重难点
- 重点：位图状态与“次数条件”的对应关系（按需筛选目标状态组合）；
- 难点：内存适配性（两个位图共占用512M×2=1G，刚好匹配题目给出的1G内存限制）。

---

## 三、布隆过滤器：近似查找与去重（允许误判）
### 核心思想
基于多个哈希函数将数据映射到位图中，用于快速判断“数据是否存在”，特点是**内存占用极小、查询速度快，但存在误判（仅会将“不存在”误判为“存在”）** ，适用于允许近似查找的场景。

### 问题：两个100亿URL（query）文件求交集
#### 要求
分别给出精确算法和近似算法。

#### 解法1：精确算法（哈希切割复用）
- 逻辑：与“两个整数文件求交集”完全一致，将URL作为字符串进行哈希切割，相同URL映射到同一小文件，再逐对小文件求交集；
- 优势：无误差，结果精确；
- 劣势：需拆分文件，IO开销略高；
- 【图片注释14：URL哈希切割求交集示意图】

[文件 A（100 亿 URL）] → 哈希函数 H + 取模 200 → A1-A200[文件 B（100 亿 URL）] → 哈希函数 H + 取模 200 → B1-B200↓逐对处理（A1&B1）...（A200&B200）→ 精确交集文件

plaintext

#### 解法2：近似算法（布隆过滤器）
1. 初始化布隆过滤器（基于位图实现，含多个哈希函数）；
2. 遍历文件A的所有URL，通过多个哈希函数映射到位图，将对应bit位设为1；
 - 【图片注释15：布隆过滤器映射示意图】

布隆过滤器（位图）：bit0 bit1 bit2 bit3 bit4 bit5 ...URL1 → 哈希函数 H1 → 2 → bit2=1→ 哈希函数 H2 → 5 → bit5=1→ 哈希函数 H3 → 7 → bit7=1URL2 → 哈希函数 H1 → 3 → bit3=1→ 哈希函数 H2 → 6 → bit6=1→ 哈希函数 H3 → 9 → bit9=1...结果：文件 A 的 URL 通过多个哈希函数，在了你图中标记多个 bit 位为 1

plaintext

3. 遍历文件B的所有URL，对每个URL通过相同的哈希函数映射：
- 若所有映射的bit位均为1 → 判定为“可能存在于文件A”（交集候选）；
- 若任意一个映射的bit位为0 → 判定为“一定不存在于文件A”；
4. 收集所有候选URL，即为近似交集。

#### 拓展：布隆过滤器的删除操作
- 问题：布隆过滤器的bit位只能设为1，无法直接删除（删除会影响其他数据的映射）；
- 解决方案：采用“计数布隆过滤器”（每个bit位扩展为计数器，如4bit），插入时计数器+1，删除时计数器-1；
- 【图片注释16：计数布隆过滤器示意图】

传统布隆过滤器：bit 位（0/1）→ 仅记录存在性计数布隆过滤器：4bit 计数器（0-15）→ 记录出现次数URL1 插入 → 计数器 + 1（值 = 1）URL1 再次插入 → 计数器 + 1（值 = 2）URL1 删除 → 计数器 - 1（值 = 1）

plaintext

- 弊端：存在“计数回绕”风险（计数器溢出后，负数可能被误判为正数）。

#### 重难点提炼
| 重点 | 难点 |
|------|------|
| 布隆过滤器的适用场景（允许误判的近似查找/去重） | 误判原因：不同数据可能通过多个哈希函数映射到相同的bit位组合（哈希碰撞）；<br>【图片注释17：误判场景示意图】<br>```
URLx → H1=2，H2=5，H3=7 → bit2=1、bit5=1、bit7=1
URLy（未在文件A中）→ H1=2，H2=5，H3=7 → 所有bit位均为1 → 误判为“存在于文件A”
``` |
| 精确算法与近似算法的选择依据（是否允许误差、对内存/速度的要求） | 计数布隆过滤器的“回绕风险”（需限制数据插入次数或扩大计数器位数） |

---

## 四、补充内容：课程安排
- 总课程量：10节（高级算法专题）；
- 当前进度：第4节；
- 剩余课程：预计4-5节（共8节可完成核心内容）；
- 拓展阅读：一致性哈希（未详细讲解，推荐参考相关博客）。

---

## 整体重难点总结
### 核心重点
1. 三大算法的核心定位：
- 哈希切割：解决“大文件拆分+同元素聚合”，适用于统计类问题（次数最多、Top K）；
- 位图：解决“内存极致压缩+集合运算”，适用于存在性判断、交集/并集/差集、次数状态统计；
- 布隆过滤器：解决“近似查找+低内存”，适用于允许误判的去重/交集场景。
2. 通用逻辑：超大数据量处理的核心是“避免直接加载内存”，通过“拆分、压缩、映射”转化为可处理的小数据量。

### 核心难点
1. 哈希函数的设计（保证均匀性、同元素映射一致性）；
2. 位图的状态扩展（用多位组合表示次数，而非仅表示存在）；
3. 布隆过滤器的误判控制（哈希函数个数、位图大小的权衡）；
4. 内存与IO的平衡（拆分份数、文件大小的合理设计）。