Hashing decimal numbers is wrong
Composites with different decimal numbers hash to the same value:
```ts
const c1 = Composite({ a: 2.0 });
const c2 = Composite({ a: 2.5 });
assert(!Composite.equal(c1, c2)); // fails
```
The reason for this is that the implementation in `MurmurHashStream.update` only hashes 4 bytes but Javascript numbers are 8 bytes:
```ts
case "number":
this._writeByte(chunk & 0xff);
this._writeByte((chunk >>> 8) & 0xff);
this._writeByte((chunk >>> 16) & 0xff);
this._writeByte((chunk >>> 24) & 0xff);
return;
```
I tried to fix this by hashing all 8 bytes in a similar way:
```ts
case "number":
this._writeByte(chunk & 0xff);
this._writeByte((chunk >>> 8) & 0xff);
this._writeByte((chunk >>> 16) & 0xff);
this._writeByte((chunk >>> 24) & 0xff);
this._writeByte((chunk >>> 32) & 0xff);
this._writeByte((chunk >>> 40) & 0xff);
this._writeByte((chunk >>> 48) & 0xff);
this._writeByte((chunk >>> 56) & 0xff);
return;
```
But that doesn't work because JS bitwise operations only work on 32-bit integers so it converts `chunk` to a 32 bit int and hence this doesn't work.
GPT-5 found this to work:
```ts
// Allocate these once, outside the hot path
const buf = new ArrayBuffer(8)
// dv and u8 are 2 different views on the same buffer `buf`
const dv = new DataView(buf)
const u8 = new Uint8Array(buf)
export class MurmurHashStream implements Hasher {
// ...
update(chunk: symbol | string | number | bigint): void {
switch (typeof chunk) {
// ...
case "number":
dv.setFloat64(0, chunk, true) // fixed little-endian
this._writeByte(u8[0]!)
this._writeByte(u8[1]!)
this._writeByte(u8[2]!)
this._writeByte(u8[3]!)
this._writeByte(u8[4]!)
this._writeByte(u8[5]!)
this._writeByte(u8[6]!)
this._writeByte(u8[7]!)
return
```
关闭于 2025-09-10 6 条评论