RabinKarpHash
Defined in: rolling/rabin-karp-hash.ts:33
Rabin-Karp’s “standard polynomial” rolling hash: ordinary modular integer
arithmetic (unlike RabinFingerprint’s GF(2) polynomial division) —
hash = (hash * base + byteIn) mod modulus, i.e. the sliding-window
recurrence from Wikipedia’s “Rolling hash” article’s “Polynomial rolling
hash” section (first byte carries the highest power of base), with the
departing byte’s contribution (byteOut * base^(windowSize - 1) mod modulus)
subtracted out first. The high-order term is precomputed once at construction
via bigIntModPow, since windowSize is fixed per instance.
Implements
Section titled “Implements”IRollingHash<bigint>
Constructors
Section titled “Constructors”Constructor
Section titled “Constructor”new RabinKarpHash(
windowSize,options?):RabinKarpHash
Defined in: rolling/rabin-karp-hash.ts:44
Parameters
Section titled “Parameters”windowSize
Section titled “windowSize”number
options?
Section titled “options?”Returns
Section titled “Returns”RabinKarpHash
Properties
Section titled “Properties”windowSize
Section titled “windowSize”
readonlywindowSize:number
Defined in: rolling/rabin-karp-hash.ts:34
Accessors
Section titled “Accessors”Get Signature
Section titled “Get Signature”get value():
bigint
Defined in: rolling/rabin-karp-hash.ts:60
The rolling hash’s current value.
Returns
Section titled “Returns”bigint
The rolling hash’s current value.
Implementation of
Section titled “Implementation of”Methods
Section titled “Methods”push()
Section titled “push()”push(
byteIn):bigint
Defined in: rolling/rabin-karp-hash.ts:64
Feeds one more byte into the window, returning the updated value.
Complexity: O(1).
Parameters
Section titled “Parameters”byteIn
Section titled “byteIn”number
The next byte, 0-255.
Returns
Section titled “Returns”bigint