Skip to content

Commit e51d49f

Browse files
jdeniaujdeniau
committed
perf(Map): index large hash-collision buckets for faster lookups
HashCollisionNode looked up entries with a linear scan, so a bucket holding many keys that share the same hash degraded build and read performance. Once a bucket grows past a threshold it now builds a secondary index keyed by a per-process seeded hash, restoring near-linear lookups. Small buckets keep the existing linear path, and the public, deterministic hash() is unchanged. Adds __tests__/Map.collision.ts and perf cases for collision-heavy buckets.
1 parent 25c58b0 commit e51d49f

4 files changed

Lines changed: 366 additions & 12 deletions

File tree

‎__tests__/Map.collision.ts‎

Lines changed: 217 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,217 @@
1+
import { describe, expect, it } from '@jest/globals';
2+
import { Map, Set, fromJS, hash, is } from 'immutable';
3+
4+
/**
5+
* Generates `2 ** rounds` distinct strings that all share the same
6+
* `Immutable.hash()`, by concatenating the classic "Aa"/"BB" collision blocks
7+
* (both equal `65 * 31 + 97 === 66 * 31 + 66 === 2112` under the JVM-style
8+
* `31 * h + c` string hash). Inserting these into a Map forces them all into a
9+
* single HashCollisionNode — the hash-flooding scenario this code guards.
10+
*/
11+
function collisionKeys(rounds: number): Array<string> {
12+
let keys = [''];
13+
for (let i = 0; i < rounds; i++) {
14+
const next: Array<string> = [];
15+
for (const k of keys) {
16+
next.push(k + 'Aa');
17+
next.push(k + 'BB');
18+
}
19+
keys = next;
20+
}
21+
return keys;
22+
}
23+
24+
describe('Map hash collisions', () => {
25+
it('the generated keys really do collide (test is meaningful)', () => {
26+
const keys = collisionKeys(8); // 256 keys
27+
const h = hash(keys[0]!);
28+
expect(keys.every((k) => hash(k) === h)).toBe(true);
29+
expect(new globalThis.Set(keys).size).toBe(keys.length); // all distinct
30+
});
31+
32+
it('does not change the public, deterministic hash() of strings', () => {
33+
// The secondary collision hash is internal and seeded; it must not leak
34+
// into the public hash().
35+
expect(hash('a')).toBe(97);
36+
expect(hash('immutable-js')).toBe(510203252);
37+
});
38+
39+
describe('correctness with thousands of colliding keys', () => {
40+
const keys = collisionKeys(11); // 2048 keys, well above the index threshold
41+
42+
it('stores and retrieves every colliding key (built from an object)', () => {
43+
const obj: Record<string, number> = {};
44+
keys.forEach((k, i) => (obj[k] = i));
45+
const map = Map(obj);
46+
47+
expect(map.size).toBe(keys.length);
48+
expect(keys.every((k, i) => map.get(k) === i)).toBe(true);
49+
expect(map.get('not-a-colliding-key', 'default')).toBe('default');
50+
expect(map.has(keys[0]!)).toBe(true);
51+
expect(map.has('not-a-colliding-key')).toBe(false);
52+
});
53+
54+
it('behaves the same whether built transiently or persistently', () => {
55+
const transient = Map<string, number>().withMutations((m) => {
56+
keys.forEach((k, i) => m.set(k, i));
57+
});
58+
let persistent = Map<string, number>();
59+
keys.forEach((k, i) => (persistent = persistent.set(k, i)));
60+
61+
expect(transient.size).toBe(keys.length);
62+
expect(persistent.size).toBe(keys.length);
63+
expect(is(transient, persistent)).toBe(true);
64+
expect(keys.every((k, i) => persistent.get(k) === i)).toBe(true);
65+
});
66+
67+
it('overwrites an existing colliding key without changing size', () => {
68+
const map = Map(keys.map((k, i) => [k, i]));
69+
const updated = map.set(keys[100]!, 9999);
70+
71+
expect(updated.get(keys[100]!)).toBe(9999);
72+
expect(updated.size).toBe(map.size);
73+
// original is untouched (persistence)
74+
expect(map.get(keys[100]!)).toBe(100);
75+
});
76+
77+
it('removes colliding keys and keeps the rest retrievable', () => {
78+
const map = Map(keys.map((k, i) => [k, i]));
79+
const removed = map.remove(keys[50]!).remove(keys[51]!).remove(keys[52]!);
80+
81+
expect(removed.size).toBe(map.size - 3);
82+
expect(removed.get(keys[50]!, 'gone')).toBe('gone');
83+
expect(removed.get(keys[51]!, 'gone')).toBe('gone');
84+
// a previously-removed-around key is still correct (index stayed valid)
85+
expect(removed.get(keys[53]!)).toBe(53);
86+
expect(removed.get(keys[0]!)).toBe(0);
87+
expect(removed.get(keys[keys.length - 1]!)).toBe(keys.length - 1);
88+
});
89+
90+
it('iterates over every colliding entry exactly once', () => {
91+
const map = Map(keys.map((k, i) => [k, i]));
92+
93+
const seen = new globalThis.Set<string>();
94+
map.forEach((_v, k) => seen.add(k));
95+
expect(seen.size).toBe(keys.length);
96+
expect(keys.every((k) => seen.has(k))).toBe(true);
97+
98+
expect(map.keySeq().toArray().sort()).toEqual([...keys].sort());
99+
expect(map.entrySeq().count()).toBe(keys.length);
100+
});
101+
102+
it('keeps equals() and hashCode() consistent', () => {
103+
const a = Map(keys.map((k, i) => [k, i]));
104+
const b = Map(keys.map((k, i) => [k, i]));
105+
expect(is(a, b)).toBe(true);
106+
expect(a.hashCode()).toBe(b.hashCode());
107+
108+
const c = a.set(keys[0]!, -1);
109+
expect(is(a, c)).toBe(false);
110+
});
111+
});
112+
113+
it('mixes colliding and normally-distributed keys', () => {
114+
const keys = collisionKeys(10); // 1024 colliding
115+
const map = Map<string, number | string>(keys.map((k, i) => [k, i]))
116+
.set('alpha', 'a')
117+
.set('beta', 'b');
118+
119+
expect(map.get('alpha')).toBe('a');
120+
expect(map.get('beta')).toBe('b');
121+
expect(map.get(keys[7]!)).toBe(7);
122+
expect(map.size).toBe(keys.length + 2);
123+
});
124+
125+
it('is correct just below and just above the index threshold', () => {
126+
// 8 keys (below threshold 16) then 64 keys (above) — both must be correct.
127+
for (const rounds of [3, 6]) {
128+
const keys = collisionKeys(rounds);
129+
let map = Map<string, number>();
130+
keys.forEach((k, i) => (map = map.set(k, i)));
131+
expect(map.size).toBe(keys.length);
132+
expect(keys.every((k, i) => map.get(k) === i)).toBe(true);
133+
134+
// remove half, the rest must remain correct
135+
let trimmed = map;
136+
keys
137+
.slice(0, keys.length / 2)
138+
.forEach((k) => (trimmed = trimmed.remove(k)));
139+
expect(trimmed.size).toBe(keys.length / 2);
140+
expect(
141+
keys
142+
.slice(keys.length / 2)
143+
.every((k, i) => trimmed.get(k) === i + keys.length / 2)
144+
).toBe(true);
145+
}
146+
});
147+
148+
it('merge() and mergeDeep() work with colliding keys', () => {
149+
const keys = collisionKeys(11); // 2048 colliding
150+
const userObj: Record<string, number> = {};
151+
keys.forEach((k, i) => (userObj[k] = i));
152+
153+
const merged = Map({ existing: -1 }).merge(userObj);
154+
expect(merged.get('existing')).toBe(-1);
155+
expect(merged.get(keys[123]!)).toBe(123);
156+
expect(merged.size).toBe(keys.length + 1);
157+
158+
const deep = Map({ existing: -1 }).mergeDeep(fromJS(userObj));
159+
expect(deep.get(keys[123]!)).toBe(123);
160+
expect(deep.size).toBe(keys.length + 1);
161+
});
162+
163+
it('Set (backed by Map) handles colliding values', () => {
164+
const keys = collisionKeys(11); // 2048 colliding
165+
const set = Set(keys);
166+
167+
expect(set.size).toBe(keys.length);
168+
expect(keys.every((k) => set.has(k))).toBe(true);
169+
expect(set.has('not-in-set')).toBe(false);
170+
171+
const without = set.remove(keys[10]!);
172+
expect(without.has(keys[10]!)).toBe(false);
173+
expect(without.size).toBe(keys.length - 1);
174+
});
175+
176+
it('handles value-object keys that all share one hashCode', () => {
177+
// Exercises the non-string fallback in hashCollisionKey: equality is still
178+
// decided by is()/equals(), never by the (constant) secondary hash.
179+
class Collider {
180+
constructor(readonly id: number) {}
181+
equals(other: unknown): boolean {
182+
return other instanceof Collider && other.id === this.id;
183+
}
184+
hashCode(): number {
185+
return 7; // force every instance into the same collision node
186+
}
187+
}
188+
const items = Array.from({ length: 50 }, (_, i) => new Collider(i));
189+
190+
let map = Map<Collider, number>();
191+
items.forEach((c, i) => (map = map.set(c, i)));
192+
193+
expect(map.size).toBe(items.length);
194+
expect(items.every((c, i) => map.get(new Collider(i)) === i)).toBe(true);
195+
expect(map.get(new Collider(999), 'absent')).toBe('absent');
196+
197+
const removed = map.remove(new Collider(25));
198+
expect(removed.size).toBe(items.length - 1);
199+
expect(removed.get(new Collider(25), 'gone')).toBe('gone');
200+
expect(removed.get(new Collider(26))).toBe(26);
201+
});
202+
203+
it('does not degrade for a large flood of colliding keys', () => {
204+
// A regression guard: with the linear scan this is ~O(n²) and takes seconds
205+
// for 16384 keys; with the seeded index it is ~linear and near-instant.
206+
const keys = collisionKeys(14); // 16384 colliding keys
207+
const obj: Record<string, number> = {};
208+
keys.forEach((k, i) => (obj[k] = i));
209+
210+
const map = Map(obj);
211+
expect(map.size).toBe(keys.length);
212+
// spot-check retrieval across the whole bucket
213+
expect(map.get(keys[0]!)).toBe(0);
214+
expect(map.get(keys[keys.length - 1]!)).toBe(keys.length - 1);
215+
expect(map.get(keys[keys.length >> 1]!)).toBe(keys.length >> 1);
216+
});
217+
});

