MultiMap 1.0.2

MultiMap

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

Table of Contents

• Overview
• Features
• 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
  • Test Coverage by Implementation
  • Test Coverage by Extension Methods
  • Test Categories
  • Test Coverage Percentage
• Benchmarks
• 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 3 interfaces, 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) that work across all implementations.

Features

• 7 multimap implementations covering a wide range of use cases
• 3 interfaces (IMultiMap, IMultiMapAsync, ISimpleMultiMap) for flexibility
• Set-like extension methods: Union, Intersect, ExceptWith, SymmetricExceptWith
• Thread-safe variants: lock-free (ConcurrentMultiMap), reader-writer locked (MultiMapLock), and async-safe (MultiMapAsync)
• Full XML documentation for IntelliSense support
• 574 unit tests with NUnit 4

Project Structure

MultiMap/
├── MultiMap/                    # Core library (NuGet package)
│   ├── Interfaces/
│   │   ├── IMultiMap.cs         # Synchronous multimap interface
│   │   ├── IMultiMapAsync.cs    # Asynchronous multimap interface
│   │   └── ISimpleMultiMap.cs   # Simplified multimap interface
│   ├── Entities/
│   │   ├── MultiMapList.cs      # List-based (allows duplicates)
│   │   ├── MultiMapSet.cs       # HashSet-based (unique values)
│   │   ├── SortedMultiMap.cs    # SortedDictionary + SortedSet
│   │   ├── ConcurrentMultiMap.cs# Lock-free ConcurrentDictionary-based
│   │   ├── MultiMapLock.cs      # ReaderWriterLockSlim-based
│   │   ├── MultiMapAsync.cs     # SemaphoreSlim-based async
│   │   └── SimpleMultiMap.cs    # Lightweight ISimpleMultiMap impl
│   └── Helpers/
│       ├── MultiMapHelper.cs    # Set-like extension methods
│       └── TestDataHelper.cs    # Sample data factory for demos
├── MultiMap.Tests/              # Unit tests (NUnit 4, 574 tests)
├── MultiMap.Demo/               # Console demo application
└── BenchmarkSuite/              # BenchmarkDotNet performance benchmarks

Interfaces

IMultiMap<TKey, TValue>

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

IMultiMapAsync<TKey, TValue>

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

ISimpleMultiMap<TKey, TValue>

A simplified multimap interface. Extends IEnumerable<KeyValuePair<TKey, TValue>>.

Implementations

MultiMapList<TKey, TValue> — List-Based

Implements IMultiMap. Uses Dictionary<TKey, List<TValue>> internally. Allows duplicate values per key. Fastest for add operations due to List<T>.Add being O(1) amortized.

MultiMapSet<TKey, TValue> — HashSet-Based

Implements IMultiMap. Uses Dictionary<TKey, HashSet<TValue>> internally. Ensures unique values per key. Best for scenarios requiring fast lookups and unique value semantics.

SortedMultiMap<TKey, TValue> — Sorted

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

ConcurrentMultiMap<TKey, TValue> — Lock-Free Concurrent

Implements IMultiMap. Uses ConcurrentDictionary<TKey, ConcurrentDictionary<TValue, byte>> for lock-free thread safety. Suitable for high-concurrency scenarios. Note: Count is computed dynamically by iterating all keys (O(k) complexity).

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.

MultiMapAsync<TKey, TValue> — Async-Safe

Implements IMultiMapAsync and IAsyncEnumerable. Uses SemaphoreSlim for async-compatible mutual exclusion. Designed for async/await patterns and I/O-bound scenarios.

SimpleMultiMap<TKey, TValue> — Lightweight

Implements ISimpleMultiMap. A lightweight multimap with a simplified API. Get throws KeyNotFoundException if the key doesn't exist, while GetOrDefault returns an empty collection.

Comparison Table

Internal Data Structures

API Behavior Differences

When to Use Which Implementation

Performance Comparison (5,000 pairs)

Note: Performance data from BenchmarkDotNet. See Benchmarks for full details.

Extension Methods

MultiMapHelper provides set-like operations as extension methods for all three interface families:

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.

Installation

NuGet

dotnet add package MultiMap

Package Reference

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

Usage

Basic Usage with IMultiMap

using MultiMap.Entities;
using MultiMap.Helpers;

// 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");

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);
});

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

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);

// Union: adds all pairs from map2 into map1
map1.Union(map2);

// Intersect: keeps only pairs present in both
map1.Intersect(map2);

// ExceptWith: removes pairs that exist in map2
map1.ExceptWith(map2);

// SymmetricExceptWith: keeps only pairs in one but not both
map1.SymmetricExceptWith(map2);

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
var flat = map.Flatten();               // all key-value pairs

// Set operations return the modified map
map = map.Union(otherMap);
map = map.Intersect(otherMap);
map = map.ExceptWith(otherMap);
map = map.SymmetricExceptWith(otherMap);

Demo Console Output

Running MultiMap.Demo produces the following output:

MULTI MAP 1:
A: 1
A: 2
B: 3

MULTI MAP 2:
A: 1
A: 3
C: 4
C: 3

UNION:
A: 1
A: 2
A: 3
B: 3
C: 4
C: 3

INTERSECT:
A: 1

EXCEPT WITH 1:
A: 2
B: 3

EXCEPT WITH 2:
A: 3
C: 4
C: 3

SYMMETRIC EXCEPT WITH:
A: 3
A: 2
B: 3
C: 4
C: 3

Testing

The library includes 574 unit tests written with NUnit 4, covering all implementations, interfaces, edge cases, and concurrent stress tests.

dotnet test

Test Coverage by Implementation

Test Coverage by Extension Methods

Test Categories

Each implementation is tested across the following categories:

Test Coverage Percentage

Coverage distribution: ~69% of tests target the 7 core implementations, while ~31% cover the set-like extension methods across all interface families — including concurrent and sequential stress tests that exercise helpers with all implementations.

Benchmarks

Benchmarks are run with BenchmarkDotNet v0.15.0 using DefaultJob with CPUUsageDiagnoser.

Environment: .NET 10.0, 13th Gen Intel Core i9-13900H, 20 logical / 14 physical cores, RyuJIT AVX2

Benchmark Parameters: 100 keys x 50 values/key for bulk operations (5,000 pairs); 50 keys x 20 values/key for set operations (1,000 pairs).

Core Operations

Set Operations (via MultiMapHelper)

Key Takeaways

• AddRange vs Add: AddRange is significantly faster — MultiMapList ~7x faster, SortedMultiMap ~6x faster, MultiMapLock ~2.4x faster, MultiMapAsync ~4.3x faster than individual Add calls
• Fastest adds: MultiMapList (no uniqueness check) — ~2x faster than MultiMapSet
• Fastest lookups: SortedMultiMap Contains at 24 ns; MultiMapLock Contains at 14 ns
• ConcurrentMultiMap Count: O(k) — 37,655 ns vs O(1) sub-nanosecond for cached implementations
• SortedMultiMap: Slowest across all operations due to tree-based data structures, but provides sorted enumeration
• Thread-safe overhead: ConcurrentMultiMap is ~2.5x slower than MultiMapSet for adds; MultiMapLock is ~1.6x slower
• Async overhead: MultiMapAsync is comparable to MultiMapLock for reads; ~1.7x slower for adds due to SemaphoreSlim

License

This project is licensed under the MIT License.

Author

TigoS — GitHub