MultiMap 3.0.0

MultiMap

A .NET library providing various multimap implementations — collections that associate each generic key with one or more generic values. Includes list-based, set-based, sorted, concurrent, reader-writer locked, and async variants with set-like extension methods. Targets .NET 10, .NET 9, and .NET 8.

Table of Contents

• Overview
• Features
• Known Limitations
• Project Structure
• Interfaces
• Implementations
• Comparison Table
  • Internal Data Structures
  • API Behavior Differences
  • When to Use Which Implementation
  • Performance Comparison
• Extension Methods
• Installation
• Usage
  • Demo Console Output
• Testing
• Benchmarks
• Release Notes
• License

Overview

A multimap is a collection that maps each key to one or more values — unlike a standard Dictionary<TKey, TValue>, which allows only one value per key. This library provides 7 ready-to-use implementations behind 6 interfaces (3 mutable + 3 read-only), so you can choose the right trade-off between uniqueness, ordering, thread-safety, and async support for your scenario. It also ships with set-like extension methods (Union, Intersect, ExceptWith, SymmetricExceptWith) and set algebra query methods (IsSubsetOf, IsSupersetOf, Overlaps, SetEquals) that work across all implementations.

Features

• 7 multimap implementations covering a wide range of use cases
• 6 interfaces (3 read-only + 3 mutable): IReadOnlySimpleMultiMap, IReadOnlyMultiMap, IReadOnlyMultiMapAsync, ISimpleMultiMap, IMultiMap, IMultiMapAsync
• Multi-target: .NET 10, .NET 9, and .NET 8
• Set-like extension methods: Union, Intersect, ExceptWith, SymmetricExceptWith
• Set algebra query methods: IsSubsetOf, IsSupersetOf, Overlaps, SetEquals
• Thread-safe variants: fully lock-free (ConcurrentMultiMap), reader-writer locked (MultiMapLock), and async-safe (MultiMapAsync)
• Dispose safety: MultiMapLock and MultiMapAsync throw ObjectDisposedException after disposal
• Custom value comparers: IEqualityComparer<TValue> constructor overloads on all HashSet-based implementations
• Value-based equality (Equals/GetHashCode) across all 7 implementations
• Initial capacity constructors: Pre-size internal dictionaries to reduce re-allocations
• Full XML documentation for IntelliSense support
• Comprehensive NUnit 4 test suite:
  • 6,924 total tests (2,308 per framework) running on net10.0, net9.0, and net8.0
  • 98.4% line coverage, 96.1% branch coverage, 98% method coverage (latest combined Coverlet metrics)
  • Covers all implementations, interfaces, edge cases, boundary conditions, concurrent stress tests, cancellation-token scenarios, and exception handling
  • High code coverage measured with Coverlet (see Testing section for latest report)

Known Limitations

SortedMultiMap Value-Comparer Constraint

Design constraint: SortedMultiMap<TKey, TValue> accepts an IComparer<TValue> for sorting but requires it to also implement IEqualityComparer<TValue> for hash-code consistency.

Enforcement (v2.1.2+): Both SortedMultiMap(IComparer<TValue>?) and SortedMultiMap(IComparer<TKey>?, IComparer<TValue>?) throw ArgumentException at construction time when a non-null value comparer does not implement IEqualityComparer<TValue>. Passing null is still accepted and uses the default comparer.

Why this matters: SortedSet<TValue> uses IComparer<TValue> for ordering but GetHashCode() and Equals() rely on IEqualityComparer<TValue>. If the two interfaces were implemented inconsistently, two instances with identical content could produce different hash codes, violating the Equals/GetHashCode contract.

Recommended pattern:

