Duplicate keys in .NET dictionaries?

Question

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.

Answer 1

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 :(

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

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

Answer 6

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.

Answer 7

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

Answer 8

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

Answer 9

Have a look at C5's HashBag class.

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

Answer 11

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

Answer 12

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.

Answer 13

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 }

Answer 14

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

Answer 15

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.

Answer 16

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

Answer 17

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

Answer 18

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
            }

Answer 19

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;

Answer 20

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

Answer 21

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.

Answer 22

Also this is possible:

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

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

Answer 23

You can add same keys with different case like:

key1
Key1
KEY1
KeY1
kEy1
keY1

I know is dummy answer, but worked for me.