Custom Data Structure: A One-to-Many Mapping

Suppose your application displays a message according to the state a customer lives in. Several states can use the same message, but a state must have exactly one assigned message. Given the state, you need to retrieve that message.

That sounds almost like a dictionary. The distinction is that we want to add a message together with several states, enforce the relationship, and later look it up in the other direction. The data structure should own those rules so every caller does not have to implement them again.

This is a useful exercise in building something from the collections .NET already provides. Start with the requirements, write tests for them, try different implementations, and then compare their performance. You can try your own version before looking at the completed sample.

Define the relationship first

The terminology in the example calls the message the key and each state a value. A key can have many values; a value can belong to only one key. Both keys and values are unique within their respective roles.

Each value belongs to one message. Lookup starts with a value and returns its associated message.

Here is the original interface:

internal interface IOneToManyMap<TKey, in TValue>
{
    void AddOneToManyMapping(TKey key, TValue[] values);
    TKey this[TValue value] { get; }
}

If the generic declaration distracts you, begin with strings for both types. The significant feature is the indexer: it accepts a value and returns a key. This is the direction in which the application needs to use the relationship.

For example:

map.AddOneToManyMapping("This is Message A", new[] { "VA", "MD" });
map.AddOneToManyMapping("This is Message B", new[] { "IN" });

string message = map["VA"]; // This is Message A

Adding a new value to an existing key is allowed. Adding a value that already has a mapping is rejected with ValuesHasPriorMappingToKeyException. Looking up a value with no mapping throws ValueNotMappedToKeyException.

There is one more requirement that is easy to miss: if an attempted addition contains a value that is already mapped, none of that addition should take effect. Imagine adding three states when the third is already assigned. We must not leave the first two inserted after reporting failure.

A database model makes the constraints visible

We can express this requirement with two relational models. The first has a Message table and a StateMessage table. Message.Description is unique. StateMessage.MessageId references the message, while its state Acronym is unique.

The second represents messages and states as independent entities, with an association table between them:

Primary keys identify rows, foreign keys connect them, and the unique state constraint prevents a state from belonging to multiple messages.

In the association model, the (MessageId, StateId) pair forms the primary key. That alone would still allow one state to appear with two different messages. The separate unique constraint on StateId prevents it. That constraint carries a business rule, and it is the part you must not lose when translating the model into an in-memory structure.

I use an association when the entities have their own reasons to exist. A state and a message can each exist independently of this relationship. A header/detail model is more natural when the detail exists because of its parent, such as an order line belonging to an order.

With the association model, a view can join the three tables, and a stored procedure can retrieve a message description from a state acronym. The in-memory versions follow the same general idea without requiring a database round trip for each lookup.

Use the same behavioral tests for every candidate

Before looking at a timing graph, make each implementation answer the same tests. The sample uses parameterized tests to run a shared suite against all four classes.

The suite checks successful lookup, missing-value lookup, adding values to an existing key, rejecting an existing mapping, and leaving the map unchanged when an addition contains an existing value. The last check must inspect both sides of the failure: old mappings remain, and the new values attempted before the conflict remain absent.

An exception alone does not prove the operation left its state unchanged. If the assertion stops at “it threw,” a partially applied operation can pass the test.

There is also an uncovered case in the historical implementation: a repeated new value within the same incoming array. The dictionary version checks incoming values against existing state, then inserts them one at a time. An input such as new[] { "VA", "VA" } passes the precheck, inserts the first value, and then fails on the second. It can leave a partial addition. The other collection implementations do not all treat this case the same way either.

That is a limit of the sample’s validation, not a relaxation of the uniqueness rule. A complete contract needs to decide how it handles duplicates within the incoming batch and validate that before committing the change. Nulls, equality rules and concurrent access also need explicit contracts if the structure is to support them.

Four ways to store the relationship

The DataTable implementation creates two tables and a DataRelation. Primary keys, a unique constraint and a foreign-key constraint express much of the schema directly. Lookup finds the value row and follows its parent relation to the key row. I like how clearly this resembles the relational model, although the generality of those classes has a cost.

The list implementation uses a list of keys with IDs and a list associating values with those IDs. Finding an item requires scanning. A List<T> uses an array internally, but the sample stores reference-type entries, so the contiguous part is the sequence of references.

The sorted-list implementation uses three SortedList collections: key to ID, ID to key, and value to key ID. Searching ordered keys uses binary search. Insertions have their own cost because the ordered storage must be maintained.

The dictionary version uses the same three relationships with dictionaries. Its lookup is short:

if (valueToKeyIdDict.TryGetValue(value, out int keyId))
{
    return idToKeyDict[keyId];
}

throw new ValueNotMappedToKeyException(
    $"The value: {value} of type: {typeof(TValue)}, " +
    $"has not been mapped to a Key of type: {typeof(TKey)}");

The private indexes are implementation details. The caller still sees the same operation and the same missing-value contract. That lets us compare storage choices without forcing those choices into the application’s call sites.

The sample deliberately explores these compositions. A more direct value-to-key dictionary is another candidate worth considering when the required operations permit it. It still has to satisfy the key, value and addition rules; a short indexer alone is not the whole implementation.

Read the benchmark as a batch of lookups

The benchmark builds the mappings in setup. Each measured method then loops over the generated values, retrieves each key and returns the last result. These are successful lookups: the code creates randomizedValues, assigns those values to keys, then looks up that same array.

This benchmark measures successful lookups only. A workload containing missing values would also take the exception path and measure something different. Include that case in a separate comparison if the application needs it.

Selected values from the original workbook are below. Times are microseconds for the whole batch, and have not been remeasured on a current runtime.

Selected original measurements, plotted against the actual number of values. The full batch grows with the collection; these are not single-lookup timings.

The dictionary is fastest across these cases. The linear list beats the sorted list at smaller sizes, then falls behind. Big-O notation helps us reason about growth, but does not establish which implementation is faster at a particular small size. Comparison cost and memory access matter too.

There is another important distinction: an approximately constant-time dictionary lookup does not imply a constant-time batch of N lookups. Nor is a batch that searches all N entries using linear scans merely one linear search. The graph combines the cost of each lookup with an increasing number of lookups.

Cache and prefetch behavior are possible explanations for the small-list result, but the timings alone do not isolate that cause. Similarly, the close DataTable and sorted-list results do not prove that their internal algorithms are identical.

The original workbook contains a suspicious list timing of 11.096 at 300 values. It is omitted from this selected comparison rather than silently corrected. The DataTable row also reports 696000 B allocated and 164.0625 Gen 0 collections per 1,000 operations; the workbook does not label a separate input size for those final diagnostic columns. They establish a reason to investigate allocation, without treating that number as a per-lookup allocation for every size.

Try another implementation if you have an idea. First run the behavioral tests, including the failure cases. Then measure the operations and data sizes the application actually uses. A data structure earns its place by preserving the rules as well as making useful work efficient.