299

Are there any dictionary classes in the .NET base class library which allow duplicate keys to be used? The only solution I've found is to create, for example, a class like:

Dictionary<string, List<object>>

But this is quite irritating to actually use. In Java, I believe a MultiMap accomplishes this, but cannot find an analog in .NET.

8
  • 4
    How is this duplicate key, it's duplicate values(the List), right? Commented Dec 18, 2010 at 5:36
  • 3
    @ShamimHafiz, no, the values need not be duplicates. If you have to store duplicates { a, 1 } and { a, 2 } in a hash table where a being the key, one alternative is to have { a, [1, 2] }.
    – nawfal
    Commented Jun 19, 2014 at 8:27
  • 3
    Actually, I believe what is really wanted here is a collection where each key can map to one or more values. I think that the expression "duplicate keys" doesn't really convey this.
    – DavidRR
    Commented Aug 6, 2014 at 1:25
  • 1
    For future reference, you should consider keeping 1 key just adding the values to it instead of adding same keys over and over.
    – Ya Wang
    Commented Aug 28, 2015 at 15:38
  • 2
    @gcode You essentially described a NameValueCollection.
    – Suncat2000
    Commented Jan 28, 2022 at 14:54

25 Answers 25

244

If you're using .NET 3.5, use the Lookup class.

EDIT: You generally create a Lookup using Enumerable.ToLookup. This does assume that you don't need to change it afterwards - but I typically find that's good enough.

If that doesn't work for you, I don't think there's anything in the framework which will help - and using the dictionary is as good as it gets :(

5
  • Thanks for the heads-up on Lookup. It offers a great way to partition (group) results from a linq query that aren't standard orderby criteria. Commented Sep 29, 2008 at 20:42
  • 3
    @Josh: You use Enumerable.ToLookup to create one.
    – Jon Skeet
    Commented May 10, 2010 at 13:43
  • 39
    Word of caution: Lookup is not serializable Commented Dec 23, 2011 at 15:27
  • 3
    how should we add items to that Lookup?
    – moldovanu
    Commented Apr 16, 2012 at 14:58
  • The .NET Framework does not allow you to instantiate a Lookup class and manipulate it yourself. You must populate some enumerable collection first and then convert it into a Lookup collection. Yet another class that Microsoft designed to make less useful.
    – Suncat2000
    Commented Jan 27, 2022 at 22:16
197

The List class actually works quite well for key/value collections containing duplicates where you would like to iterate over the collection. Example:

List<KeyValuePair<string, string>> list = new List<KeyValuePair<string, string>>();

// add some values to the collection here

for (int i = 0;  i < list.Count;  i++)
{
    Print(list[i].Key, list[i].Value);
}
2
  • 43
    This solution works functionally, but the implementation of List has no knowledge of the key or value and cant optimize searching for keys at all Commented Feb 28, 2013 at 3:02
  • ModelStateDictionary uses IEnumerable<KeyValuePair<string, ModelStateEntry>>, so if the list is small we should not feel bad about optimizing. You can use IList instead if you want to Add.
    – Jess
    Commented Nov 28, 2021 at 16:28
49

Here is one way of doing this with List< KeyValuePair< string, string > >

public class ListWithDuplicates : List<KeyValuePair<string, string>>
{
    public void Add(string key, string value)
    {
        var element = new KeyValuePair<string, string>(key, value);
        this.Add(element);
    }
}

var list = new ListWithDuplicates();
list.Add("k1", "v1");
list.Add("k1", "v2");
list.Add("k1", "v3");

foreach(var item in list)
{
    string x = string.format("{0}={1}, ", item.Key, item.Value);
}

Outputs k1=v1, k1=v2, k1=v3

0
26

If you are using strings as both the keys and the values, you can use System.Collections.Specialized.NameValueCollection, which will return an array of string values via the GetValues(string key) method.

6
  • 8
    NameValueCollection does not allow multiple keys. Commented Apr 3, 2015 at 10:15
  • @Jenny O'Reilly: Sure, you can add duplicate keys.
    – isHuman
    Commented Jan 5, 2016 at 12:51
  • Strictly speaking @JennyO'Reilly is correct, as the remarks on the linked MSDN page clearly states: this class stores multiple string values under a single key.
    – Ronald
    Commented Mar 15, 2017 at 15:57
  • It will allow but will return multiple values, I tried using index and key. Commented Oct 6, 2017 at 20:51
  • Note that NameValueCollection cannot be deserailized by System.Text.Json. Commented May 15, 2021 at 8:06
