{"id":47,"date":"2024-02-13T07:33:53","date_gmt":"2024-02-13T15:33:53","guid":{"rendered":"https:\/\/denispavlov.net\/Blog\/?p=47"},"modified":"2024-05-28T12:09:18","modified_gmt":"2024-05-28T19:09:18","slug":"multi-value-dictionary","status":"publish","type":"post","link":"https:\/\/denispavlov.net\/Blog\/2024\/02\/13\/multi-value-dictionary\/","title":{"rendered":"Multi Value Dictionary"},"content":{"rendered":"\n

I recently was asked to implement a dictionary-like data structure that can store multiple values for a given key. The interface I was given is as follows.<\/p>\n\n\n\n

    public interface IMultiValueDictionary<K, V> : IEnumerable<KeyValuePair<K, V>>\n    {\n        bool Add(K key, V value);\n        IEnumerable<V> Get(K key);\n        IEnumerable<V> GetOrDefault(K key);\n        void Remove(K key, V value);\n        void Clear(K key);\n        IEnumerable<KeyValuePair<K, V>> Flatten();\n    }<\/code><\/pre>\n\n\n\n
Since the precondition was that the values are unique for any given key, I decided to use a Dictionary<\/code> where key is of type K<\/code> and value is a HashSet<\/code> of type V<\/code>, as follows.<\/p>\n\n\n\n
private readonly Dictionary<K, HashSet<V>> _data = [];<\/code><\/pre>\n\n\n\n
Let’s go down the list and implement all the methods.<\/p>\n\n\n\n
public bool Add(K key, V value)\n{\n    if (_data.TryGetValue(key, out var values))\n    {\n        return values.Add(value);\n    }\n    else\n    {\n        _data.Add(key, [value]);\n        return true;\n    }\n}<\/code><\/pre>\n\n\n\n
The add key\/value method is pretty straightforward. If the values for a given key exist, attempt to add new value to that hash set, which returns a boolean indicating success, otherwise add the key with a new hash set containing only the new value.
Time Complexity: O(1) or O(n)<\/strong> if underlying array runs out of empty spots and larger array has to be reallocated (Dictionary is implemented using an array under the hood, and HashSet is implemented using a Dictionary where key and value are same).<\/p>\n\n\n\n
public IEnumerable<V> Get(K key)\n{\n    if (!_data.TryGetValue(key, out var values))\n        throw new KeyNotFoundException();\n\n    return values;\n}<\/code><\/pre>\n\n\n\n
The get by key method should throw an exception if the key doesn’t exist, otherwise return the values at key.
Time Complexity: O(1)<\/strong><\/p>\n\n\n\n
public IEnumerable<V> GetOrDefault(K key) => _data.TryGetValue(key, out var values) ? values : [];<\/code><\/pre>\n\n\n\n
The get or default is a safe version of the get method, which will never throw an exception and is useful for method-chaining.
Time Complexity: O(1)<\/strong><\/p>\n\n\n\n
public void Remove(K key, V value)\n{\n    if (!_data.TryGetValue(key, out var values))\n        throw new KeyNotFoundException();\n\n    values.Remove(value);\n}<\/code><\/pre>\n\n\n\n
The remove key\/value method will throw an exception if the key doesn’t exist, otherwise will try to remove the value.
Time Complexity: O(1)<\/strong><\/p>\n\n\n\n
public void Clear(K key) => _data.Remove(key);<\/code><\/pre>\n\n\n\n
The clear method just removes that key if it exists, and all the values associated with it.
Time Complexity: O(1)<\/strong><\/p>\n\n\n\n
public IEnumerable<KeyValuePair<K, V>> Flatten()\n{\n    var data = new List<KeyValuePair<K, V>>();\n\n    foreach (var item in _data)\n        foreach (var value in item.Value)\n            data.Add(new KeyValuePair<K, V>(item.Key, value));\n\n    return data;\n}<\/code><\/pre>\n\n\n\n
The flatten method just needs to return a collection of all key\/value pairs, where key is repeated for each of its values. The above implementation does the job, however, it creates a copy of all the data in another list. Luckily, C# offers a better solution.<\/p>\n\n\n\n
public IEnumerable<KeyValuePair<K, V>> Flatten()\n{\n    foreach (var item in _data)\n        foreach (var value in item.Value)\n            yield return new KeyValuePair<K, V>(item.Key, value);\n}<\/code><\/pre>\n\n\n\n
The solution is to use yield return, which is an iterator to provide the next value. It avoids having to create another copy of data. Or use shorthand LINQ method syntax as shown below.
Time Complexity: O(n)<\/strong><\/p>\n\n\n\n
public IEnumerable<KeyValuePair<K, V>> Flatten()\n    => _data.SelectMany(x => x.Value.Select(value => new KeyValuePair<K, V>(x.Key, value)));<\/code><\/pre>\n\n\n\n
Great! Are we done?<\/p>\n\n\n\n
Not exactly. If you notice above, the IMultiValueDictionary<\/code> interface inherits IEnumerable<\/code> interface, so if we try to compile as is, we will get two errors.<\/p>\n\n\n\n
'MultiValueDictionary<K, V>' does not implement interface member 'IEnumerable<KeyValuePair<K, V>>.GetEnumerator()'\n'MultiValueDictionary<K, V>' does not implement interface member 'IEnumerable.GetEnumerator()'<\/code><\/pre>\n\n\n\n
We have to implement GetEnumerator<\/code> methods, as instructed by the compiler, to define how our data structure will iterate through its data. As it turns out, flatten already does exactly that (or defers that action) by returning an IEnumerable<\/code>, which has GetEnumerator<\/code>.<\/p>\n\n\n\n
public IEnumerator<KeyValuePair<K, V>> GetEnumerator() => Flatten().GetEnumerator();<\/code><\/pre>\n\n\n\n
And lastly IEnumerable.GetEnumerator<\/code> is implemented with the following one-liner, which you don’t usually have to change.<\/p>\n\n\n\n
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();<\/code><\/pre>\n\n\n\n
And that does it! This compiles nicely, passes all unit tests and is efficient at storing\/retrieving data.<\/strong><\/p>\n\n\n\n
\n\n\n\n