latest
jabr/fliphashConstant-time consistent range-hashing algorithm
This package works with Cloudflare Workers, Node.js, Deno, Bun, Browsers
JSR Score
70%
Published
3 months ago (0.1.1)
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293import * as XXH64 from "jsr:@jabr/xxhash64@2.0.0"; type Key = bigint|string interface Hasher { hash(key: Key, seed: bigint, bits: number, iteration: number): bigint; } class XXH3Hasher implements Hasher { private seedBytes = new Uint8Array(BigUint64Array.BYTES_PER_ELEMENT) private seedView = new DataView(this.seedBytes.buffer) constructor(private hasher: XXH64.Hasher) {} private generateSeed(seed: bigint): Uint8Array { this.seedView.setBigUint64(0, seed) return this.seedBytes } hash(key: string, seed: bigint, bits: number, iteration: number) { const mask = BigInt(bits) + BigInt(iteration) << 32n return this.hasher.reseed( this.generateSeed(seed ^ mask) ).update(key).digest('bigint') as bigint } } function intLog2(value: number|bigint) { return (value.toString(2).length - 1) } function maskFrom(value: number|bigint) { return BigInt(Math.pow(2, value.toString(2).length) - 1) } class MoremurHasher implements Hasher { // https://mostlymangling.blogspot.com/2019/12/stronger-better-morer-moremur-better.html hash(key: bigint, seed: bigint, bits: number, iteration: number) { key = key ^ seed key = (key * (BigInt(bits) * 2n + 1n)) & 0xffff_ffff_ffff_ffffn; key = ((key ^ (key >> 27n)) * 0x3C79AC492BA7B653n) & 0xffff_ffff_ffff_ffffn; key = (key * (BigInt(iteration) * 2n + 1n)) & 0xffff_ffff_ffff_ffffn; key = ((key ^ (key >> 33n)) * 0x1C69B3F74AC4AE35n) & 0xffff_ffff_ffff_ffffn; return key ^ (key >> 27n) } } export default class Fliphash { static async instance(seed: bigint = 0n): Promise<Fliphash> { return new this(BigInt(seed), await XXH64.create3()) } private constructor(private seed: bigint, hasher: XXH64.Hasher) { this.xxh3Hasher = new XXH3Hasher(hasher) } private moremurHasher = new MoremurHasher() private xxh3Hasher: XXH3Hasher hash_string(key: string, buckets: number): number { return Number(this.internalHash(this.xxh3Hasher, key, buckets)) } hash_bigint(key: bigint, buckets: number): number { return Number(this.internalHash(this.moremurHasher, key, buckets)) } private internalHash(hasher: Hasher, key: Key, buckets: number) { if (buckets <= 1) { return 0n } const end = buckets - 1 const rehash = (hash: bigint, mask: bigint) => { const maskedHash = hash & mask if (maskedHash === 0n) { return 0n } const log2 = intLog2(maskedHash) const halfMask = maskFrom(maskedHash) >> 1n const flip = hasher.hash(key, this.seed, log2, 0) & halfMask return maskedHash ^ flip } const mask = maskFrom(end) const hash = hasher.hash(key, this.seed, 0, 0) const ph = rehash(hash, mask) if (ph <= end) { return ph } const endLog2 = intLog2(end) for (let iteration = 1; iteration <= 64; iteration++) { const draw = hasher.hash(key, this.seed, endLog2, iteration) & mask if (draw <= mask >> 1n) { break } else if (draw <= end) { return draw } } return rehash(hash, mask >> 1n) } }