TS SparseSet

TS SparseSet is a high-performance TypeScript data structure implementing a sparse set, providing constant-time operations and cache-friendly dense storage. Ideal for ECS architectures, game engines, simulations, and any ID-indexed data.

---

Features

• O(1) Operations: add, remove, has, get, ensure, and index lookups.
• Dense Storage: Compact arrays for optimal data locality and iteration speed.
• Swap-Remove Semantics: Maintains dense compactness after deletions without gaps.
• Full Iteration Support: Native iterators, values(), ids(), entries(), forEach().
• Zero-GC Hot Path: No intermediate allocations in iteration modes.
• TypeScript Native: Fully typed, generic, and safe.

---

Installation

npm install ts-sparse-set

---

Usage Example

import { SparseSet } from 'ts-sparse-set';

const set = new SparseSet<number>();

set.add(10, 42);
set.add(20, 100);

console.log(set.has(10)); // true
console.log(set.get(20)); // 100

set.add(10, 77);
console.log(set.get(10)); // 77

set.remove(20);
console.log(set.has(20)); // false

// Iteration (dense order)
for (const entry of set) {
  console.log(entry.id, entry.value);
}

// Using ensure(...)
const v = set.ensure(50, () => 123);
console.log(v); // 123

// Utility iteration helpers
console.log([...set.ids()]);    // [10, 50]
console.log([...set.values()]); // [77, 123]
console.log(set.size());        // 2

---

API Documentation

class SparseSet<V>

Core Methods

Method	Description
add(id: number, value: V): V	Inserts a new value or replaces an existing one.
get(id: number): V | null	Retrieves a value or returns null if not present.
has(id: number): boolean	Checks if an element exists.
remove(id: number): void	Removes the element using O(1) swap-remove logic.
size(): number	Returns the number of elements stored.
clear(): void	Removes all elements.

Iteration Helpers

Method	Description
[Symbol.iterator]()	Iterates over { id, value } entries in dense order.
ids(): Generator<number>	Iterates over all ids.
values(): Generator<V>	Iterates over all values.
entries(): Generator<[number, V]>	Iterates over [id, value] tuples.
forEach(fn)	Efficient callback-based iteration without allocations.

Utility Methods

Method	Description
ensure(id: number, factory: () => V): V	Returns existing value or inserts a new one lazily.
tryGetIndex(id: number): number	Returns dense index or -1 if id does not exist.

---

Benchmarks

Tested on:

• CPU: AMD Ryzen 7 7700 (8-core, up to 5.4 GHz)
• RAM: 32 GB DDR5-5600
• OS: Windows 11 Pro
• Runtime: Node.js v24.11.1 (tsx)
• Set size: 1,000,000 entities

Operation	Throughput (ops/sec)	Per-operation latency
add()	30.0 – 31.0 million	~32–34 ns
has()	9.7 – 9.9 million	~101–103 ns
get()	7.6 – 7.7 million	~130–132 ns
remove() (swap-remove)	13.0 – 13.9 million	~72–77 ns
ensure(id, factory)	4.0 million	~250 ns
size()	>526 million	~1.9 ns
forEach() (1M elements)	191–193 passes/sec	~5.2 ms
ids() / values()	64–65 passes/sec	~15.4–15.6 ms
Generator iteration	54–55 passes/sec	~18–19 ms

When to Use SparseSet

SparseSet excels when:

• IDs are numeric and bounded.
• You need fast add/remove with compact dense data.
• You rely heavily on iteration speed (ECS, physics, grids, pools).
• You want predictable memory layout and minimal GC pressure.

It is not a general-purpose map or associative container — it is optimized for performance-critical numeric ID use cases.

---

Contributing

Issues, PRs, and suggestions are welcome. Project repository: https://github.com/yazmeyaa/ts-sparse-set

---