19

I just came across the PowerCollections library which includes, among other things, a class called MultiDictionary. This neatly wraps this type of functionality.

17

Since the new C# (I belive it's from 7.0), you can also do something like this:

var duplicatedDictionaryExample = new List<(string Key, string Value)> { ("", "") ... }

and you are using it as a standard List, but with two values named whatever you want

foreach(var entry in duplicatedDictionaryExample)
{ 
    // do something with the values
    entry.Key;
    entry.Value;
}
0
16

Very important note regarding use of Lookup:

You can create an instance of a Lookup(TKey, TElement) by calling ToLookup on an object that implements IEnumerable(T)

There is no public constructor to create a new instance of a Lookup(TKey, TElement). Additionally, Lookup(TKey, TElement) objects are immutable, that is, you cannot add or remove elements or keys from a Lookup(TKey, TElement) object after it has been created.

(from MSDN)

I'd think this would be a show stopper for most uses.

2
  • 6
    I can think of very few uses where this would be a show stopper. But then, I think immutable objects are great. Commented May 23, 2011 at 16:35
  • 2
    @JoelMueller I can think of a lot of cases where this is a show stopper. Having to re-create a dictionary to add an item is not a particularly efficient solution...
    – reirab
    Commented Dec 2, 2014 at 20:16
15

I think something like List<KeyValuePair<object, object>> would do the Job.

4
  • How do you look something up in that list by it's key? Commented Sep 28, 2008 at 17:00
  • You have to iterate through it: but I was not aware of the LookUp-Class of .NET 3.5: maybe this is more useful for searching in it's content.
    – MADMap
    Commented Sep 28, 2008 at 17:20
  • 2
    @wizlib: The only way is to loop through the list, which is not nearly as efficient as hashing. -1
    – petr k.
    Commented Sep 28, 2008 at 17:21
  • @petrk. That really depends on what your data is. I used this implementation because I had very few unique keys and didn't want to incur the overhead of hash collisions. +1
    – Evan M
    Commented Jun 11, 2012 at 16:13
11

If you are using >= .NET 4 then you can use Tuple Class:

// declaration
var list = new List<Tuple<string, List<object>>>();

// to add an item to the list
var item = Tuple<string, List<object>>("key", new List<object>);
list.Add(item);

// to iterate
foreach(var i in list)
{
    Console.WriteLine(i.Item1.ToString());
}
1
  • 2
    This looks like a List<KeyValuePair<key, value>> solution like the above. Am I wrong? Commented Apr 10, 2019 at 16:08
10

It's easy enough to "roll your own" version of a dictionary that allows "duplicate key" entries. Here is a rough simple implementation. You might want to consider adding support for basically most (if not all) on IDictionary<T>.

public class MultiMap<TKey,TValue>
{
    private readonly Dictionary<TKey,IList<TValue>> storage;

    public MultiMap()
    {
        storage = new Dictionary<TKey,IList<TValue>>();
    }

    public void Add(TKey key, TValue value)
    {
        if (!storage.ContainsKey(key)) storage.Add(key, new List<TValue>());
        storage[key].Add(value);
    }

    public IEnumerable<TKey> Keys
    {
        get { return storage.Keys; }
    }

    public bool ContainsKey(TKey key)
    {
        return storage.ContainsKey(key);
    }

    public IList<TValue> this[TKey key]
    {
        get
        {
            if (!storage.ContainsKey(key))
                throw new KeyNotFoundException(
                    string.Format(
                        "The given key {0} was not found in the collection.", key));
            return storage[key];
        }
    }
}

A quick example on how to use it:

const string key = "supported_encodings";
var map = new MultiMap<string,Encoding>();
map.Add(key, Encoding.ASCII);
map.Add(key, Encoding.UTF8);
map.Add(key, Encoding.Unicode);

foreach (var existingKey in map.Keys)
{
    var values = map[existingKey];
    Console.WriteLine(string.Join(",", values));
}
4

In answer to the original question. Something like Dictionary<string, List<object>> is implemented in a class called MultiMap in The Code Project.

You could find more info to the below link : http://www.codeproject.com/KB/cs/MultiKeyDictionary.aspx

3

The NameValueCollection supports multiple string values under one key (which is also a string), but it is the only example I am aware of.

I tend to create constructs similar to the one in your example when I run into situations where I need that sort of functionality.

0
3

When using the List<KeyValuePair<string, object>> option, you could use LINQ to do the search:

