v0.3.4 · Python · JS · Rust · Java · zero dependencies

Hash any substring in O(log n).
Edit without rehashing.

hashrope is a weight-balanced rope where every node carries a polynomial fingerprint. Concatenate, split, repeat and fingerprint byte sequences of any size — including ones too big to ever exist in memory.

$ npm i hashrope

01 / Why should I use hashrope?

Every fingerprinting tool makes you pick: fast queries or fast edits.

Rolling hashes answer substring queries instantly — until one byte changes. Merkle trees survive edits, but only at block boundaries. hashrope gives you both, at every byte offset, with composable math.

operationhashropePrefix-sum rolling hashMerkle tree / CDCPlain ropeSuffix array / treeRehash (SHA / xxHash)
Substring hash● O(log n)● O(1)◐ block-aligned only○ O(k) scan○ n/a○ O(k)
Edit (insert/delete)● O(log n)○ O(n) rebuild◐ O(log n)+ boundary shift● O(log n)○ O(n) rebuild○ O(n)
Concatenate two● O(log n)○ O(n)◐ new root, re-chunk● O(log n)○ O(n)○ O(n)
Split at any byte● O(log n)○ O(n)◐ re-chunk● O(log n)○ O(n)○ O(n)
Whole-sequence hash● O(1) at root● O(1)● O(1) at root○ none○ none○ O(n)
Repeat s^q● O(log q), 1 node○ O(|s|·q)○ O(|s|·q)○ O(|s|·q)○ O(|s|·q)○ O(|s|·q)
Exact equality / LCP● shares subtrees◐ hash only◐ hash only◐ O(n) scan● O(1) LCP query◐ hash only
Persistent versions● yes, shared○ no● yes● yes○ no○ no
Streaming window● SlidingWindow● yes● yes○ no○ no◐ incremental only
Cryptographic○ no○ no● yes (w/ SHA)○ —○ —● SHA: yes

n = sequence length, k = substring length, q = repetition count. Complexities exclude uncached exponentiation.

Composable by construction

H(A‖B) = H(A)·x^|B| + H(B). Fingerprints of parts combine into the fingerprint of the whole — so the tree never re-reads bytes it already hashed.

Balanced, persistent, cheap

Strict BB[2/7] weight balance keeps height logarithmic. Edits return new roots that share unchanged subtrees, so every version stays addressable.

Same answer everywhere

Python, JavaScript, Rust and Java are tested against the same pinned fixtures and produce identical fingerprints for identical bytes.

When not to use hashrope

  • — You need tamper resistance. It is a polynomial fingerprint, not a cryptographic digest.
  • — Data is small and never changes. Hash it once with xxHash and move on.
  • — You need fingerprint equality as proof. Use the exact rope_equal APIs to confirm.

02 / How it works

A balanced tree that does algebra on its way up.

