MultiMap

import { MultiMap } from "jsr:@ende/data-structures/unstable-multimap";

class · experimental

class MultiMap<K, V> implements Iterable<[K, V]>

A map that associates each key with an ordered list of values.

Unlike Map, each key can hold multiple values. Values are stored in insertion order, and duplicate values under the same key are preserved.

Iterator methods (MultiMap.prototype.entries, MultiMap.prototype.groups, MultiMap.prototype.keys, MultiMap.prototype.values) return in constant time and iterate lazily; fully draining them is linear in the total value count (or the number of distinct keys, for MultiMap.prototype.keys).

Method	Per-call time complexity
`MultiMap.prototype.size`	Constant
`MultiMap.prototype.valueCount`	Constant
`MultiMap.prototype.add`	Amortized constant
`MultiMap.prototype.get`	Linear in the bucket size (copy)
`MultiMap.prototype.has`	Constant
`MultiMap.prototype.hasEntry`	Linear in the bucket size
`MultiMap.prototype.delete`	Constant
`MultiMap.prototype.deleteEntry`	Linear in the bucket size
`MultiMap.prototype.clear`	Linear in the key count
`MultiMap.prototype.forEach`	Linear in the total value count
`MultiMap.prototype.toMap`	Linear in the total value count
`MultiMap.groupBy`	Linear in the number of items

Example: Usage

import { MultiMap } from "@ende/data-structures/unstable-multimap";
import { assertEquals } from "@ende/assert";

const map = new MultiMap([["a", 1], ["a", 2], ["b", 3]]);

assertEquals(map.get("a"), [1, 2]);
assertEquals(map.get("b"), [3]);

Example: Preserves insertion order and duplicates

import { MultiMap } from "@ende/data-structures/unstable-multimap";
import { assertEquals } from "@ende/assert";

const map = new MultiMap<string, number>();
map.add("a", 2).add("a", 1).add("a", 2);

assertEquals(map.get("a"), [2, 1, 2]);
assertEquals(map.size, 1);

Constructors

`constructor`

new MultiMap(entries?: Iterable<readonly [K, V]> | null)

experimental

Creates a new instance.

entries?: Iterable<readonly [K, V]> | null: An iterable of key-value pairs for the initial entries. Duplicate values for the same key are preserved in insertion order.

Example: Creating an empty map

import { MultiMap } from "@ende/data-structures/unstable-multimap";
import { assertEquals } from "@ende/assert";

const map = new MultiMap<string, number>();
assertEquals(map.size, 0);

Example: Creating a map from an iterable

import { MultiMap } from "@ende/data-structures/unstable-multimap";
import { assertEquals } from "@ende/assert";

const map = new MultiMap([["a", 1], ["a", 2], ["b", 3]]);
assertEquals(map.get("a"), [1, 2]);

Static methods

`groupBy`

static groupBy<K, T>(items: Iterable<T>, keyFn: (item: T, index: number) => K): MultiMap<K, T>

experimental

Groups items from an iterable by the result of keyFn, returning a new multimap. Mirrors the shape of Map.groupBy, but returns a MultiMap so further mutation is supported.

Item order is preserved within each bucket.

items: Iterable<T>: The items to group.
keyFn: (item: T, index: number) => K: A function called for each item with the item and its zero-based index; its return value is the bucket key.

Returns

A new MultiMap of grouped items.

Example: Usage

import { MultiMap } from "@ende/data-structures/unstable-multimap";
import { assertEquals } from "@ende/assert";

const users = [
  { name: "Ada", role: "admin" },
  { name: "Bo", role: "user" },
  { name: "Cy", role: "admin" },
];

const byRole = MultiMap.groupBy(users, (u) => u.role);

assertEquals(byRole.get("admin"), [
  { name: "Ada", role: "admin" },
  { name: "Cy", role: "admin" },
]);
assertEquals(byRole.get("user"), [{ name: "Bo", role: "user" }]);

Example: The key function receives the item index

import { MultiMap } from "@ende/data-structures/unstable-multimap";
import { assertEquals } from "@ende/assert";

