Дублирующиеся ключи в словарях .NET?

256

Есть ли в библиотеке базовых классов .NET какие-либо словарные классы, позволяющие использовать дублирующиеся ключи? Единственное решение, которое я нашел, - это создать, например, такой класс:

Dictionary<string, List<object>>

Но это довольно раздражает на самом деле использовать. Я полагаю, что в Java MultiMap выполняет это, но не может найти аналог в .NET.

Механическая улитка
источник
3
Как этот дубликат ключа, это дубликаты значений (Список), верно?
Шамим Хафиз
1
@ShamimHafiz, нет, значения не должны быть дубликатами. Если вам нужно хранить дубликаты { a, 1 }и { a, 2 }в хеш-таблице, где aони являются ключом, есть альтернатива { a, [1, 2] }.
nawfal
1
На самом деле, я считаю, что здесь действительно требуется коллекция, в которой каждый ключ может отображаться в одно или несколько значений. Я думаю, что выражение «дубликаты ключей» на самом деле не передает этого.
DavidRR
Для дальнейшего использования, вам следует рассмотреть возможность сохранения 1 ключа, просто добавляя к нему значения, а не добавляя одни и те же ключи снова и снова.
Я. Ван
Если и ключи, и значения являются строками, существует NameValueCollection (которая может связывать несколько строковых значений с каждым строковым ключом).
AnorZaken

Ответы:

229

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

РЕДАКТИРОВАТЬ: вы обычно создаете Lookupиспользование Enumerable.ToLookup. Это предполагает, что вам не нужно менять его потом - но я нахожу, что это достаточно хорошо.

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

Джон Скит
источник
Спасибо за хедз-ап на Lookup. Он предлагает отличный способ разбить (сгруппировать) результаты запроса linq, которые не являются стандартными критериями orderby.
Роберт Полсон,
3
@Josh: вы используете Enumerable.ToLookup для его создания.
Джон Скит
29
Слово предостережения : Lookupне сериализуемо
SliverNinja - MSFT
1
как мы должны добавить элементы в этот поиск?
молдавану
171

Класс 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);
}
Джон Сондерс
источник
31
Это решение работает функционально, но реализация List не знает ключа или значения и вообще не может оптимизировать поиск ключей
Спенсер Роуз,
41

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

Гектор Корреа
источник
Прекрасно работает в моем сценарии, а также прост в использовании.
user6121177
21

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

Matt
источник
6
NameValueCollection не позволяет использовать несколько ключей.
Дженни О'Рейли,
@ Дженни О'Рейли: Конечно, вы можете добавить дубликаты ключей.
isHuman
Строго говоря, @ JennyO'Reilly - это правильно, поскольку в примечаниях на связанной странице MSDN четко сказано: этот класс хранит несколько строковых значений под одним ключом .
Рональд
Это позволит, но вернет несколько значений, я пытался использовать индекс и ключ.
user6121177
18

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


источник
14

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

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

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

(из MSDN)

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

TheSoftwareJedi
источник
6
Я могу вспомнить очень мало случаев, когда это будет шоу-стопором. Но тогда я думаю, что неизменные объекты - это здорово.
Джоэл Мюллер
1
@JoelMueller Я могу вспомнить много случаев, когда это шоу-стоппер. Необходимость повторного создания словаря для добавления элемента не является особенно эффективным решением ...
reirab
12

Я думаю, что-то вроде List<KeyValuePair<object, object>>бы сделал работу.

MADMap
источник
Как вы ищите что-то в этом списке по его ключу?
Уэйн Блосс,
Вы должны пройти через это: но я не знал о LookUp-классе .NET 3.5: возможно, это более полезно для поиска в его содержимом.
MADMap
2
@wizlib: единственный способ - циклически проходить по списку, который не так эффективен, как хеширование. -1
петр к.
@petrk. Это действительно зависит от ваших данных. Я использовал эту реализацию, потому что у меня было очень мало уникальных ключей и я не хотел нести накладные расходы на хэш-конфликты. +1
Эван М
9

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

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

источник
Это выглядит как List<KeyValuePair<key, value>>решение, как указано выше. Я ошибся?
Натан
6

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

В ответ на оригинальный вопрос. Нечто подобное Dictionary<string, List<object>>реализовано в классе, названном MultiMapв Code Project.

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

Дэн
источник
3

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

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

ckramer
источник
3

При использовании 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 }
Greg
источник
2
Да, но это не делает это быстрее (все еще без хэширования)
Хаукман
3

Так как новый 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;
}
reniasa
источник
2

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

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

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

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

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

Николас Манкузо
источник
2
Хеш-таблица уже обрабатывает ключи, которые имеют хеш-значения с тем же значением (это называется коллизией). Я имею в виду ситуацию, когда вы хотите отобразить несколько значений на один и тот же ключ.
2

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

Dictionary<string, List<string>>

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

Пример:

List<string> value = new List<string>();
if (dictionary.Contains(key)) {
     value = dictionary[key];
}
value.Add(newValue);
Стефан Мильке
источник
Это красиво и чисто.
Джерри Никсон
Это отличное решение для моего случая использования.
даб стайл
1

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

 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;
            }
        }
    }
Sintrinsic
источник
1

Я изменил ответ @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();
    }
  }
kjhf
источник
0

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

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
            }
Али Юсефи
источник
0

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

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;
Джон
источник
0

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

/// <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 }
Александр Толстиков
источник
Можете ли вы дать некоторые объяснения относительно того, что делает ваш код, как он отвечает на вопрос, и некоторые примеры использования?
Enigmativity
@Enigmativity, он делает именно то, что было задано, вопрос заключался в том, чтобы предложить какой-то словарь, который поддерживает дубликаты, поэтому я предложил создать обертку вокруг словаря .net, которая будет поддерживать эту функцию, и в качестве примера создал такую ​​обертку, в качестве бонуса он может обрабатывать ноль в качестве ключа (даже если это плохая практика, наверняка) Использование довольно просто: 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 }
Александр Толстиков
Можете ли вы добавить детали к своему ответу?
Enigmativity
@ Энигмативность, если ты имеешь в виду исходный ответ, то обязательно
Александр Толстиков
-1

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

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

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

myDict.ContainsKey(keyBuilder(key1, key2))
Алиреза Эсрари
источник
-3

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

Райан
источник
5
Не является ли смысл использования словаря для повышения производительности? Использование DataSet кажется не лучше, чем List <KeyValuePair <T, U >>.
Дуг
-4

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

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

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

шань
источник
ОП попросил словарь, который позволяет дублировать ключи.
Скапарате
-10

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

key1
Key1
КЛЮЧ1
ключом1
ключом1
ключом1

Я знаю, это глупый ответ, но работал на меня.

user4459653
источник
4
Нет, у тебя это не сработало. Словари допускают очень быстрый поиск - также классифицируемый как O (1) - по ключу. Вы теряете это, когда добавляете несколько ключей с различным регистром, потому что, как вы получаете их? Попробуйте каждую прописную / строчную комбинацию? Независимо от того, как вы это делаете, производительность не будет такой же, как при обычном поиске по одному словарю. Это в дополнение к другим, более очевидным недостаткам, таким как ограничение значений на ключ, в зависимости от количества символов в ключе, которые можно прописать.
Евгений Бересовский