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 hashrope01 / 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.
| operation | hashrope | Prefix-sum rolling hash | Merkle tree / CDC | Plain rope | Suffix array / tree | Rehash (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_equalAPIs 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.
Bytes live in leaves. Every node stores (length, weight, hash) — computed once, from its children.
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.
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.
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.
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.
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
| Python | JavaScript | Rust | Java |
|---|---|---|---|
| rope_concat | ropeConcat | arena.concat | Rope.concat |
| rope_split | ropeSplit | arena.split | Rope.split |
| rope_substr_hash | ropeSubstrHash | arena.substr_hash | Rope.substrHash |
| rope_repeat | ropeRepeat | arena.repeat | Rope.repeat |
| rope_equal / rope_lcp | ropeEqual / ropeLcp | arena.equal / lcp | Rope.equal / lcp |
| int | bigint | u64 (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.