const grouped = MultiMap.groupBy(
  ["a", "b", "c", "d"],
  (item, index) => index < 2 ? "first-half" : "second-half",
);

assertEquals(grouped.get("first-half"), ["a", "b"]);
assertEquals(grouped.get("second-half"), ["c", "d"]);

Properties

`[Symbol.toStringTag]`

readonly [Symbol.toStringTag]: "MultiMap"

experimental

A string tag for the class, used by Object.prototype.toString().

Example: Usage

import { MultiMap } from "@ende/data-structures/unstable-multimap";
import { assertEquals } from "@ende/assert";

const map = new MultiMap();
assertEquals(map[Symbol.toStringTag], "MultiMap");

Methods

`size`

get size(): number

experimental

The number of distinct keys in the map.

Returns

The number of distinct keys in the map.

Example: Usage

import { MultiMap } from "@ende/data-structures/unstable-multimap";
import { assertEquals } from "@ende/assert";

const map = new MultiMap([["a", 1], ["a", 2], ["b", 3]]);
assertEquals(map.size, 2);

`valueCount`

get valueCount(): number

experimental

The total number of values stored across all keys, counting duplicates.

In contrast to MultiMap.prototype.size — which reports the number of distinct keys, matching the Map convention — this counts every individual value. Maintained in O(1): add() increments it, delete() and deleteEntry() decrement it, and clear() resets it.

Returns

The total number of values across all keys.

Example: Usage

import { MultiMap } from "@ende/data-structures/unstable-multimap";
import { assertEquals } from "@ende/assert";

const map = new MultiMap([["a", 1], ["a", 2], ["b", 3]]);
assertEquals(map.size, 2);
assertEquals(map.valueCount, 3);

map.add("a", 2);
assertEquals(map.valueCount, 4);

map.deleteEntry("a", 1);
assertEquals(map.valueCount, 3);

`add`

add(key: K, value: V): this

experimental

Appends a value to the list stored under the given key. Duplicate values are preserved.

key: K: The key to add the value under.
value: V: The value to append.

Returns

The instance.

Example: Usage

import { MultiMap } from "@ende/data-structures/unstable-multimap";
import { assertEquals } from "@ende/assert";

const map = new MultiMap<string, number>();
map.add("a", 1).add("a", 2);

assertEquals(map.get("a"), [1, 2]);

`get`

get(key: K): V[] | undefined

experimental

Returns a snapshot of the values associated with the given key, in insertion order, or undefined if the key does not exist.

The returned array is a fresh copy; mutating it does not affect the map, and later mutations to the map are not reflected in it. For read-only traversal across all keys, prefer MultiMap.prototype.groups to avoid the per-call copy.

key: K: The key to look up.

Returns

A fresh array of values in insertion order, or undefined.

Example: Usage

import { MultiMap } from "@ende/data-structures/unstable-multimap";
import { assertEquals } from "@ende/assert";

const map = new MultiMap([["a", 1], ["a", 2]]);

assertEquals(map.get("a"), [1, 2]);
assertEquals(map.get("b"), undefined);

`has`

has(key: K): boolean

experimental

Returns true if the key exists with at least one value.

key: K: The key to check.

Returns

true if the key exists, false otherwise.

Example: Usage

import { MultiMap } from "@ende/data-structures/unstable-multimap";
import { assertEquals } from "@ende/assert";

const map = new MultiMap([["a", 1]]);

assertEquals(map.has("a"), true);
assertEquals(map.has("b"), false);

`hasEntry`

hasEntry(key: K, value: V): boolean

experimental

Returns true if the [key, value] entry exists in the map (i.e. the given value appears at least once under the given key).

key: K: The key to look up.
value: V: The value to check.

Returns

true if the entry exists, false otherwise.

Example: Usage

import { MultiMap } from "@ende/data-structures/unstable-multimap";
import { assertEquals } from "@ende/assert";

const map = new MultiMap([["a", 1], ["a", 2]]);