‎perf/Map.js‎

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -135,4 +135,41 @@ describe('Map', function () {
135135
});
136136
});
137137
});
138+
139+
// Keys built from "Aa"/"BB" blocks all share the same string hash, so they
140+
// pile into a single HashCollisionNode. This is the hash-flooding scenario:
141+
// with a plain linear scan it is O(n²) to build or read them all.
142+
describe('hash collisions', () => {
143+
function collisionKeys(rounds) {
144+
let keys = [''];
145+
for (let i = 0; i < rounds; i++) {
146+
const next = [];
147+
for (let j = 0; j < keys.length; j++) {
148+
next.push(keys[j] + 'Aa');
149+
next.push(keys[j] + 'BB');
150+
}
151+
keys = next;
152+
}
153+
return keys;
154+
}
155+
156+
[8, 10, 12].forEach((rounds) => {
157+
const keys = collisionKeys(rounds);
158+
const obj = {};
159+
for (let ii = 0; ii < keys.length; ii++) {
160+
obj[keys[ii]] = ii;
161+
}
162+
const map = Immutable.Map(obj);
163+
164+
it('builds ' + keys.length + ' colliding keys', () => {
165+
Immutable.Map(obj);
166+
});
167+
168+
it('reads ' + keys.length + ' colliding keys', () => {
169+
for (let ii = 0; ii < keys.length; ii++) {
170+
map.get(keys[ii]);
171+
}
172+
});
173+
});
174+
});
138175
});

