Повторяющиеся ключи в словарях .NET?

Я думаю, что что-то вроде List<KeyValuePair<object, object>> подойдет.

Дублирующиеся ключи нарушают весь контракт Словаря. В словаре каждый ключ уникален и соответствует одному значению. Если вы хотите связать объект с произвольным количеством дополнительных объектов, лучшим вариантом может быть что-то вроде DataSet (в просторечии - таблица). Поместите свои ключи в один столбец, а свои значения - в другой. Это значительно медленнее, чем словарь, но это ваш компромисс за потерю способности хешировать ключевые объекты.

Вы имеете в виду конгруэнтный, а не фактический дубликат? В противном случае хеш-таблица не сможет работать.

Конгруэнтность означает, что два отдельных ключа могут хешировать эквивалентное значение, но ключи не равны.

Например: скажем, хеш-функция вашей хэш-таблицы была просто hashval = key mod 3. И 1, и 4 соответствуют 1, но имеют разные значения. Здесь в игру вступает ваша идея списка.

Когда вам нужно найти 1, это значение хешируется до 1, список просматривается до тех пор, пока не будет найден ключ = 1.

Если вы разрешили вставку повторяющихся ключей, вы не сможете различить, какие ключи соответствуют каким значениям.

Если вы используете строки как в качестве ключей, так и в качестве значений, вы можете использовать System.Collections.Specialized.NameValueCollection, который вернет массив строковых значений через метод GetValues ​​(строковый ключ).

Я только что наткнулся на библиотеку PowerCollections, которая включает, среди прочего, класс MultiDictionary. Это аккуратно завершает этот тип функциональности.

NameValueCollection поддерживает несколько строковых значений под одним ключом (который также является строкой), но это единственный известный мне пример.

Я склонен создавать конструкции, подобные той, что в вашем примере, когда я сталкиваюсь с ситуациями, когда мне нужна такая функциональность.

Если вы используете .NET 3.5, используйте класс Lookup.

Обновлено: вы обычно создаете Lookup, используя Enumerable.ToLookup. Это действительно предполагает, что вам не нужно менять его впоследствии, но я обычно считаю, что это достаточно хорошо.

Если этот не работает для вас, я не думаю, что во фреймворке есть что-то, что поможет - и использование словаря так же хорошо, как и получается :(

Очень важное замечание относительно использования Lookup:

Вы можете создать экземпляр Lookup(TKey, TElement), вызвав ToLookup для объекта, который реализует IEnumerable(T).

Общедоступного конструктора для создания нового экземпляра Lookup(TKey, TElement) не существует. Кроме того, объекты Lookup(TKey, TElement) неизменяемы, то есть вы не можете добавлять или удалять элементы или ключи из объекта Lookup(TKey, TElement) после его создания.

(из MSDN)

Я думаю, что это будет ограничитель шоу для большинства применений.

Класс List на самом деле очень хорошо работает для коллекций ключ / значение, содержащих дубликаты, в которых вы хотели бы перебирать коллекцию. Пример:

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

В ответ на исходный вопрос. Что-то вроде Dictionary<string, List<object>> реализовано в классе MultiMap в Code Project.

Вы можете найти дополнительную информацию по ссылке ниже: http://www.codeproject.com/KB/cs/MultiKeyDictionary.aspx

Я наткнулся на этот пост в поисках того же ответа и не нашел, поэтому я создал простой пример решения, используя список словарей, переопределив оператор [], чтобы добавить новый словарь в список, когда у всех остальных есть заданный ключ (набор) и вернуть список значений (получить) .
Это уродливо и неэффективно, он получает / устанавливает ТОЛЬКО по ключу и всегда возвращает список, но он работает:

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

При использовании опции List<KeyValuePair<string, object>> вы можете использовать LINQ для поиска:

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 }

Вот один из способов сделать это с помощью 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);
}

Выходы k1 = v1, k1 = v2, k1 = v3

То, как я использую, просто

Dictionary<string, List<string>>

Таким образом, у вас есть единственный ключ, содержащий список строк.

Пример:

List<string> value = new List<string>();
if (dictionary.Contains(key)) {
     value = dictionary[key];
}
value.Add(newValue);

Если вы используете> = .NET 4, вы можете использовать класс Tuple:

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

Вы можете добавить одинаковые ключи в другом регистре, например:

key1
Key1
KEY1
KeY1
kEy1
keY1

Я знаю, что это фиктивный ответ, но сработал для меня.

Также это возможно:

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

Таким образом, у нас могут быть уникальные ключи. Надеюсь, что это работает для вас.

U может определить метод построения составного строкового ключа везде, где вы хотите использовать словарь, вы должны использовать этот метод для создания своего ключа Например:

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

для использования:

myDict.ContainsKey(keyBuilder(key1, key2))

Достаточно просто создать «свою собственную» версию словаря, допускающую «повторяющиеся ключевые» записи. Вот примерная простая реализация. Возможно, вы захотите рассмотреть возможность добавления поддержки практически для большинства (если не для всех) 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];
        }
    }
}

Быстрый пример того, как его использовать:

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

Это буксирный способ. Параллельный словарь, я думаю, это вам поможет:

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

Примеры:

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
            }

Я изменил ответ @Hector Correa на расширение с универсальными типами, а также добавил к нему собственный TryGetValue.

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

я использую этот простой класс:

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

использование:

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

Вы можете создать свою собственную оболочку словаря, что-то вроде этой, в качестве бонуса она поддерживает нулевое значение в качестве ключа:

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

Пример использования:

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 }

Начиная с нового C# (я полагаю, что это из 7.0), вы также можете сделать что-то вроде этого:

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

и вы используете его как стандартный список, но с двумя значениями, названными так, как вы хотите

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