Each byte maps to si+1 (so zero-padding can't collide), and the hash is a polynomial over the Mersenne prime p = 261−1. Mersenne reduction is just shifts and adds.

Concat
H(A‖B) = H(A) · x^|B| + H(B)
Repeat
H(Sᵠ) = H(S) · Φ(q, x^|S|)
Base
H(s) = Σ (sᵢ+1) · x^(n−1−i) mod p
live tree from the npm package

Bytes live in leaves. Every node stores (length, weight, hash) — computed once, from its children.

⊕len 10 · d82b95⊕len 8 · b7bcb1"hash"len 4 · 2bb9ca" rop"len 4 · 8a57c7"e "len 2 · 3453
root hash (from tree)
0x02de1aca10d82b95
direct hash of bytes
0x02de1aca10d82b95
match
✓ identical

03 / Playground

Poke it. Every result is checked against a naive rehash.

Type into A and B, pick an operation, and watch the real tree change. Everything runs in your browser on the published npm package.

tree height
3
op time
—
rope hash
0x12cda86148f0bb50
naive full rehash
0x12cda86148f0bb50
verified
✓
⊕len 43 · f0bb50⊕len 20 · b49096⊕len 12 · 7b5feb"the qu"len 6 · 4a0d7f"ick br"len 6 · a409eb⊕len 8 · c9152f"own fo"len 6 · 36f7cb"x "len 2 · 3e0c⊕len 23 · 541af0⊕len 12 · e2bd3a"jumps "len 6 · 78bd77"over t"len 6 · 89dc1c⊕len 11 · 42f217"he laz"len 6 · 4254e2"y dog"len 5 · 0f8fda

04 / Repetition

Represent sq for q = 260. In one node.

RepeatNode stores a child and a count. Its fingerprint comes from a closed-form geometric sum, so a sequence larger than all storage on Earth hashes in microseconds — and you can still query any substring inside it.

represented length
3458764513820540928 bytes
if materialised
3 EB
fingerprint
0x09d42f2e6e381bd2
substring hash at the midpoint
0x000000000019dc7f
time (build + hash + query)
—
nodes used
2 (leaf + repeat)

05 / Benchmarks — live, on your machine

Naive rehashing grows linearly. hashrope barely moves.

This runs in your browser right now against the JavaScript package. Same hasher, same bytes, same fingerprints — the only difference is the data structure.

1 KB → 1 MB · substring = middle third · edit = insert 4 bytes then rehash

06 / Use cases

Wherever sequences change and you still need to compare them.

Collaborative editors

Fingerprint the whole document after every keystroke in O(log n). Peers compare root hashes to detect divergence, then binary-search the tree to the differing range.

ropeInsert → ropeHash

Delta sync & dedup

Find matching ranges between versions at any byte offset — not just chunk boundaries. Stream large inputs through a bounded SlidingWindow.

SlidingWindow, ropeSubstrHash

Compression verification

LZ77 back-references (including overlapping copies) get their fingerprint in closed form via the overlap theorem — verify a decoder without decoding.

appendCopy, hashOverlap

Genomics & long strings

Tandem repeats become RepeatNodes. Exact LCP and range equality skip shared subtrees and prove periodic spans. See the hashrope-bio packages.

ropeRepeat, ropeLcp

Content-addressed caches

Compose cache keys for concatenated artefacts (bundles, logs, build outputs) from the keys of their parts, without re-reading them.

hashConcat

String algorithms

Rabin–Karp style matching, palindrome checks and binary-searched LCP — but on a mutable, persistent sequence instead of a frozen array.

ropeSubstrHash

07 / Four languages, one fingerprint

Python, JavaScript, Rust and Java — side by side.

Same algorithm, same defaults (p = 2⁶¹−1, base 131), same fixtures. A fingerprint computed in your Python pipeline matches the one in your Rust service and your browser.

Python
from hashrope import PolynomialHash, Leaf, rope_concat, rope_hash

h = PolynomialHash()
ab = rope_concat(Leaf(b"hello ", h), Leaf(b"world", h), h)

assert rope_hash(ab) == h.hash(b"hello world")
PyPI: pip install hashrope
hash(b"hello world") computed live in your browser → 0x05f87bb7db23cc7b · the same value in all four languages with default settings.
PythonJavaScriptRustJava
rope_concatropeConcatarena.concatRope.concat
rope_splitropeSplitarena.splitRope.split
rope_substr_hashropeSubstrHasharena.substr_hashRope.substrHash
rope_repeatropeRepeatarena.repeatRope.repeat
rope_equal / rope_lcpropeEqual / ropeLcparena.equal / lcpRope.equal / lcp
intbigintu64 (or BigUint)BigInteger

08 / Guarantees & limits

Honest about what it is.

Collision bound

For two distinct length-n inputs and a random base, Pr[collision] ≤ n / (2⁶¹−1). Fixed default base 131 has known crafted collisions — use exact comparison when it matters.

127-bit mode

MERSENNE_127 profile in every language (Rust via the bigint feature) for a far smaller collision probability.

Exact comparisons

ropeEqual, ropeLcp and range variants compare real bytes, skip shared subtrees and prove periodic spans — no fingerprint trust required.

Zero dependencies

Every package ships without runtime dependencies. Rust is no_std + alloc with arena storage.

Verified parity

Each port is tested against fixtures from a SHA-256-pinned Python wheel; hashes, shapes and bytes are compared.

Not cryptographic

Never use fingerprints for authentication or against an adversary. Pair with SHA-256 when you need that.