Dictionary

public struct Dictionary[K, V, H = DefaultHasher] where K: Hashable, H: Hasher, H: Defaultable { /* private fields */ }

An unordered hash map keyed by any K: Hashable, parameterized over the hasher type H (defaults to DefaultHasher).

Uses open addressing with linear probing and a 75% load-factor threshold for resizes; capacity always grows to the next power of two. Storage is reference-counted with copy-on-write, so copying a Dictionary is O(1) and only the next mutation pays for the deep clone. Iteration order is unspecified and may change between versions or after any mutation. For ordered alternatives consider keeping an ordered key list separately; for set-only behavior see Set.

Examples

var ages: [String: Int64] = [:];
ages("Alice") = 30;
ages("Bob")   = 25;

ages("Alice");                // Some(30)
ages("Carol", default: 0);    // 0

for (name, age) in ages.iter() { ... }
let sum = ages.values.iter().sum();

Hashing

The hash for each key is cached in its bucket so resizes don't recompute it. Replacing the hasher (H) lets you swap in SipHasher, FxHasher, etc.; the default is DefaultHasher and resolves through the [K: V] shorthand.

Capacity & Reallocation

count is live entries; capacity is total slots. The table resizes (doubling capacity, starting from 8) once count reaches 75% of capacity. Use reserveCapacity(...) to pre-grow and shrinkToFit() to release excess.

Representation

One field: an RcBox[DictionaryStorage[K, V, H]] holding (buckets, len, cap) over a heap bucket array.

Memory Model

Reference-counted storage with copy-on-write value semantics. Copying a Dictionary is O(1) and shares the bucket array; the next mutation on a shared dictionary triggers makeUnique(), which deep-clones via DictionaryStorage.clone() so the mutation is invisible to other copies.

Guarantees

Every key satisfies K: Hashable. The cached hash is computed once per insert and reused on resize.
count <= capacity * 3 / 4 after every mutation (the resize threshold).
Removing a key leaves a .Deleted tombstone; lookups still work but tombstones reduce effective capacity until the next resize.
Iteration order is not specified.

Properties

public var capacity: Int64 { get }

Total slots in the bucket array — always >= count. Read-only.

Resizes (doubling) trigger when count reaches 75% of capacity. Tombstones count against the threshold even though they don't count toward count. The actual value after init(capacity:) rounds up to the next power of two.

Examples

let d = Dictionary[String, Int64](capacity: 100);
d.capacity;  // 128

public var count: Int64 { get }

Number of live (.Occupied) entries. Read-only; O(1).

Excludes tombstones — count only reflects what iter()/contains(...) would see.

Examples

["a": 1, "b": 2].count;  // 2
[:].count;               // 0

public var isEmpty: Bool { get }

true when the dictionary holds no live entries; equivalent to count == 0.

Reads more naturally than the comparison.

Examples

[:].isEmpty;           // true
["a": 1].isEmpty;      // false

public var keys: KeysView[K, V] { get }

Lazy view of the dictionary's keys, iterable in unspecified order.

Constructing the view is O(1) — it shares the bucket pointer and skips empty/deleted slots during iteration. The view is invalidated by any mutation that may reallocate (insertion past the load threshold, reserveCapacity, shrinkToFit).

Examples

let dict = ["a": 1, "b": 2, "c": 3];
for key in dict.keys { print(key) }
let keyArray = Array(from: dict.keys);

public var values: ValuesView[K, V] { get }

Lazy view of the dictionary's values, iterable in unspecified order.

Same iteration order as keys — the two views walk the buckets in lockstep, so zip(dict.keys, dict.values) yields pairs equivalent to dict.iter(). Invalidated by any mutation that may reallocate.

Examples

let dict = ["a": 1, "b": 2, "c": 3];
for value in dict.values { print(value) }
let sum = dict.values.iter().sum();  // 6

Initializers

public init(dictionaryLiteral: std.memory.LiteralSlice[(K, V)])

Creates a dictionary by inserting every (K, V) pair from a literal slice in order.