‎src/Hash.ts‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -96,6 +96,29 @@ function hashString(string: string): number {
9696
return smi(hashed);
9797
}
9898

99+
// Per-process seed for the secondary collision hash. Never exposed nor
100+
// serialized, so the public `hash()` stays deterministic. An odd base in
101+
// [3, 2^20) keeps `base * h` exact as a double (no `Math.imul`).
102+
const COLLISION_HASH_BASE =
103+
((Math.random() * 0x100000) | 1) % 0x100000 || 0x9e37;
104+
105+
// Secondary hash to index entries within a `HashCollisionNode`, where every key
106+
// shares the same primary `hash()`. Using a different, seeded base scatters
107+
// crafted collision families (e.g. "Aa"/"BB", which only collide under base 31)
108+
// that an attacker cannot precompute without the seed. It only narrows
109+
// candidates — `is()` still decides equality — so non-string keys can safely
110+
// fall back to the (here constant) primary hash and a linear scan.
111+
export function hashCollisionKey(key: unknown): number {
112+
if (typeof key !== 'string') {
113+
return hash(key);
114+
}
115+
let hashed = 0;
116+
for (let ii = 0; ii < key.length; ii++) {
117+
hashed = (COLLISION_HASH_BASE * hashed + key.charCodeAt(ii)) | 0;
118+
}
119+
return hashed;
120+
}
121+
99122
function hashSymbol(sym: symbol): number {
100123
let hashed = symbolMap[sym];
101124
if (hashed !== undefined) {

0 commit comments

Comments
 (0)