assertEquals(map.hasEntry("a", 1), true);
assertEquals(map.hasEntry("a", 3), false);
assertEquals(map.hasEntry("b", 1), false);

`delete`

delete(key: K): boolean

experimental

Removes all values for the given key.

key: K: The key to remove.

Returns

true if the key existed and was removed, false otherwise.

Example: Usage

import { MultiMap } from "@ende/data-structures/unstable-multimap";
import { assertEquals } from "@ende/assert";

const map = new MultiMap([["a", 1], ["a", 2], ["b", 3]]);
assertEquals(map.delete("a"), true);
assertEquals(map.delete("a"), false);

assertEquals(map.has("a"), false);
assertEquals(map.size, 1);

`deleteEntry`

deleteEntry(key: K, value: V): boolean

experimental

Removes the first occurrence of the [key, value] entry from the map. If the key's list becomes empty, the key is also removed.

key: K: The key to look up.
value: V: The value to remove.

Returns

true if an entry was removed, false otherwise.

Example: Usage

import { MultiMap } from "@ende/data-structures/unstable-multimap";
import { assertEquals } from "@ende/assert";

const map = new MultiMap([["a", 1], ["a", 2], ["a", 1]]);

assertEquals(map.deleteEntry("a", 1), true);
assertEquals(map.get("a"), [2, 1]);

assertEquals(map.deleteEntry("a", 1), true);
assertEquals(map.get("a"), [2]);

`clear`

clear(): void

experimental

Removes all entries.

Example: Usage

import { MultiMap } from "@ende/data-structures/unstable-multimap";
import { assertEquals } from "@ende/assert";

const map = new MultiMap([["a", 1], ["b", 2]]);
map.clear();

assertEquals(map.size, 0);

`forEach`

forEach<T = undefined>(callbackfn: (this: T, value: V, key: K, map: this) => void, thisArg?: T): void

experimental

Executes a provided function once for each individual value in the map, in insertion order of keys and values.

Within a bucket, the set of values to visit is fixed at the time the bucket is entered, so a callback that mutates the current key's list (via add() or deleteEntry()) will not extend or shift the visit. Cross-bucket mutations during iteration (adding or deleting other keys) are not supported and may skip or repeat keys.

callbackfn: (this: T, value: V, key: K, map: this) => void: The function to call for each value.
thisArg?: T: Value to use as this when executing callbackfn.

Example: Usage

import { MultiMap } from "@ende/data-structures/unstable-multimap";
import { assertEquals } from "@ende/assert";

const map = new MultiMap([["a", 1], ["a", 2], ["b", 3]]);
const result: [string, number][] = [];
map.forEach((value, key) => result.push([key, value]));

assertEquals(result, [["a", 1], ["a", 2], ["b", 3]]);

Example: With thisArg

import { MultiMap } from "@ende/data-structures/unstable-multimap";
import { assertEquals } from "@ende/assert";

const map = new MultiMap([["a", 1], ["a", 2], ["b", 3]]);
const counter = { total: 0 };
map.forEach(function (value) {
  this.total += value;
}, counter);

assertEquals(counter.total, 6);

`entries`

entries(): IterableIterator<[K, V]>

experimental

Returns an iterator of all [key, value] pairs, with each value yielded individually across all keys, in insertion order.

Mutating the map during iteration is not supported and may skip or repeat entries.

Returns

An iterator of [key, value] pairs.

Example: Usage

import { MultiMap } from "@ende/data-structures/unstable-multimap";
import { assertEquals } from "@ende/assert";

const map = new MultiMap([["a", 1], ["a", 2], ["b", 3]]);

assertEquals(Array.from(map.entries()), [["a", 1], ["a", 2], ["b", 3]]);

`groups`

groups(): IterableIterator<[K, V[]]>

experimental

Returns an iterator of [key, values] pairs, where values is the list of values associated with that key in insertion order.

Use this when you need both the key and its full value list, for example to filter by bucket size. For individual [key, value] pairs, use MultiMap.prototype.entries.