Last-write-wins on duplicate keys (same as init(from:)). An empty literal yields an empty unallocated dictionary.

Examples

// Triggered by the dictionary-literal syntax:
let dict: [String: Int64] = ["a": 1, "b": 2];

public init()

Creates an empty dictionary with no allocation.

Capacity starts at zero; the first insert allocates the smallest bucket array (currently 8 slots). For pre-sized creation use init(capacity:).

Examples

var d = Dictionary[String, Int64]();
d.count;     // 0
d.capacity;  // 0

public init[I](from: I) where I: Iterable, I.Item == (K, V)

Creates a dictionary by inserting every (key, value) pair produced by an iterable.

Last write wins for duplicate keys. For a panic-on-duplicate variant use init(uniquePairs:). Capacity grows geometrically as inserts arrive — for sized sources, follow up with shrinkToFit() if memory matters.

Examples

let pairs = [("a", 1), ("b", 2)];
let dict = Dictionary(from: pairs);              // ["a": 1, "b": 2]
let dups = Dictionary(from: [("a", 1), ("a", 2)]);  // ["a": 2] — later wins

public init[I, E](grouping: I, by: (E) -> K) where I: Iterable, I.Item == E, V == Array[E]

Buckets each element of an iterable into an array under the key derived from keyFunc.

The value type is constrained to Array[E]: each bucket accumulates the elements that mapped to it, in insertion order within that bucket. Useful for building "index-by" tables from a flat collection. The keyFunc runs once per element.

Examples

let words = ["apple", "apricot", "banana", "blueberry"];
let grouped = Dictionary(grouping: words) { (w) in w.chars.first().unwrap() };
// ["a": ["apple", "apricot"], "b": ["banana", "blueberry"]]

let nums = [1, 2, 3, 4, 5];
let parity = Dictionary(grouping: nums) { (n) in n % 2 };
// [0: [2, 4], 1: [1, 3, 5]]

public init(consuming lang.ptr[(K, V)], consuming lang.i64)

Compiler-emitted bridge for [k: v, ...] literals.

Not called by user code directly — the parser lowers literal expressions into a (ptr, count) pair which this constructor wraps in a LiteralSlice and forwards to init(dictionaryLiteral:).

Safety

The compiler guarantees _dictionaryLiteralPointer points to exactly _dictionaryLiteralCount initialized (K, V) pairs.

public init[I](uniquePairs: I) where I: Iterable, I.Item == (K, V)

Creates a dictionary from key-value pairs, panicking on any duplicate key.

Use this when duplicate keys would indicate a bug in upstream data; for last-write-wins semantics use init(from:). Each pair triggers a contains check before insertion, so it's slower than init(from:) for large inputs.

Errors

Panics with "Dictionary(uniquePairs:): duplicate key" the first time pairs yields a key already in the dictionary.

Examples

let dict = Dictionary(uniquePairs: [("a", 1), ("b", 2)]);
Dictionary(uniquePairs: [("a", 1), ("a", 2)]);
// PANIC: Dictionary(uniquePairs:): duplicate key

public init(capacity: Int64)

Creates an empty dictionary sized to hold at least the requested number of entries without resizing.

The actual allocated capacity is the next power of two >= capacity (minimum 8). A non-positive capacity behaves like init() (no allocation). Panics on allocation failure.

Examples

var d = Dictionary[String, Int64](capacity: 100);
d.capacity;   // 128 (next power of two)
d.count;      // 0

Methods

public func all(where: (K, V) -> Bool) -> Bool

true when every entry satisfies predicate(key, value) (vacuously true for empty).

Short-circuits on the first failure. Dual of any(where:).

Examples

["a": 2, "b": 4].all { (k, v) in v % 2 == 0 };  // true
["a": 1, "b": 2].all { (k, v) in v % 2 == 0 };  // false
[:].all { (k, v) in false };                    // true (vacuous)

public func allKeys(of: V) -> Array[K]

Returns every key whose value equals value.

O(capacity), allocates an Array[K]. Result order matches bucket layout and is therefore unspecified. Empty array if no matches.

Examples

