文件去重

按大小+哈希找重复文件、硬链接合并去重、Shell fdupes 一行命令。

一、去重原理：两级过滤

为什么不能对所有文件两两比对 MD5？ 假设有 N 个文件，暴力两两比对的时间复杂度是 O(N²)。N=10 万时，需要 50 亿次比较——不可行。

实际做法是两级过滤 + 索引加速，时间复杂度降至 O(N)：

1. 按文件大小分组（O(N)）——不同大小的文件不可能内容相同，直接排除。这一步通常能筛掉 90%+ 的文件，因为文件系统中大小相同的文件占比很低。
2. 组内按哈希比对（O(M²) per group，但 M ≪ N）——只有同大小的文件才需要计算哈希。再加上内存中的哈希索引（dict 查找 O(1)），同一组内有 K 个文件只需 K 次哈希计算，而非 K² 次比对。

Quick Hash 优化：对于大文件（如视频 ISO），读完整文件计算 MD5 也很慢。可以用"首部哈希"——只读文件的前 64KB 和后 64KB 做 MD5。原理是：两个内容不同的文件，其开头和结尾同时相同的概率极低（≈ 2⁻²⁵⁶）。这比全量 MD5 快 10~100 倍，假阳性（误判为相同）概率在工程上可忽略。

二、Python 去重脚本

#!/usr/bin/env python3
"""查找重复文件——两级过滤 + Quick Hash 加速"""
import os, hashlib
from collections import defaultdict

def find_duplicates(root_dir, min_size=1):
    size_map = defaultdict(list)
    for dirpath, _, filenames in os.walk(root_dir):
        for fname in filenames:
            fpath = os.path.join(dirpath, fname)
            try:
                size = os.path.getsize(fpath)
                if size >= min_size:
                    size_map[size].append(fpath)
            except OSError:
                pass

    duplicates = []
    for size, files in size_map.items():
        if len(files) < 2: continue           # 单文件组无需比较
        hash_map = defaultdict(list)
        for fpath in files:
            h = hashlib.md5()
            with open(fpath, 'rb') as f:
                # Quick Hash：只读头尾各 64KB
                head = f.read(65536)
                f.seek(-65536, os.SEEK_END)
                h.update(head + f.read(65536))
            hash_map[h.hexdigest()].append(fpath)

        for group in hash_map.values():
            if len(group) > 1:
                duplicates.append(group)

    return duplicates

if __name__ == '__main__':
    groups = find_duplicates('.')
    total_saved = 0
    for i, group in enumerate(groups, 1):
        size = os.path.getsize(group[0])
        wasted = size * (len(group) - 1)
        total_saved += wasted
        print(f"\n组 {i}: {len(group)} 个 × {size/1024:.0f}KB = 浪费 {wasted/1024:.0f}KB")
        for f in group:
            print(f"  {f}")
    print(f"\n总计可节省: {total_saved/1024/1024:.1f}MB")

三、硬链接去重（节省空间但不删文件）

硬链接 vs 软链接 vs 复制：

操作	新增 inode	新增磁盘占用	删除任一文件影响
copy	✅ 新 inode	✅ 翻倍	互不影响
os.link 硬链接	❌ 共享 inode	❌ 不增	删除一个不减数据（引用计数 >1）
os.symlink 软链接	✅ 新 inode	✅ 少量	删原文件 → 软链接断链

os.link(original, dup) 让两个路径指向同一个 inode——内核为该 inode 增加引用计数。只有当所有硬链接都被删除时，磁盘空间才被释放。硬链接不能跨文件系统。

#!/usr/bin/env python3
import os

def dedup_by_hardlink(duplicate_groups, dry_run=True):
    saved = 0
    for group in duplicate_groups:
        original = group[0]
        for dup in group[1:]:
            if dry_run:
                print(f"  [预览] {dup} → 硬链接 {original}")
            else:
                os.remove(dup)
                os.link(original, dup)
            saved += os.path.getsize(original)
    action = "预览" if dry_run else "已完成"
    print(f"{action}：可节省 {saved/1024/1024:.1f}MB")

四、Shell——fdupes 一行命令

fdupes 的内部算法与上述 Python 实现类似：大小过滤 → MD5 比较。-d 交互式删除时，fdupes 会提问"保留哪个文件"。

#!/bin/bash
# brew install fdupes / apt install fdupes

fdupes -r /path/to/dir                    # 递归查找
fdupes -r -dN /path/to/dir                # -d 删除 -N 不询问，只保留每组第一个
fdupes -r -L /path/to/dir                 # -L 用硬链接替代重复文件

# 手动一行 md5sum 找重复
find . -type f -exec md5sum {} \; | sort | \
    awk '{if($1==prev) print "重复:", $2; else prev=$1}'