// Implement both interfaces on the same comparer:
class CaseInsensitiveStringComparer : IComparer<string>, IEqualityComparer<string>
{
    public int Compare(string? x, string? y)
        => StringComparer.OrdinalIgnoreCase.Compare(x, y);
    public bool Equals(string? x, string? y)
        => StringComparer.OrdinalIgnoreCase.Equals(x, y);
    public int GetHashCode(string obj)
        => StringComparer.OrdinalIgnoreCase.GetHashCode(obj);

### ConcurrentSet.Count Staleness

`ConcurrentSet<T>.Count` (and therefore `ConcurrentMultiMap`'s value-collection count) delegates to `ConcurrentDictionary<TKey, TValue>.Count`. The BCL acquires all internal segment locks to produce a consistent snapshot, so the operation is effectively O(1) in practice, but the value can be **stale by the time it is observed** — other threads may add or remove elements between the read and any subsequent decision. Use `IsEmpty` when you only need to test for emptiness, and avoid building control-flow logic around the count in concurrent scenarios.
}

var map = new SortedMultiMap<string, string>(new CaseInsensitiveStringComparer());

If you need a value comparer that only sorts and does not participate in hashing, use MultiMapList<TKey, TValue> instead.

MultiMap/
├── MultiMap/                                 # Core library (NuGet package)
│   ├── Interfaces/
│   │   ├── IReadOnlySimpleMultiMap.cs        # Base read-only interface
│   │   ├── IReadOnlyMultiMap.cs              # Extended read-only interface
│   │   ├── IReadOnlyMultiMapAsync.cs         # Async read-only with cancellation support
│   │   ├── ISimpleMultiMap.cs                # Simplified (extends IReadOnlySimpleMultiMap)
│   │   ├── IMultiMap.cs                      # Synchronous multimap (extends IReadOnlyMultiMap)
│   │   └── IMultiMapAsync.cs                 # Async multimap (extends IReadOnlyMultiMapAsync)
│   ├── Entities/
│   │   ├── MultiMapBase.cs                   # Abstract dictionary-backed base for MultiMapList/Set/Sorted/Concurrent
│   │   ├── MultiMapBase.ValuesCollection.cs  # Nested ValuesCollection enumerator (partial)
│   │   ├── MultiMapBase.ValuesEnumerator.cs  # Nested ValuesEnumerator struct (partial)
│   │   ├── MultiMapList.cs                   # List-based (allows duplicates)
│   │   ├── MultiMapSet.cs                    # HashSet-based (unique values)
│   │   ├── SortedMultiMap.cs                 # SortedDictionary + SortedSet
│   │   ├── ConcurrentSet.cs                  # Thread-safe set value collection for ConcurrentMultiMap
│   │   ├── ConcurrentMultiMap.cs             # Nested ConcurrentDictionary, fully lock-free
│   │   ├── MultiMapLock.cs                   # ReaderWriterLockSlim-based
│   │   ├── MultiMapAsync.cs                  # SemaphoreSlim-based async (public API)
│   │   ├── MultiMapAsync.Core.cs             # SemaphoreSlim-based async (private helpers, partial)
│   │   └── SimpleMultiMap.cs                 # Lightweight ISimpleMultiMap implementation
│   └── Helpers/
│       ├── Guard.cs                          # Internal argument-validation helpers; [NotNull] applied unconditionally across all TFMs
│       ├── Polyfills.cs                      # Single home for all version-gated conditionals (HashSet<T>.AsReadOnly on .NET 10+)
│       └── MultiMapHelper.cs                 # Set-like extension methods
├── MultiMap.Tests/                           # Unit tests (NUnit 4, multi-targeted: net10.0, net9.0, and net8.0)
├── MultiMap.Demo/                            # Console demo application
│   ├── Program.cs                            # Demo entry point
│   └── TestDataHelper.cs                     # Sample data factory for demos
└── BenchmarkSuite/                           # BenchmarkDotNet performance benchmarks

Interfaces

Interface Hierarchy

The library follows a hierarchical interface design with three parallel families:

Read-Only Interfaces:

• IReadOnlySimpleMultiMap<TKey, TValue> — Base read-only interface with Get, GetOrDefault, TryGet, ContainsKey, and Contains
• IReadOnlyMultiMap<TKey, TValue> — Extends IReadOnlySimpleMultiMap with Count, KeyCount, Keys, Values, GetValuesCount, this[key], and typed enumeration
• IReadOnlyMultiMapAsync<TKey, TValue> — Async read-only with async Get-s, Contains-es, Count-s, Keys/Values accessors, and async enumeration

Mutable Interfaces:

• ISimpleMultiMap<TKey, TValue> — Extends IReadOnlySimpleMultiMap with Add, Remove, and RemoveKey (returns bool)
• IMultiMap<TKey, TValue> — Extends both IReadOnlyMultiMap<TKey, TValue> and ISimpleMultiMap<TKey, TValue> with AddRange, RemoveRange, RemoveWhere, and Clear
• IMultiMapAsync<TKey, TValue> — Extends IReadOnlyMultiMapAsync with async mutations (Add/Remove), ClearAsync, and async equality helpers (EqualsAsync overloads)

IReadOnlySimpleMultiMap<TKey, TValue>

The base read-only interface. Extends IEnumerable<KeyValuePair<TKey, TValue>> and IReadOnlyCollection<KeyValuePair<TKey,TValue>>.

Method	Returns	Description
Get(key)	IEnumerable<TValue>	Returns values; throws KeyNotFoundException if not found
GetOrDefault(key)	IEnumerable<TValue>	Returns values or empty if not found
TryGet(key, out values)	bool	Attempts to retrieve values; returns true if key exists
ContainsKey(key)	bool	Checks if a key exists
Contains(key, value)	bool	Checks if a specific key-value pair exists
Count	int	Gets the total number of key-value pairs (from IReadOnlyCollection<KeyValuePair<TKey,TValue>>)

ISimpleMultiMap<TKey, TValue>

A simplified multimap interface. Extends IReadOnlySimpleMultiMap<TKey, TValue>.

Method	Returns	Description
Add(key, value)	bool	Adds a key-value pair; returns false if already present
Remove(key, value)	bool	Removes a specific pair; returns true if removed
RemoveKey(key)	bool	Removes all values for a key; returns true when the key existed
Clear()	void	Removes all entries

Migration note: legacy ISimpleMultiMap.Clear(TKey)/void patterns were removed; use RemoveKey(TKey) and consume its bool result.

Inherited from IReadOnlySimpleMultiMap: Get, GetOrDefault, TryGet, ContainsKey, Contains, Count

IReadOnlyMultiMap<TKey, TValue>

Extended read-only interface. Extends IReadOnlySimpleMultiMap<TKey, TValue>.

Member	Returns	Description
KeyCount	int	Gets the number of unique keys
Keys	IEnumerable<TKey>	Gets all keys
Values	IEnumerable<TValue>	Gets all values across all keys
GetValuesCount(key)	int	Gets count of values for a key (0 if missing)
this[key]	IEnumerable<TValue>	Indexer — convenient value access by key
GetEnumerator()	IEnumerator<KeyValuePair>	Enumerates all key-value pairs

Inherited from IReadOnlySimpleMultiMap: Get, GetOrDefault, TryGet, ContainsKey, Contains, Count

IMultiMap<TKey, TValue>

The standard synchronous multimap interface. Extends IReadOnlyMultiMap<TKey, TValue>.

Method	Returns	Description
Add(key, value)	bool	Adds a key-value pair; returns false if already present
AddRange(key, values)	int	Adds multiple values for a key; returns count added
AddRange(items)	int	Adds multiple key-value pairs; returns count added
Remove(key, value)	bool	Removes a specific key-value pair
RemoveRange(items)	int	Removes multiple key-value pairs; returns count removed
RemoveWhere(key, predicate)	int	Removes values matching predicate; returns count removed
RemoveKey(key)	bool	Removes a key and all its values
Clear()	void	Removes all entries

Inherited from IReadOnlyMultiMap: Get, GetOrDefault, TryGet, ContainsKey, Contains, KeyCount, Count, Keys, Values, GetValuesCount, this[key]

IReadOnlyMultiMapAsync<TKey, TValue>

Asynchronous read-only multimap interface. Extends IAsyncEnumerable<KeyValuePair<TKey, TValue>>, IDisposable, and IAsyncDisposable. All methods support CancellationToken.

Method	Returns	Description
GetAsync(key)	ValueTask<IEnumerable<TValue>>	Retrieves values; throws KeyNotFoundException if not found
GetOrDefaultAsync(key)	ValueTask<IEnumerable<TValue>>	Retrieves values or empty if not found
TryGetAsync(key)	ValueTask<(bool, IEnumerable<TValue>)>	Attempts to retrieve values; returns tuple with found status and values
ContainsKeyAsync(key)	ValueTask<bool>	Checks for a key
ContainsAsync(key, value)	ValueTask<bool>	Checks for a pair
GetCountAsync()	ValueTask<int>	Gets total count of key-value pairs
GetKeyCountAsync()	ValueTask<int>	Gets number of keys
GetKeysAsync()	ValueTask<IEnumerable<TKey>>	Gets all keys
GetValuesCountAsync(key)	ValueTask<int>	Gets count of values for a key
GetValuesAsync()	ValueTask<IEnumerable<TValue>>	Gets all values across all keys

IMultiMapAsync<TKey, TValue>

Asynchronous multimap interface. Extends IReadOnlyMultiMapAsync<TKey, TValue>. All methods support CancellationToken and return ValueTask or Task.

Method	Returns	Description
AddAsync(key, value)	ValueTask<bool>	Asynchronously adds a key-value pair
AddRangeAsync(key, values)	ValueTask<int>	Asynchronously adds multiple values; returns count added
AddRangeAsync(items)	ValueTask<int>	Asynchronously adds multiple key-value pairs; returns count added
RemoveAsync(key, value)	ValueTask<bool>	Asynchronously removes a pair
RemoveRangeAsync(items)	ValueTask<int>	Asynchronously removes multiple pairs; returns count removed
RemoveWhereAsync(key, predicate)	ValueTask<int>	Asynchronously removes values matching predicate; returns count removed
RemoveKeyAsync(key)	ValueTask<bool>	Asynchronously removes a key
ClearAsync()	Task	Asynchronously clears all entries

Inherited from IReadOnlyMultiMapAsync: GetAsync, GetOrDefaultAsync, TryGetAsync, ContainsKeyAsync, ContainsAsync, GetCountAsync, GetKeyCountAsync, GetKeysAsync, GetValuesCountAsync, GetValuesAsync

Implementations

MultiMapBase<TKey, TValue, TCollection> — Abstract Base Class

Provides the shared dictionary-backed implementation inherited by MultiMapList, MultiMapSet, SortedMultiMap, and ConcurrentMultiMap. Implements IMultiMap<TKey, TValue> with Add, AddRange, Remove, RemoveKey, RemoveRange, RemoveWhere, Get, GetOrDefault, TryGet, ContainsKey, Contains, Count, KeyCount, Keys, Values, GetValuesCount, indexer, Clear, and GetEnumerator. Subclasses override protected CreateCollection(), TryGetCollection, AddToCollection(), ToReadOnly, and RemoveWhereFromCollection() to plug in their specific collection type. MultiMapList and MultiMapSet also override Add/AddRange to use CollectionsMarshal.GetValueRefOrAddDefault for a single dictionary lookup per operation.

Encapsulation: The underlying _dictionary field is protected. The value counter _count is private; subclasses mutate it exclusively through protected helpers: IncrementCount(), DecrementCount(int by = 1), ResetCount() (non-atomic), and InterlockedIncrementCount(), InterlockedAddCount(int by), InterlockedExchangeCount(int value), VolatileReadCount() (atomic, used by ConcurrentMultiMap). This prevents any subclass from silently corrupting the Count == total mapped values invariant.

MultiMapList<TKey, TValue> — List-Based

Extends MultiMapBase<TKey, TValue, List<TValue>>. Uses Dictionary<TKey, List<TValue>> internally. Allows duplicate values per key. Fastest for add operations due to List<T>.Add being O(1) amortized. Uses CollectionsMarshal for a single dictionary lookup per Add/AddRange operation. Returns a zero-copy ReadOnlyCollection<TValue> from Get.

Constructors: (), (int capacity), (IEqualityComparer<TKey>? keyComparer), (int capacity, IEqualityComparer<TKey>? keyComparer)

MultiMapSet<TKey, TValue> — HashSet-Based

Extends MultiMapBase<TKey, TValue, HashSet<TValue>>. Uses Dictionary<TKey, HashSet<TValue>> internally. Ensures unique values per key. Best for scenarios that require fast lookups and unique-value semantics. Uses CollectionsMarshal for a single dictionary lookup per Add/AddRange operation. On .NET 10+, Get/GetOrDefault/TryGet return a zero-copy ReadOnlySet<TValue> view instead of an array snapshot.

Constructors: (), (IEqualityComparer<TKey>? keyComparer), (IEqualityComparer<TValue>? valueComparer), (int capacity), (int capacity, IEqualityComparer<TKey>? keyComparer), (int capacity, IEqualityComparer<TValue>? valueComparer), (int capacity, IEqualityComparer<TKey>? keyComparer, IEqualityComparer<TValue>? valueComparer)

SortedMultiMap<TKey, TValue> — Sorted

Extends MultiMapBase<TKey, TValue, SortedSet<TValue>>. Uses SortedDictionary<TKey, SortedSet<TValue>>. Keys and values are maintained in sorted order. Ideal for ordered enumeration and range queries.

Type constraints: TKey must implement IComparable<TKey> (required by SortedMultiMap for sorted key ordering). The actual sorted operations rely on IComparer<TKey> — either the default comparer or a custom one supplied via a constructor overload. TValue similarly requires IComparable<TValue> (for SortedSet<TValue> ordering). Unlike all other multimap types, SortedMultiMap does not accept a custom equality comparer because SortedSet<T> derives equality from the comparer.

Constructors: (), (IComparer<TKey>? keyComparer), (IComparer<TValue>? valueComparer), (IComparer<TKey>? keyComparer, IComparer<TValue>? valueComparer)

ConcurrentMultiMap<TKey, TValue> — Fully Lock-Free Concurrent

Extends MultiMapBase<TKey, TValue, ConcurrentSet<TValue>>. Uses ConcurrentDictionary<TKey, ConcurrentSet<TValue>> for fully lock-free concurrent access — no explicit locks are held for per-key operations. Count and KeyCount are O(1), backed by _count and _keyCount fields maintained via Interlocked in every mutating path. Keys and Values are lazy iterators that yield directly from the live dictionary (call .ToList() / .ToArray() when a stable snapshot is needed). Suitable for high-concurrency scenarios.

Note: ConcurrentMultiMap does not implement IDisposable. Unlike MultiMapLock (which disposes a ReaderWriterLockSlim) and MultiMapAsync (which disposes two SemaphoreSlim instances), ConcurrentMultiMap owns no disposable resources — the underlying ConcurrentDictionary requires no explicit cleanup.

Note: ConcurrentSet<T>.Count (used internally per key) delegates to ConcurrentDictionary.Count, which acquires all internal segment locks. The value is effectively O(1) but may be stale by the time it is read in concurrent scenarios. Use IsEmpty when testing for emptiness.

Constructors: (), (IEqualityComparer<TKey>? keyComparer), (IEqualityComparer<TKey>? keyComparer, IEqualityComparer<TValue>? valueComparer), (IEqualityComparer<TValue>? valueComparer), (int concurrencyLevel, int capacity), (int concurrencyLevel, int capacity, IEqualityComparer<TKey>? keyComparer), (int concurrencyLevel, int capacity, IEqualityComparer<TValue>? valueComparer), (int concurrencyLevel, int capacity, IEqualityComparer<TKey>? keyComparer, IEqualityComparer<TValue>? valueComparer)

MultiMapLock<TKey, TValue> — Reader-Writer Locked

Implements IMultiMap and IDisposable. Uses ReaderWriterLockSlim to allow concurrent reads with exclusive writes. Good for read-heavy workloads with occasional writes.

Cancellable write operations: ReaderWriterLockSlim.EnterWriteLock() blocks indefinitely with no cancellation path. Every write method (Add, AddRange, Remove, RemoveRange, RemoveWhere, RemoveKey, Clear, Union, Intersect, ExceptWith, SymmetricExceptWith) has a CancellationToken overload that polls with TryEnterWriteLock(20 ms) in a loop and calls cancellationToken.ThrowIfCancellationRequested() between attempts. Cancellation latency is at most ~20 ms; if the token fires after the lock is acquired, the mutation completes normally (the token is only checked while waiting).

Constructors: (), (IEqualityComparer<TKey>? keyComparer), (IEqualityComparer<TValue>? valueComparer), (int capacity), (int capacity, IEqualityComparer<TKey>? keyComparer), (int capacity, IEqualityComparer<TValue>? valueComparer), (int capacity, IEqualityComparer<TKey>? keyComparer, IEqualityComparer<TValue>? valueComparer)

MultiMapAsync<TKey, TValue> — Async-Safe

Implements IMultiMapAsync, IDisposable, and IAsyncDisposable. Uses SemaphoreSlim for async-compatible mutual exclusion. Designed for async/await patterns and I/O-bound scenarios. Equals(IReadOnlyMultiMapAsync<TKey, TValue>?) uses a deadlock-safe dual-semaphore acquisition when comparing two MultiMapAsync instances; Equals(object?) throws InvalidOperationException under a SynchronizationContext — use EqualsAsync in async contexts instead.

Locking protocol: Two SemaphoreSlim(1,1) instances implement a custom readers-writer protocol with writer preference. _writeLock is held exclusively by every mutating operation and by the first reader for as long as any reader is active. _readerLock guards the _activeReaders counter and is held only for the brief increment/decrement critical section. Key invariants: (1) a writer blocks until _activeReaders reaches 0 and _writeLock is released by the last reader; (2) the first reader blocks if a writer currently holds _writeLock; (3) every operation has a non-blocking fast path (Wait(0)) that avoids a heap-allocated continuation when there is no contention.

Writer preference: A _pendingWriters counter is incremented (via Interlocked) by every writer before it calls _writeLock.WaitAsync and decremented once the lock is acquired. All three read-entry paths (TryEnterReadLockSync, EnterReadLockSync, EnterReadLockAsync) check this counter and back off — retrying after the current writer finishes — when it is non-zero. This prevents writer starvation under sustained high-frequency concurrent reads.

Note: The primary constructor is MultiMapAsync(int capacity, IEqualityComparer<TKey>? keyComparer, IEqualityComparer<TValue>? valueComparer); all other constructor overloads delegate to it.

Constructors: (), (IEqualityComparer<TKey>? keyComparer), (IEqualityComparer<TValue>? valueComparer), (int capacity), (int capacity, IEqualityComparer<TKey>? keyComparer), (int capacity, IEqualityComparer<TValue>? valueComparer), (int capacity, IEqualityComparer<TKey>? keyComparer, IEqualityComparer<TValue>? valueComparer)

SimpleMultiMap<TKey, TValue> — Lightweight ⚠️ Deprecated

Deprecated — SimpleMultiMap<TKey, TValue> is marked [Obsolete] and may be removed in a future major version. Use MultiMapSet<TKey, TValue> instead; it provides the same set-based, no-duplicate semantics while implementing the richer IMultiMap contract (including AddRange, RemoveRange, RemoveWhere, KeyCount, and all extension methods).

Implements ISimpleMultiMap. A lightweight, standalone multimap with a simplified API. Provides typed Equals(IReadOnlySimpleMultiMap<TKey, TValue>?) comparing total pair count then per-key value-set contents.

Constructors:

Comparison Table

Implementation	Interface	Thread-Safe	Duplicates	Ordered	Count Complexity
SimpleMultiMap	ISimpleMultiMap	❌ No	❌ No	❌ No	O(1)
MultiMapList	IMultiMap	❌ No	✅ Yes	❌ No	O(1)
MultiMapSet	IMultiMap	❌ No	❌ No	❌ No	O(1)
SortedMultiMap	IMultiMap	❌ No	❌ No	✅ Yes	O(1)
ConcurrentMultiMap	IMultiMap	✅ Lock-free	❌ No	❌ No	O(1)
MultiMapLock	IMultiMap	✅ RW Lock	❌ No	❌ No	O(1)
MultiMapAsync	IMultiMapAsync	✅ Semaphore	❌ No	❌ No	O(1)

Internal Data Structures

Implementation	Outer Structure	Inner Structure	Notes
SimpleMultiMap	Dictionary<TKey, HashSet<TValue>>	HashSet<TValue>	Simplified API surface
MultiMapList	Dictionary<TKey, List<TValue>>	List<TValue>	O(1) amortized add; allows duplicate values
MultiMapSet	Dictionary<TKey, HashSet<TValue>>	HashSet<TValue>	O(1) add/contains; enforces unique values
SortedMultiMap	SortedDictionary<TKey, SortedSet<TValue>>	SortedSet<TValue>	O(log n) operations; keys & values sorted
ConcurrentMultiMap	ConcurrentDictionary<TKey, ConcurrentSet<TValue>>	ConcurrentSet<TValue>	Fully lock-free via nested ConcurrentDictionary; Count and KeyCount are O(1) via Interlocked-maintained counters
MultiMapLock	Dictionary<TKey, HashSet<TValue>>	HashSet<TValue>	Protected by ReaderWriterLockSlim
MultiMapAsync	Dictionary<TKey, HashSet<TValue>>	HashSet<TValue>	Protected by a custom readers-writer protocol over two SemaphoreSlim(1,1) instances (_writeLock + _readerLock)

API Behavior Differences

Behavior	IMultiMap	IMultiMapAsync	ISimpleMultiMap
Interface Hierarchy	✅ Extends IReadOnlyMultiMap → IReadOnlySimpleMultiMap	✅ Extends IReadOnlyMultiMapAsync	✅ Extends IReadOnlySimpleMultiMap
Get (missing key)	✅ Get throws KeyNotFoundException; GetOrDefault returns empty	✅ GetAsync throws KeyNotFoundException; GetOrDefaultAsync returns empty	✅ Get throws KeyNotFoundException; GetOrDefault returns empty
TryGet (missing key)	✅ TryGet returns false with empty collection	✅ TryGetAsync returns (false, empty) tuple	✅ TryGet returns false with empty collection
KeyCount property	✅ KeyCount property (number of unique keys)	✅ GetKeyCountAsync() method	❌ Not available
Add (duplicate)	✅ Returns false	✅ Returns false (via ValueTask<bool>)	✅ Returns false
AddRange	✅ AddRange(key, values) and AddRange(items)	✅ AddRangeAsync(key, values) and AddRangeAsync(items)	❌ Not available
Remove return type	✅ bool	✅ ValueTask<bool>	✅ bool
RemoveRange	✅ RemoveRange(items) returns int	✅ RemoveRangeAsync(items) returns ValueTask<int>	❌ Not available
RemoveWhere	✅ RemoveWhere(key, predicate) returns int	✅ RemoveWhereAsync(key, predicate) returns ValueTask<int>	❌ Not available
GetValuesCount	✅ GetValuesCount(key) returns int	✅ GetValuesCountAsync(key) returns ValueTask<int>	❌ Not available
Enumeration	✅ IEnumerable<KeyValuePair>	✅ IAsyncEnumerable<KeyValuePair>	✅ IEnumerable<KeyValuePair>
Disposable	⚠️ Only MultiMapLock	✅ Yes (IAsyncDisposable + IDisposable)	❌ No
CancellationToken	❌ No	✅ Yes (all methods)	❌ No

When to Use Which Implementation

Use Case	Recommended Implementation	Reason
Minimal API, quick prototyping (deprecated)	SimpleMultiMap → MultiMapSet	SimpleMultiMap is obsolete; MultiMapSet covers the same use case with a richer API
General purpose, unique values	MultiMapSet	Fast O(1) lookups with uniqueness guarantee
Duplicate values needed	MultiMapList	Only implementation allowing duplicate values per key
Sorted enumeration / range queries	SortedMultiMap	Maintains key and value ordering
High-concurrency, many threads	ConcurrentMultiMap	Fully lock-free via nested ConcurrentDictionary; no contention under concurrent reads/writes
Read-heavy, occasional writes	MultiMapLock	RW lock allows concurrent readers
Async / I/O-bound code	MultiMapAsync	SemaphoreSlim works with async/await

Performance Comparison (5,000 pairs)

Implementation	Add	Get (100 keys)	Contains	Count	Relative Add Speed
MultiMapList	46,949 ns	9,157 ns	35 ns	< 1 ns	1.0x (baseline)
SimpleMultiMap	81,557 ns	12,013 ns	5 ns	< 1 ns	1.7x
MultiMapSet	81,379 ns	12,909 ns	41 ns	< 1 ns	1.7x
MultiMapLock	123,190 ns	12,439 ns	15 ns	11 ns	2.6x
MultiMapAsync	185,584 ns	18,283 ns	82 ns	80 ns	4.0x
ConcurrentMultiMap	202,077 ns	54,536 ns	186 ns	< 1 ns	4.3x
SortedMultiMap	845,301 ns	37,745 ns	34 ns	< 1 ns	18.0x

Note: Performance data from BenchmarkDotNet (latest run on .NET 10.0.8 / SDK 10.0.300). See Benchmarks for full details.

Extension Methods

For all 3 interface families, the MultiMapHelper provides:

1. Set-like operations as extension methods:

Family	Methods	Current signatures
ISimpleMultiMap<TKey, TValue>	Union, Intersect, ExceptWith, SymmetricExceptWith	this ISimpleMultiMap<TKey,TValue> target, ISimpleMultiMap<TKey,TValue> other → returns ISimpleMultiMap<TKey,TValue>
IMultiMap<TKey, TValue>	Union, Intersect, ExceptWith, SymmetricExceptWith	this IMultiMap<TKey,TValue> target, IReadOnlyMultiMap<TKey,TValue> other → returns IMultiMap<TKey,TValue>
IMultiMapAsync<TKey, TValue>	UnionAsync, IntersectAsync, ExceptWithAsync, SymmetricExceptWithAsync	this IMultiMapAsync<TKey,TValue> target, IReadOnlyMultiMapAsync<TKey,TValue> other, CancellationToken cancellationToken = default → returns Task

These signatures mutate and return the sync target map for fluent usage, while async extensions complete via Task and support CancellationToken.

2. Set algebra query operations as extension methods:

Family	Methods	Current signatures
ISimpleMultiMap<TKey, TValue>	IsSubsetOf, IsSupersetOf, Overlaps, SetEquals	this ISimpleMultiMap<TKey,TValue> target, ISimpleMultiMap<TKey,TValue> other → returns bool
IMultiMap<TKey, TValue>	IsSubsetOf, IsSupersetOf, Overlaps, SetEquals	this IMultiMap<TKey,TValue> target, IMultiMap<TKey,TValue> other → returns bool
IMultiMapAsync<TKey, TValue>	IsSubsetOfAsync, IsSupersetOfAsync, OverlapsAsync, SetEqualsAsync	this IMultiMapAsync<TKey,TValue> target, IMultiMapAsync<TKey,TValue> other, CancellationToken cancellationToken = default → returns Task<bool>

These signatures return bool, while async extensions complete via Task<bool> and support CancellationToken.

Note: When used with concurrent implementations, these methods are not atomic. Individual operations are thread-safe, but the overall result may reflect interleaved concurrent modifications. No structural corruption or count drift will occur.

Async cancellation behaviour: Every IMultiMapAsync overload accepts a CancellationToken that is forwarded to each individual IMultiMapAsync call it makes (GetKeysAsync, GetOrDefaultAsync, AddRangeAsync, etc.). Cancellation is therefore observed at every await boundary, not only between top-level iterations. For mutating operations (UnionAsync, IntersectAsync, ExceptWithAsync, SymmetricExceptWithAsync) already-applied changes are not rolled back on cancellation — the method throws OperationCanceledException and leaves target in a partially modified state. Read-only operations (IsSubsetOfAsync, IsSupersetOfAsync, OverlapsAsync, SetEqualsAsync) require no rollback. OverlapsAsync returns early as soon as a shared pair is found, limiting the number of async calls made before a potential cancellation check.

Performance notes for set-like helpers: Intersect and SymmetricExceptWith build a per-key HashSet<TValue> lookup to avoid O(n²) inner-loop scans. When the per-key value collection already implements ISet<TValue> (for example, when the underlying map is a MultiMapSet), the existing set is used directly, and no allocation occurs. ExceptWith and Union iterate directly without any temporary collection. GetHashCode() on all concrete implementations uses the key and value equality comparers stored by that instance, so hash codes remain consistent with the equality semantics used by the map — custom comparers are fully respected.

Installation

NuGet

dotnet add package MultiMap

Package Reference

<PackageReference Include="MultiMap" Version="2.1.0" />

Usage

Basic Usage with IMultiMap

using MultiMap.Entities;

// HashSet-based (unique values per key)
var map = new MultiMapSet<string, int>();
map.Add("fruits", 1);
map.Add("fruits", 2);
map.Add("fruits", 1); // returns false — already exists
map.AddRange("vegetables", [10, 20, 30]);

IEnumerable<int> values = map.Get("fruits");   // [1, 2]
bool exists = map.Contains("fruits", 1);       // true
int count = map.Count;                         // 5

map.Remove("fruits", 1);
map.RemoveKey("vegetables");

Advanced Usage — New Interface Members

Working with KeyCount and Values

using MultiMap.Entities;

var map = new MultiMapSet<string, int>();
map.Add("A", 1);
map.Add("A", 2);
map.Add("B", 3);

// KeyCount returns the number of unique keys (not total pairs)
int keyCount = map.KeyCount;        // 2 (keys: "A", "B")
int totalCount = map.Count;         // 3 (pairs: A→1, A→2, B→3)

// Values property returns all values across all keys
IEnumerable<int> allValues = map.Values;  // [1, 2, 3]

// GetValuesCount returns the count for a specific key
int valuesForA = map.GetValuesCount("A");  // 2
int valuesForB = map.GetValuesCount("B");  // 1
int noKey = map.GetValuesCount("C");       // 0 (key doesn't exist)

// Indexer provides convenient access to values
IEnumerable<int> aValues = map["A"];  // [1, 2]

Bulk Operations with AddRange and RemoveRange

using MultiMap.Entities;

var map = new MultiMapSet<string, int>();

// AddRange with key-value pairs collection
var items = new[]
{
    new KeyValuePair<string, int>("A", 1),
    new KeyValuePair<string, int>("A", 2),
    new KeyValuePair<string, int>("B", 3)
};
map.AddRange(items);

// RemoveRange returns the count of actually removed pairs
var toRemove = new[]
{
    new KeyValuePair<string, int>("A", 1),
    new KeyValuePair<string, int>("C", 99)  // doesn't exist
};
int removedCount = map.RemoveRange(toRemove);  // Returns 1 (only A→1 was removed)

Conditional Removal with RemoveWhere

using MultiMap.Entities;

var map = new MultiMapSet<string, int>();
map.AddRange("numbers", [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);

// Remove all even numbers for the key "numbers"
int removed = map.RemoveWhere("numbers", n => n % 2 == 0);
Console.WriteLine($"Removed {removed} even numbers");  // "Removed 5 even numbers"

// map["numbers"] now contains: [1, 3, 5, 7, 9]

Retrieval Pattern Options

using MultiMap.Entities;

var map = new MultiMapSet<string, int>();
map.Add("A", 1);

// Pattern 1: Get (throws on missing key)
try
{
    var values = map.Get("B");
}
catch (KeyNotFoundException)
{
    Console.WriteLine("Key not found!");
}

// Pattern 2: GetOrDefault (returns empty on missing key)
var safe = map.GetOrDefault("B");  // Returns empty collection

// Pattern 3: TryGet (boolean pattern)
if (map.TryGet("A", out var result))
{
    Console.WriteLine($"Found {result.Count()} values");
}
else
{
    Console.WriteLine("Key not found");
}

Concurrent Usage

using MultiMap.Entities;

var concurrentMap = new ConcurrentMultiMap<string, int>();

// Safe to call from multiple threads
Parallel.For(0, 1000, i =>
{
    concurrentMap.Add("key", i);
});

// KeyCount is O(1) with thread-safe reads
int keys = concurrentMap.KeyCount;
int total = concurrentMap.Count;

Async Usage

using MultiMap.Entities;

using var asyncMap = new MultiMapAsync<string, int>();
await asyncMap.AddAsync("key", 1);
await asyncMap.AddAsync("key", 2);

var values = await asyncMap.GetAsync("key");              // [1, 2]
var count = await asyncMap.GetCountAsync();               // 2
bool contains = await asyncMap.ContainsAsync("key", 1);   // true

Advanced Async Operations

using MultiMap.Entities;

using var map = new MultiMapAsync<string, int>();

// Bulk add with AddRangeAsync
var items = new[]
{
    new KeyValuePair<string, int>("A", 1),
    new KeyValuePair<string, int>("A", 2),
    new KeyValuePair<string, int>("B", 3)
};
await map.AddRangeAsync(items);

// Get key and value counts
int keyCount = await map.GetKeyCountAsync();       // 2
int totalCount = await map.GetCountAsync();        // 3
int aValues = await map.GetValuesCountAsync("A");  // 2

// Bulk remove with RemoveRangeAsync
var toRemove = new[]
{
    new KeyValuePair<string, int>("A", 1),
    new KeyValuePair<string, int>("B", 3)
};
int removed = await map.RemoveRangeAsync(toRemove);  // Returns 2

// Conditional removal with RemoveWhereAsync
await map.AddRangeAsync("numbers", [1, 2, 3, 4, 5, 6]);
int removedCount = await map.RemoveWhereAsync("numbers", n => n > 3);
// Removed values: 4, 5, 6

// TryGetAsync pattern
var (found, values) = await map.TryGetAsync("A");
if (found)
{
    Console.WriteLine($"Found {values.Count()} values");
}

// All methods support CancellationToken
using var cts = new CancellationTokenSource();
await map.AddAsync("key", 100, cts.Token);

Set Operations

using MultiMap.Entities;
using MultiMap.Helpers;

var map1 = new MultiMapSet<string, int>();
map1.Add("A", 1);
map1.Add("A", 2);
map1.Add("B", 3);

var map2 = new MultiMapSet<string, int>();
map2.Add("A", 2);
map2.Add("A", 3);
map2.Add("C", 4);

map1 = map1.Union(map2);                // Union: adds all pairs from map2 into map1
map1 = map1.Intersect(map2);            // Intersect: keeps only pairs present in both
map1 = map1.ExceptWith(map2);           // ExceptWith: removes pairs that exist in map2
map1 = map1.SymmetricExceptWith(map2);  // SymmetricExceptWith: keeps only pairs in one but not both

// Read-only set query operations (extension methods):
bool isSubset = MultiMapHelper.IsSubsetOf(map1, map2);      // Check if map1 ⊆ map2
bool isSuperset = MultiMapHelper.IsSupersetOf(map1, map2);  // Check if map1 ⊇ map2
bool overlaps = MultiMapHelper.Overlaps(map1, map2);        // Check if they share any pairs
bool equals = MultiMapHelper.SetEquals(map1, map2);         // Check if they contain the same pairs

// Atomic set operations and set query methods for MultiMapLock:
var lockMap1 = new MultiMapLock<string, int>();
lockMap1.Add("A", 1);
lockMap1.Add("A", 2);
lockMap1.Add("B", 3);

var lockMap2 = new MultiMapLock<string, int>();
lockMap2.Add("A", 2);
lockMap2.Add("A", 3);
lockMap2.Add("C", 4);

lockMap1.Union(lockMap2);               // Union: adds all pairs from lockMap2 into lockMap1
lockMap1.Intersect(lockMap2);           // Intersect: keeps only pairs present in both
lockMap1.ExceptWith(lockMap2);          // ExceptWith: removes pairs that exist in lockMap2
lockMap1.SymmetricExceptWith(lockMap2); // SymmetricExceptWith: keeps only pairs in one but not both

bool isSubsetLock = lockMap1.IsSubsetOf(lockMap2);      // Check if lockMap1 ⊆ lockMap2
bool isSupersetLock = lockMap1.IsSupersetOf(lockMap2);  // Check if lockMap1 ⊇ lockMap2
bool overlapsLock = lockMap1.Overlaps(lockMap2);        // Check if they share any pairs
bool equalsLock = lockMap1.SetEquals(lockMap2);         // Check if they contain the same pairs

// Atomic set operations and set query methods for MultiMapAsync:
var asyncMap1 = new MultiMapAsync<string, int>();
await asyncMap1.AddAsync("A", 1);
await asyncMap1.AddAsync("A", 2);
await asyncMap1.AddAsync("B", 3);

var asyncMap2 = new MultiMapAsync<string, int>();
await asyncMap2.AddAsync("A", 2);
await asyncMap2.AddAsync("A", 3);
await asyncMap2.AddAsync("C", 4);

await asyncMap1.UnionAsync(asyncMap2);                  // Union: adds all pairs from asyncMap2 into asyncMap1
await asyncMap1.IntersectAsync(asyncMap2);              // Intersect: keeps only pairs present in both
await asyncMap1.ExceptWithAsync(asyncMap2);             // ExceptWith: removes pairs that exist in asyncMap2
await asyncMap1.SymmetricExceptWithAsync(asyncMap2);    // SymmetricExceptWith: keeps only pairs in one but not both

bool isSubsetAsync = await asyncMap1.IsSubsetOfAsync(asyncMap2);        // Check if asyncMap1 ⊆ asyncMap2
bool isSupersetAsync = await asyncMap1.IsSupersetOfAsync(asyncMap2);    // Check if asyncMap1 ⊇ asyncMap2
bool overlapsAsync = await asyncMap1.OverlapsAsync(asyncMap2);          // Check if they share any pairs
bool equalsAsync = await asyncMap1.SetEqualsAsync(asyncMap2);           // Check if they contain the same pairs

SimpleMultiMap with Demo

using MultiMap.Entities;
using MultiMap.Helpers;

ISimpleMultiMap<string, int> map = new SimpleMultiMap<string, int>();
map.Add("A", 1);
map.Add("A", 2);

var values = map.Get("A");                                      // [1, 2]
var safe = map.GetOrDefault("missing");                         // empty
bool tryGetA = map.TryGet("A", out var values);                 // true; values = [1, 2]
bool tryGetMissing = map.TryGet("missing", out var values);     // false; values = empty

// Enumerate directly — ISimpleMultiMap implements IEnumerable<KeyValuePair<TKey, TValue>>
foreach (var kvp in map) { /* ... */ }  // replaces map.Flatten()

// Set operations return the modified map
ISimpleMultiMap<string, int> union = map.Union(otherMap);
ISimpleMultiMap<string, int> intersection = map.Intersect(otherMap);
ISimpleMultiMap<string, int> exceptWith = map.ExceptWith(otherMap);
ISimpleMultiMap<string, int> symmetricExceptWith = map.SymmetricExceptWith(otherMap);

// Set query operations return bool
bool isSubsetOf = map.IsSubsetOf(otherMap);
bool isSupersetOf = map.IsSupersetOf(otherMap);
bool overlaps = map.Overlaps(otherMap);
bool setEquals = map.SetEquals(otherMap);

Demo Console Output

The MultiMap.Demo console project demonstrates set operations (Union, Intersect, ExceptWith, SymmetricExceptWith, IsSubsetOf, IsSupersetOf, Overlaps, SetEquals) on ISimpleMultiMap instances and prints their results to the console.

Run it with:

dotnet run --project MultiMap.Demo

--wait flag

Pass --wait to keep the console window open after all output has been printed — useful when launching from an IDE or a terminal that closes immediately on exit:

dotnet run --project MultiMap.Demo -- --wait

The process blocks on Console.ReadLine() until you press Enter.

Testing

See Testing for the full unit test details.

Benchmarks

See Benchmarks for the full benchmark details.

Migration Guide

See Migration Guide for the full migration guide.

Release Notes

See Release Notes for the full version history.

License

This project is licensed under the MIT License.

See LICENSE for details.

Author

TigoS — GitHub