["a": 1, "b": 2, "c": 1].allKeys(of: 1);  // ["a", "c"]  — order unspecified
["a": 1].allKeys(of: 99);                  // []

public func any(where: (K, V) -> Bool) -> Bool

true when at least one entry satisfies predicate(key, value).

Alias for contains(where:) — the two names exist so predicate-style code reads naturally regardless of context. Short-circuits on the first match.

Examples

["a": 1, "b": 5].any { (k, v) in v > 3 };  // true
[:].any { (k, v) in true };                // false (empty)

public mutating func clear()

Removes every entry, leaving the bucket array allocated and reset to all-.Empty.

O(capacity). The buffer is kept so subsequent inserts don't reallocate; follow with shrinkToFit() to release it.

Examples

var dict = ["a": 1, "b": 2];
dict.clear();    // dict = [:]
dict.capacity;   // unchanged

public func compactMapValues[U]((V) -> U?) -> Dictionary[K, U, H]

Returns a new dictionary with each value run through transform; entries whose transform(value) is None are dropped.

Useful for parse-or-skip patterns. The result is unsized at construction (since the final count isn't known until the pass completes); for fixed transforms that always succeed, mapValues(...) avoids the allocation policy difference.

Examples

let dict = ["a": "1", "b": "two", "c": "3"];
let parsed = dict.compactMapValues { (s) in Int64.parse(s) };
// ["a": 1, "c": 3] — "two" failed to parse

public func contains(K) -> Bool

true if key is present in the dictionary.

Wraps findEntry. For value-based search use the V: Equatable extension's containsValue(value:).

Examples

["a": 1, "b": 2].contains("a");  // true
["a": 1, "b": 2].contains("z");  // false

public func contains(where: (K, V) -> Bool) -> Bool

true if any entry satisfies predicate(key, value).

Linear scan; short-circuits on the first match. false for empty dictionaries. The aliased shape any(satisfy:) exists for symmetry with Array.

Examples

["a": 1, "b": 5].contains { (k, v) in v > 3 };  // true
["a": 1, "b": 2].contains { (k, v) in v > 3 };  // false

public func containsValue(V) -> Bool

true if any entry's value equals value.

O(capacity) — every bucket is inspected because the dictionary is keyed on K, not V. For O(1) checks against a small set of values, build a Set[V] instead.

Examples

["a": 1, "b": 2].containsValue(2);  // true
["a": 1, "b": 2].containsValue(5);  // false

public func countItems(where: (K, V) -> Bool) -> Int64

Returns the number of entries for which predicate(key, value) is true.

Linear scan, no short-circuit. For just a presence check use any(where:); for a yes/no on every entry, all(where:).

Examples

["a": 1, "b": 2, "c": 3].countItems { (k, v) in v > 1 };  // 2
[:].countItems { (k, v) in true };                        // 0

public func deepClone() -> Dictionary[K, V, H]

Returns a fully-detached copy of the dictionary, with no shared storage.

Walks every bucket and re-inserts the live entries into a freshly-sized table. Use over clone() when you specifically want to avoid the lazy COW share — for example, before passing the copy to another thread or system that might race with further mutations.

Examples

let a = ["x": [1, 2, 3]];
let b = a.deepClone();  // fully independent copy

public func filter(where: (K, V) -> Bool) -> Dictionary[K, V, H]

Returns a new dictionary containing only entries for which predicate(key, value) is true.

Non-mutating mirror of retain(where:). Allocates a fresh dictionary; for in-place filtering use retain or removeAll(where:).

Examples

let dict = ["a": 1, "b": 2, "c": 3];
let big = dict.filter { (k, v) in v > 1 };  // ["b": 2, "c": 3]

public func first(where: (K, V) -> Bool) -> (K, V)?

Returns some entry matching predicate(key, value), or None.

"First" is determined by bucket order, which is hash-dependent and unspecified — treat the result as arbitrary among matching entries. Short-circuits on the first match.

Examples

let dict = ["a": 1, "b": 5, "c": 3];
dict.first { (k, v) in v > 2 };  // Some entry with v > 2
dict.first { (k, v) in v > 99 }; // None

public func firstKey(of: V) -> K?

Returns some key mapping to value, or None.

O(capacity); short-circuits on the first match. "First" is determined by bucket order and is unspecified — for an exhaustive list use allKeys(of:).

Examples

["a": 1, "b": 2].firstKey(of: 2);  // Some("b")
["a": 1, "b": 2].firstKey(of: 5);  // None

public mutating func insert(K, V) -> V?

Inserts (key, value), replacing any existing entry for key, and returns the old value (or None) on update.

Triggers ensureCapacity() and may resize before the insert lands. The cached hash is computed once here. For transform-based updates see update(...) and upsert(...).

Examples

var dict = ["a": 1];
dict.insert("b", 2);  // None;     dict = ["a": 1, "b": 2]
dict.insert("a", 9);  // Some(1);  dict = ["a": 9, "b": 2]

public func mapValues[U]((V) -> U) -> Dictionary[K, U, H]

Returns a new dictionary with each value run through transform, keys unchanged.

Pre-sized to self.capacity so the first build avoids resizing. The result's value type can change (V → U); for a version that drops None results see compactMapValues(...).

Examples

let dict = ["a": 1, "b": 2];
let doubled = dict.mapValues { (v) in v * 2 };
// ["a": 2, "b": 4]

public mutating func merge(Dictionary[K, V, H], uniquingKeysWith: (V, V) -> V)

Merges every entry of other into self, calling combine to resolve key collisions.

combine(existing, incoming) is invoked exactly once per collision — pick one, return both summed, or use (_, new) for last-write-wins. New keys are inserted directly. For a non-mutating variant use merging(...).

Examples

var a = ["x": 1, "y": 2];
let b = ["y": 20, "z": 30];
a.merge(b) { (old, new) in old + new };
// a == ["x": 1, "y": 22, "z": 30]

public mutating func merge[I](from: I, uniquingKeysWith: (V, V) -> V) where I: Iterable, I.Item == (K, V)

Merges every (key, value) pair from an arbitrary iterable into self, calling combine on collisions.

Same semantics as merge(...) but accepts any iterable of pairs — useful for arrays of tuples, generator output, or streamed sources.

Examples

var dict = ["a": 1];
dict.merge(from: [("b", 2), ("c", 3)]) { (_, new) in new };
// dict == ["a": 1, "b": 2, "c": 3]

public func merging(Dictionary[K, V, H], uniquingKeysWith: (V, V) -> V) -> Dictionary[K, V, H]

Returns a new dictionary that is self merged with other, resolving collisions via combine.

Non-mutating mirror of merge(...). Internally clones via COW (cheap until the next mutation) and merges into the copy.

Examples

let a = ["x": 1, "y": 2];
let b = ["y": 20, "z": 30];
let merged = a.merging(b) { (_, new) in new };
// merged == ["x": 1, "y": 20, "z": 30]
// a is unchanged

public mutating func modify[R](K, (V) -> R) -> R?

Mutates the value for key in place and returns the closure's result, or None (without invoking body) if the key is absent.

The interim form of in-place value access — the conditional ref-returning lookup (find(key:) -> Optional[&V]) waits for Optional[&T]. Today this is a bucket read → mutate → write-back under the hood; it can upgrade to true in-place mutation later with no API change. One probe (no re-hash on write-back, unlike update(...)); triggers COW only when the key is present.

Examples

var dict = ["a": 1];
dict.modify("a") { (mutating v) in v = v + 1 };  // .Some(())
dict.modify("z") { (mutating v) in v = v + 1 };  // .None; body not invoked
dict("a");  // Some(2)

public mutating func remove(K) -> V?

Removes key and returns its value, or None if absent.

Replaces the bucket with a .Deleted tombstone so existing probe chains stay intact. Tombstones are reclaimed by the next resize. Triggers COW only when an entry is actually removed.

Examples

var dict = ["a": 1, "b": 2];
dict.remove("a");  // Some(1); dict = ["b": 2]
dict.remove("z");  // None;    dict unchanged

public mutating func removeAll(where: consuming (K, V) -> Bool)

Removes every entry for which predicate(key, value) is true.

Inverse of retain(where:); implemented as retain over the negated predicate. Same tombstone caveat applies — consider shrinkToFit() after large removals.

Examples

var dict = ["a": 1, "b": 2, "c": 3];
dict.removeAll { (k, v) in v < 2 };  // ["b": 2, "c": 3]

public mutating func reserveCapacity(Int64)

Grows the bucket array so at least minimumCapacity entries fit without resizing.

No-op when current capacity already suffices. The actual new capacity rounds up to the next power of two and accounts for the 75% load factor (so target = nextPowerOfTwo(min * 4 / 3)). The opposite operation is shrinkToFit().

Examples

var dict = Dictionary[String, Int64]();
dict.reserveCapacity(1000);
// No reallocations for the first ~750 inserts.

public mutating func retain(where: (K, V) -> Bool)

Keeps only entries for which predicate(key, value) is true.

Two-pass implementation: collects keys to remove, then deletes them. Each removal leaves a tombstone — call shrinkToFit() afterwards if you've removed a large fraction. The mirror is removeAll(where:).

Examples

var dict = ["a": 1, "b": 2, "c": 3];
dict.retain { (k, v) in v > 1 };  // ["b": 2, "c": 3]

public mutating func shrinkToFit()

Reduces capacity to the smallest power of two that still satisfies the load factor for the current count.

Frees excess memory and reclaims tombstone space (the resize rebuilds the table without them). Empty dictionaries fall through to clear(). No-op when the table is already at the minimum acceptable capacity.

Examples

var dict = Dictionary[String, Int64](capacity: 1000);
dict("a") = 1;
dict.shrinkToFit();  // capacity drops from 1024 to 8

public func sumValues() -> V

Returns the sum of every value, starting from V() (the default-constructed zero).

Empty dictionaries return V() — for Int64 that's 0, for String that's "", etc. Linear in count.

Examples

["a": 1, "b": 2, "c": 3].sumValues();  // 6
[:].sumValues();                        // 0 — V's default

public mutating func update(K, with: (V) -> V) -> Bool

Applies transform to the existing value for key and writes the result back; returns whether the key was found.

No-op when the key is absent — for "update or insert" semantics use upsert(...). Internally re-uses insert(...), so the hash is recomputed.

Examples

var dict = ["a": 1, "b": 2];
dict.update("a") { (v) in v * 10 };  // true;  dict("a") == Some(10)
dict.update("z") { (v) in v * 10 };  // false; dict unchanged

public mutating func upsert(K, default: V, with: (V) -> V)

Inserts transform(defaultValue) for a new key, or transform(existing) for an existing one.

The classic "increment-or-set-to-1" pattern. defaultValue is passed through transform even on the insert path, so the same closure handles both branches uniformly. For the no-insert variant see update(...).

Examples

var counts: [String: Int64] = [:];
counts.upsert("apple", default: 0) { (n) in n + 1 };
counts.upsert("apple", default: 0) { (n) in n + 1 };
counts("apple");  // Some(2)

Subscripts

public subscript(K) -> V? { get set }

Reads the value for key (or None if absent), or assigns to insert/remove the entry.

The assignment form treats Some(v) as insert/update and None as delete — so dict(k) = None is the inline form of dict.remove(k). For a non-Optional getter use dict(key, default: ...) or dict(unwrap: key).

Examples

var dict = ["a": 1, "b": 2];
dict("a");           // Some(1)
dict("z");           // None
dict("c") = 3;       // inserts "c": 3
dict("a") = None;    // removes "a"

public subscript(unwrap: K) -> V { get set }

Reads or writes the value for key, panicking on the read when the key is absent.

Use when you've already verified the key exists (or when its absence indicates a bug). The setter is equivalent to insert(key, newValue) and never panics. For a non-panicking read use dict(key) or dict(key, default: ...).

Errors

Read panics with "Dictionary subscript(unwrap:): key not found" when the key is absent.

Examples

let dict = ["a": 1, "b": 2];
dict(unwrap: "a");  // 1
dict(unwrap: "z");  // PANIC: key not found

public subscript(K, default: V) -> V { get }

Reads the value for key, falling back to defaultValue when the key is absent.

Read-only and non-inserting — the default value is returned but never stored. To upsert with a default, use upsert(...) or update(...).

Examples

let dict = ["a": 1, "b": 2];
dict("a", default: 0);  // 1
dict("z", default: 0);  // 0
dict("z");              // still None — default wasn't stored

ImplementsIterable

Associated Types

type Item = (K, V)

Iterable element type — a (key, value) tuple.

type TargetIterator = DictionaryIterator[K, V]

Concrete iterator type returned by iter().

Methods

public func iter() -> DictionaryIterator[K, V]

Returns a DictionaryIterator[K, V] over the live entries.

Order is unspecified and may change between mutations. The iterator borrows the bucket array; do not mutate the dictionary while iterating. For key- or value-only iteration, use keys.iter() / values.iter().

Examples

for (k, v) in dict.iter() { ... }
let entries = Array(from: dict.iter());

ImplementsCloneable

Methods

public func clone() -> Dictionary[K, V, H]

Returns a Dictionary sharing the same storage; the deep copy is deferred until either side mutates.

O(1) — just bumps the storage RcBox's refcount. The first mutation on either side triggers makeUnique(), which deep-clones via DictionaryStorage.clone(). For an immediate deep copy use deepClone() (defined in the unconditional extension below).

Examples

let a: [String: Int64] = ["x": 1];
var b = a.clone();  // O(1), shares storage
b("y") = 2;         // b deep-copies here; a is unchanged

ImplementsEquatable

Associated Types

type Output = Bool

Methods

public func equal(to: Self) -> Bool

Bridges Equal.equal(to:) to Equatable.isEqual(to:).

public func isEqual(to: Dictionary[K, V, H]) -> Bool

Order-independent equality: dictionaries are equal iff they have the same count and every key in self is present in other with an equal value.

Short-circuits on the first mismatch. Insertion order does not matter — only the multiset of (key, value) pairs does.

Examples

["a": 1, "b": 2].isEqual(to: ["b": 2, "a": 1]);  // true
["a": 1].isEqual(to: ["a": 2]);                  // false
["a": 1].isEqual(to: [:]);                       // false

public func notEqual(to: Self) -> Bool

Default !=: delegates to == so there's a single source of truth.

ImplementsFormattable

Methods

public func format(into: mutating StringBuilder, FormatOptions)

Renders the dictionary as "{" + entries.joined(", ") + "}", passing options to each key and value's format.

Examples

["a": 1, "b": 2].format();  // "{a: 1, b: 2}"  — order unspecified
Dictionary[String, Int64]().format();  // "{}"
"\{["a": 1, "b": 2]}";      // "{a: 1, b: 2}"  via interpolation

public func formatted(FormatOptions) -> String

Returns this value rendered as a String.

Convenience wrapper: creates a StringBuilder, calls format(into:), and returns the built string. Uses a distinct name to avoid overload-resolution ambiguity with format(into:).

Implements_ExpressibleByDictionaryLiteral

Associated Types

type Key = K

Key type for the literal protocol — matches K.

type Value = V

Value type for the literal protocol — matches V.

Initializers

init(consuming lang.ptr[(Key, Value)], consuming lang.i64)

Compiler-emitted init taking a raw (Key, Value) pointer and count.

Both params are consuming for the same reason as the array bridge: the compiler hands ownership of the stack buffer to the implementation. MIR lowering matches on the unwrapped param shape, so an impl that deviates from this convention will be skipped during literal lowering.

ImplementsExpressibleByDictionaryLiteral

Initializers

init(dictionaryLiteral: LiteralSlice[(Key, Value)])

Builds an instance from a literal slice of key-value pairs.

ImplementsDefaultable

Initializers

init()

Builds the default-valued instance.

Defined in lang/std/collections/dictionary.ks