Each yielded array is a fresh snapshot; mutating it does not affect the map, and later mutations to the map are not reflected in it. Mutating the map during iteration is not supported and may skip or repeat buckets.

Returns

An iterator of [key, values] pairs.

Example: Usage

import { MultiMap } from "@ende/data-structures/unstable-multimap";
import { assertEquals } from "@ende/assert";

const map = new MultiMap([["a", 1], ["a", 2], ["b", 3]]);

assertEquals(Array.from(map.groups()), [["a", [1, 2]], ["b", [3]]]);

Example: Filter by bucket size

import { MultiMap } from "@ende/data-structures/unstable-multimap";
import { assertEquals } from "@ende/assert";

const map = new MultiMap([["a", 1], ["a", 2], ["b", 3]]);
const collisions: string[] = [];
for (const [key, values] of map.groups()) {
  if (values.length > 1) collisions.push(key);
}

assertEquals(collisions, ["a"]);

`keys`

keys(): IterableIterator<K>

experimental

Returns an iterator of all distinct keys in the map, in insertion order.

Mutating the map during iteration is not supported and may skip or repeat keys.

Returns

An iterator of keys.

Example: Usage

import { MultiMap } from "@ende/data-structures/unstable-multimap";
import { assertEquals } from "@ende/assert";

const map = new MultiMap([["a", 1], ["a", 2], ["b", 3]]);

assertEquals(Array.from(map.keys()), ["a", "b"]);

`values`

values(): IterableIterator<V>

experimental

Returns an iterator of all individual values across all keys, in insertion order.

Mutating the map during iteration is not supported and may skip or repeat values.

Returns

An iterator of values.

Example: Usage

import { MultiMap } from "@ende/data-structures/unstable-multimap";
import { assertEquals } from "@ende/assert";

const map = new MultiMap([["a", 1], ["a", 2], ["b", 3]]);

assertEquals(Array.from(map.values()), [1, 2, 3]);

`toMap`

toMap(): Map<K, V[]>

experimental

Returns a new Map snapshot of the multimap, with each key mapped to a fresh array of its values in insertion order.

The returned map and its value arrays are owned by the caller; mutating them does not affect the multimap, and later mutations to the multimap are not reflected in the snapshot. This is the natural inverse of MultiMap.groupBy and the Map.groupBy builtin.

Returns

A new Map<K, V[]> snapshot.

Example: Usage

import { MultiMap } from "@ende/data-structures/unstable-multimap";
import { assertEquals } from "@ende/assert";

const map = new MultiMap([["a", 1], ["a", 2], ["b", 3]]);

assertEquals(map.toMap(), new Map([["a", [1, 2]], ["b", [3]]]));

`[Symbol.iterator]`

[Symbol.iterator](): IterableIterator<[K, V]>

experimental

Returns an iterator of all [key, value] pairs, with each value yielded individually. The map is not modified. Same as MultiMap.prototype.entries.

Mutating the map while iterating is not supported and may skip or repeat entries.

Returns

An iterator of [key, value] pairs.

Example: Usage

import { MultiMap } from "@ende/data-structures/unstable-multimap";
import { assertEquals } from "@ende/assert";

const map = new MultiMap([["a", 1], ["a", 2], ["b", 3]]);

assertEquals(Array.from(map), [["a", 1], ["a", 2], ["b", 3]]);

`[Symbol.for("Deno.customInspect")]`

[Symbol.for("Deno.customInspect")](inspect: (value: unknown, options: unknown) => string, options: unknown): string

experimental

Custom output for Ende.inspect, rendering the multimap as MultiMap(size) { key => [values], ... }. Each key and bucket is inspected via the provided inspect callback so caller-configured options (colors, depth, circular detection) are honored.

inspect: (value: unknown, options: unknown) => string: Internal inspect function.
options: unknown: Inspect options forwarded from the host.

Returns

The string representation of the multimap.

Example: Usage

import { MultiMap } from "@ende/data-structures/unstable-multimap";

const map = new MultiMap([["a", 1], ["a", 2], ["b", 3]]);
console.log(map);

Source