List<KeyValuePair<string, object>> myList = new List<KeyValuePair<string, object>>();
//fill it here
var q = from a in myList Where a.Key.Equals("somevalue") Select a.Value
if(q.Count() > 0){ //you've got your value }
1
  • 3
    Yes, but that doesn't make it faster (still no hashing)
    – Haukman
    Commented Aug 16, 2011 at 18:28
2

Do you mean congruent and not an actual duplicate? Otherwise a hashtable wouldn't be able to work.

Congruent means that two separate keys can hash to the equivalent value, but the keys aren't equal.

For example: say your hashtable's hash function was just hashval = key mod 3. Both 1 and 4 map to 1, but are different values. This is where your idea of a list comes into play.

When you need to lookup 1, that value is hashed to 1, the list is traversed until the Key = 1 is found.

If you allowed for duplicate keys to be inserted, you wouldn't be able to differentiate which keys map to which values.

1
  • 3
    A hash table already handles keys which happen to hash to the same value (this is called a collision). I am referring to a situation where you want to map multiple values to the same exact key.
    – waltersobchek.myopenid.com
    Commented Sep 28, 2008 at 19:21
2

The way I use is just a

Dictionary<string, List<string>>

This way you have a single key holding a list of strings.

Example:

List<string> value = new List<string>();
if (dictionary.Contains(key)) {
     value = dictionary[key];
}
value.Add(newValue);
2
  • That's nice and clean. Commented Aug 5, 2018 at 15:10
  • This is a great solution to handle my use case.
    – dub stylee
    Commented Sep 24, 2018 at 21:38
2

You can create your own dictionary wrapper, something like this one, as a bonus it supports null value as a key:

/// <summary>
/// Dictionary which supports duplicates and null entries
/// </summary>
/// <typeparam name="TKey">Type of key</typeparam>
/// <typeparam name="TValue">Type of items</typeparam>
public class OpenDictionary<TKey, TValue>
{
    private readonly Lazy<List<TValue>> _nullStorage = new Lazy<List<TValue>>(
        () => new List<TValue>());

    private readonly Dictionary<TKey, List<TValue>> _innerDictionary =
        new Dictionary<TKey, List<TValue>>();

    /// <summary>
    /// Get all entries
    /// </summary>
    public IEnumerable<TValue> Values =>
        _innerDictionary.Values
            .SelectMany(x => x)
            .Concat(_nullStorage.Value);

    /// <summary>
    /// Add an item
    /// </summary>
    public OpenDictionary<TKey, TValue> Add(TKey key, TValue item)
    {
        if (ReferenceEquals(key, null))
            _nullStorage.Value.Add(item);
        else
        {
            if (!_innerDictionary.ContainsKey(key))
                _innerDictionary.Add(key, new List<TValue>());

            _innerDictionary[key].Add(item);
        }

        return this;
    }

    /// <summary>
    /// Remove an entry by key
    /// </summary>
    public OpenDictionary<TKey, TValue> RemoveEntryByKey(TKey key, TValue entry)
    {
        if (ReferenceEquals(key, null))
        {
            int targetIdx = _nullStorage.Value.FindIndex(x => x.Equals(entry));
            if (targetIdx < 0)
                return this;

            _nullStorage.Value.RemoveAt(targetIdx);
        }
        else
        {
            if (!_innerDictionary.ContainsKey(key))
                return this;

            List<TValue> targetChain = _innerDictionary[key];
            if (targetChain.Count == 0)
                return this;

            int targetIdx = targetChain.FindIndex(x => x.Equals(entry));
            if (targetIdx < 0)
                return this;

            targetChain.RemoveAt(targetIdx);
        }

        return this;
    }

    /// <summary>
    /// Remove all entries by key
    /// </summary>
    public OpenDictionary<TKey, TValue> RemoveAllEntriesByKey(TKey key)
    {
        if (ReferenceEquals(key, null))
        {
            if (_nullStorage.IsValueCreated)
                _nullStorage.Value.Clear();
        }       
        else
        {
            if (_innerDictionary.ContainsKey(key))
                _innerDictionary[key].Clear();
        }

        return this;
    }

    /// <summary>
    /// Try get entries by key
    /// </summary>
    public bool TryGetEntries(TKey key, out IReadOnlyList<TValue> entries)
    {
        entries = null;

        if (ReferenceEquals(key, null))
        {
            if (_nullStorage.IsValueCreated)
            {
                entries = _nullStorage.Value;
                return true;
            }
            else return false;
        }
        else
        {
            if (_innerDictionary.ContainsKey(key))
            {
                entries = _innerDictionary[key];
                return true;
            }
            else return false;
        }
    }
}

The sample of usage:

var dictionary = new OpenDictionary<string, int>();
dictionary.Add("1", 1); 
// The next line won't throw an exception; 
dictionary.Add("1", 2);

dictionary.TryGetEntries("1", out List<int> result); 
// result is { 1, 2 }

dictionary.Add(null, 42);
dictionary.Add(null, 24);
dictionary.TryGetEntries(null, out List<int> result); 
// result is { 42, 24 }
4
  • Can you throw some explanation around what your code does, how it answers the question, and some example usages? Commented Oct 26, 2019 at 23:56
  • @Enigmativity, it does exactly what was asked, the question was to suggest some dictionary which supports duplicates, so I offered to create a wrapper around .net dictionary which will support this functionality and as an example created such wrapper, as a bonus it can handle null as a key (even if it's a bad practise, for sure) The usage is quite simple: var dictionary = new OpenDictionary<string, int>(); dictionary.Add("1", 1); // The next line won't throw an exception; dictionary.Add("1", 2); dictionary.TryGetEntries("1", out List<int> result); // result is { 1, 2 } Commented Oct 27, 2019 at 17:12
  • Can you add the detail to your answer? Commented Oct 27, 2019 at 22:54
  • @Enigmativity, if you mean to the original answer, then sure Commented Oct 29, 2019 at 7:49
1

I stumbled across this post in search of the same answer, and found none, so I rigged up a bare-bones example solution using a list of dictionaries, overriding the [] operator to add a new dictionary to the list when all others have a given key(set), and return a list of values (get).
It's ugly and inefficient, it ONLY gets/sets by key, and it always returns a list, but it works:

 class DKD {
        List<Dictionary<string, string>> dictionaries;
        public DKD(){
            dictionaries = new List<Dictionary<string, string>>();}
        public object this[string key]{
             get{
                string temp;
                List<string> valueList = new List<string>();
                for (int i = 0; i < dictionaries.Count; i++){
                    dictionaries[i].TryGetValue(key, out temp);
                    if (temp == key){
                        valueList.Add(temp);}}
                return valueList;}
            set{
                for (int i = 0; i < dictionaries.Count; i++){
                    if (dictionaries[i].ContainsKey(key)){
                        continue;}
                    else{
                        dictionaries[i].Add(key,(string) value);
                        return;}}
                dictionaries.Add(new Dictionary<string, string>());
                dictionaries.Last()[key] =(string)value;
            }
        }
    }
1

I changed @Hector Correa 's answer into an extension with generic types and also added a custom TryGetValue to it.

  public static class ListWithDuplicateExtensions
  {
    public static void Add<TKey, TValue>(this List<KeyValuePair<TKey, TValue>> collection, TKey key, TValue value)
    {
      var element = new KeyValuePair<TKey, TValue>(key, value);
      collection.Add(element);
    }

    public static int TryGetValue<TKey, TValue>(this List<KeyValuePair<TKey, TValue>> collection, TKey key, out IEnumerable<TValue> values)
    {
      values = collection.Where(pair => pair.Key.Equals(key)).Select(pair => pair.Value);
      return values.Count();
    }
  }
1

i use this simple class:

public class ListMap<T,V> : List<KeyValuePair<T, V>>
{
    public void Add(T key, V value) {
        Add(new KeyValuePair<T, V>(key, value));
    }

    public List<V> Get(T key) {
        return FindAll(p => p.Key.Equals(key)).ConvertAll(p=> p.Value);
    }
}

usage:

var fruits = new ListMap<int, string>();
fruits.Add(1, "apple");
fruits.Add(1, "orange");
var c = fruits.Get(1).Count; //c = 2;
0

This is a tow way Concurrent dictionary I think this will help you:

public class HashMapDictionary<T1, T2> : System.Collections.IEnumerable
{
    private System.Collections.Concurrent.ConcurrentDictionary<T1, List<T2>> _keyValue = new System.Collections.Concurrent.ConcurrentDictionary<T1, List<T2>>();
    private System.Collections.Concurrent.ConcurrentDictionary<T2, List<T1>> _valueKey = new System.Collections.Concurrent.ConcurrentDictionary<T2, List<T1>>();

    public ICollection<T1> Keys
    {
        get
        {
            return _keyValue.Keys;
        }
    }

    public ICollection<T2> Values
    {
        get
        {
            return _valueKey.Keys;
        }
    }

    public int Count
    {
        get
        {
            return _keyValue.Count;
        }
    }

    public bool IsReadOnly
    {
        get
        {
            return false;
        }
    }

    public List<T2> this[T1 index]
    {
        get { return _keyValue[index]; }
        set { _keyValue[index] = value; }
    }

    public List<T1> this[T2 index]
    {
        get { return _valueKey[index]; }
        set { _valueKey[index] = value; }
    }

    public void Add(T1 key, T2 value)
    {
        lock (this)
        {
            if (!_keyValue.TryGetValue(key, out List<T2> result))
                _keyValue.TryAdd(key, new List<T2>() { value });
            else if (!result.Contains(value))
                result.Add(value);

            if (!_valueKey.TryGetValue(value, out List<T1> result2))
                _valueKey.TryAdd(value, new List<T1>() { key });
            else if (!result2.Contains(key))
                result2.Add(key);
        }
    }

    public bool TryGetValues(T1 key, out List<T2> value)
    {
        return _keyValue.TryGetValue(key, out value);
    }

    public bool TryGetKeys(T2 value, out List<T1> key)
    {
        return _valueKey.TryGetValue(value, out key);
    }

    public bool ContainsKey(T1 key)
    {
        return _keyValue.ContainsKey(key);
    }

    public bool ContainsValue(T2 value)
    {
        return _valueKey.ContainsKey(value);
    }

    public void Remove(T1 key)
    {
        lock (this)
        {
            if (_keyValue.TryRemove(key, out List<T2> values))
            {
                foreach (var item in values)
                {
                    var remove2 = _valueKey.TryRemove(item, out List<T1> keys);
                }
            }
        }
    }

    public void Remove(T2 value)
    {
        lock (this)
        {
            if (_valueKey.TryRemove(value, out List<T1> keys))
            {
                foreach (var item in keys)
                {
                    var remove2 = _keyValue.TryRemove(item, out List<T2> values);
                }
            }
        }
    }

    public void Clear()
    {
        _keyValue.Clear();
        _valueKey.Clear();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return _keyValue.GetEnumerator();
    }
}

examples:

public class TestA
{
    public int MyProperty { get; set; }
}

public class TestB
{
    public int MyProperty { get; set; }
}

            HashMapDictionary<TestA, TestB> hashMapDictionary = new HashMapDictionary<TestA, TestB>();

            var a = new TestA() { MyProperty = 9999 };
            var b = new TestB() { MyProperty = 60 };
            var b2 = new TestB() { MyProperty = 5 };
            hashMapDictionary.Add(a, b);
            hashMapDictionary.Add(a, b2);
            hashMapDictionary.TryGetValues(a, out List<TestB> result);
            foreach (var item in result)
            {
                //do something
            }
0

Use a sorted list. Then to iterate all values for a key, binary search to find the first (or no) value for key, iterate forward until key no longer matches.

-3

U can define a method to building a Compound string key every where u want to using dictionary u must using this method to build your key for example:

private string keyBuilder(int key1, int key2)
{
    return string.Format("{0}/{1}", key1, key2);
}

for using:

myDict.ContainsKey(keyBuilder(key1, key2))
-4

Duplicate keys break the entire contract of the Dictionary. In a dictionary each key is unique and mapped to a single value. If you want to link an object to an arbitrary number of additional objects, the best bet might be something akin to a DataSet (in common parlance a table). Put your keys in one column and your values in the other. This is significantly slower than a dictionary, but that's your tradeoff for losing the ability to hash the key objects.

1
  • 6
    Isn't the whole point of using a Dictionary for the performance gain? Using a DataSet seems no better than a List<KeyValuePair<T, U>>.
    – Doug
    Commented Feb 24, 2011 at 16:51
-5

Also this is possible:

Dictionary<string, string[]> previousAnswers = null;

This way, we can have unique keys. Hope this works for you.

1
  • The OP asked for a dictionary that allows duplicate keys.
    – Skaparate
    Commented Mar 24, 2016 at 21:30
-14

You can add same keys with different case like:

key1
Key1
KEY1
KeY1
kEy1
keY1

I know is dummy answer, but worked for me.

1
  • 6
    No, it did not work for you. Dictionaries allow very fast lookup - also classified as O(1) - by key, You lose that when you add your differently cased multiple keys, because how do you retrieve them? Try every upper/lower case combination? No matter how you do it, performance will not be that of normal, single dictionary lookup. That's in addition to other, more obvious shortcomings like the limitation of values per key, depending on the number of upcaseable characters in the key. Commented Jul 2, 2015 at 23:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.