土法炼钢 · 系统与基础设施

字符串哈希：Rabin-Karp、滚动哈希与内容定义分块

2026-05-25 | algorithms | #rabin-karp #rolling-hash #polynomial-hash #rabin-fingerprint #thue-morse #buzhash #gear-hash #content-defined-chunking #fastcdc #rsync #restic #borgbackup

滚动哈希的保证来自输入确定后才随机选的素数、基或不可约多项式。本文按 Karp-Rabin 原文推导碰撞界，实测 Thue-Morse 串攻破 2^64 自然溢出，并用 LBFS、FastCDC、restic、borg 的源码与模拟说明内容定义分块。