阅读中文版本

Rolling Hash CLI

A Node CLI that computes a rolling polynomial hash over a sliding window of a file, printing the hash at each window position for block-matching.

node --version

node rhash.mjs file.txt 16

node --test rhash.test.mjs

Prints the rolling hash value at each window position as the window slides across the file, using a polynomial hash with O(1) update.

What it does

Computes a polynomial rolling hash over a sliding window of the file. The initial window hash is computed in O(w), then each slide updates the hash in O(1) by adding the new byte, multiplying by the base, and subtracting the old byte times the base to the window power.

import { readFileSync } from 'node:fs';
const data = readFileSync(process.argv[2]);
const w = +process.argv[3] || 16;
const BASE = 257, MOD = 1000000007n;
let h = 0n, pow = 1n;
for (let i = 0; i < w; i++) { h = (h * BigInt(BASE) + BigInt(data[i])) % MOD; pow = pow * BigInt(BASE) % MOD; }
console.log(h.toString());
for (let i = w; i < data.length; i++) {
  h = (h * BigInt(BASE) + BigInt(data[i]) - BigInt(data[i - w]) * pow % MOD + MOD) % MOD;
  console.log(h.toString());
}

Run and verify

node rhash.mjs file.txt 16

Run the test command to check the implementation: node --test rhash.test.mjs.

Expected Output

Each line is the hash of the current 16-byte window as it slides across the file:

123456789
987654321
...

Limitations

The hash is a polynomial hash with a large modulus, not a cryptographic hash. Collisions are possible but rare for matching purposes. The window size must not exceed the file length.