Chaves duplicadas em dicionários .NET?

256

Existem classes de dicionário na biblioteca de classes base do .NET que permitem que chaves duplicadas sejam usadas? A única solução que encontrei é criar, por exemplo, uma classe como:

Dictionary<string, List<object>>

Mas isso é bastante irritante para realmente usar. Em Java, acredito que um MultiMap realiza isso, mas não consegue encontrar um analógico no .NET.

Caracol mecânico
fonte
3
Como é essa chave duplicada, seus valores duplicados (a Lista), certo?
Shamim Hafiz
1
@ShamimHafiz, não, os valores não precisam ser duplicados. Se você precisar armazenar duplicatas { a, 1 }e { a, 2 }em uma tabela de hash aa chave, uma alternativa é ter { a, [1, 2] }.
Nawfal
1
Na verdade, acredito que o que realmente se quer aqui é uma coleção em que cada chave possa mapear para um ou mais valores. Eu acho que a expressão "chaves duplicadas" realmente não transmite isso.
precisa saber é o seguinte
Para referência futura, considere manter 1 chave apenas adicionando os valores a ela, em vez de adicionar as mesmas chaves repetidamente.
Ya Wang
Se chaves e valores forem cadeias, haverá NameValueCollection (que pode associar vários valores de cadeia a cada chave de cadeia).
AnorZaken 03/04

Respostas:

229

Se você estiver usando o .NET 3.5, use o Lookup classe

EDIT: você geralmente cria um LookupusandoEnumerable.ToLookup . Isso pressupõe que você não precise alterá-lo posteriormente - mas normalmente acho que isso é bom o suficiente.

Se isso não funcionar para você, acho que não há nada na estrutura que ajude - e usar o dicionário é o melhor possível :(

Jon Skeet
fonte
Obrigado pelo aviso na pesquisa. Ele oferece uma ótima maneira de particionar (agrupar) resultados de uma consulta linq que não são critérios padrão de pedido por ordem.
Robert Paulson
3
@ Josh: Você usa Enumerable.ToLookup para criar um.
Jon Skeet
29
Palavra de cautela : Lookupnão é serializável
SliverNinja - MSFT
1
como devemos adicionar itens a essa pesquisa?
Moldovanu
171

A classe List realmente funciona muito bem para coleções de chave / valor que contêm duplicatas nas quais você deseja iterar sobre a coleção. Exemplo:

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);
}
John Saunders
fonte
31
Esta solução funciona funcionalmente, mas a implementação da lista não tem conhecimento da chave ou valor e otimizar hipocrisia procura de chaves em tudo
Spencer Rose
41

Aqui está uma maneira de fazer isso com 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);
}

Saídas k1 = v1, k1 = v2, k1 = v3

Hector Correa
fonte
Funciona muito bem no meu cenário e também fácil de usar.
user6121177
21

Se você estiver usando cadeias de caracteres como as chaves e os valores, poderá usar System.Collections.Specialized.NameValueCollection , que retornará uma matriz de valores de string por meio do método GetValues ​​(string string).

Matt
fonte
6
NameValueCollection não permite várias chaves.
Jenny O'Reilly
@ Jenny O'Reilly: Claro, você pode adicionar chaves duplicadas.
precisa saber é
Estritamente falando, @ JennyO'Reilly está correto, como afirma claramente as observações na página vinculada do MSDN: essa classe armazena vários valores de seqüência de caracteres em uma única chave .
Ronald
Isso permitirá, mas retornará vários valores, tentei usar o índice e a chave.
user6121177
18

Acabei de encontrar a biblioteca do PowerCollections , que inclui, entre outras coisas, uma classe chamada MultiDictionary. Isso envolve perfeitamente esse tipo de funcionalidade.


fonte
14

Nota muito importante sobre o uso da pesquisa:

Você pode criar uma instância de a Lookup(TKey, TElement)chamando ToLookupum objeto que implementaIEnumerable(T)

Não há construtor público para criar uma nova instância de a Lookup(TKey, TElement). Além disso, os Lookup(TKey, TElement)objetos são imutáveis, ou seja, você não pode adicionar ou remover elementos ou chaves de um Lookup(TKey, TElement)objeto depois que ele foi criado.

(do MSDN)

Eu acho que isso seria uma rolha de show para a maioria dos usos.

TheSoftwareJedi
fonte
6
Eu posso pensar em muito poucos usos em que isso seria uma rolha de exibição. Mas acho que objetos imutáveis ​​são ótimos.
Joel Mueller
1
@JoelMueller Eu posso pensar em muitos casos em que isso é um impedimento de exibição. Ter que re-criar um dicionário para adicionar um item não é uma solução particularmente eficiente ...
reirab
12

Eu acho que algo como List<KeyValuePair<object, object>>faria o trabalho.

MADMap
fonte
Como você procura algo nessa lista por sua chave?
Wayne Bloss
Você precisa fazer uma iteração: mas eu não conhecia a classe LookUp do .NET 3.5: talvez isso seja mais útil para pesquisar no conteúdo.
MADMap 28/09/08
2
@ wizlib: A única maneira é percorrer a lista, o que não é tão eficiente quanto o hash. -1
petr k.
@petrk. Isso realmente depende do que são seus dados. Eu usei essa implementação porque tinha muito poucas chaves exclusivas e não queria incorrer na sobrecarga de colisões de hash. 1
Evan M
9

Se você estiver usando> = .NET 4, poderá usar a TupleClasse:

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

fonte
Parece uma List<KeyValuePair<key, value>>solução como a acima. Estou errado?
21719 Nathan Goings
6

É fácil o suficiente "rolar sua própria" versão de um dicionário que permita entradas de "chave duplicada". Aqui está uma implementação simples e aproximada. Você pode considerar adicionar suporte para basicamente a maioria (se não todos) 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];
        }
    }
}

Um exemplo rápido de como usá-lo:

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
fonte
4

Em resposta à pergunta original. Algo como Dictionary<string, List<object>>é implementado em uma classe chamada MultiMapThe Code Project.

Você pode encontrar mais informações no link abaixo: http://www.codeproject.com/KB/cs/MultiKeyDictionary.aspx

Dan
fonte
3

O NameValueCollection oferece suporte a vários valores de string em uma chave (que também é uma string), mas é o único exemplo que eu conheço.

Costumo criar construções semelhantes à do seu exemplo quando encontro situações em que preciso desse tipo de funcionalidade.

ckramer
fonte
3

Ao usar a List<KeyValuePair<string, object>>opção, você pode usar o LINQ para fazer a pesquisa:

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
fonte
2
Sim, mas isso não o torna mais rápido (ainda sem hashing)
Haukman
3

Desde o novo C # (acredito que seja do 7.0), você também pode fazer algo assim:

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

e você está usando-o como uma lista padrão, mas com dois valores nomeados como quiser

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

Você quer dizer congruente e não uma duplicata real? Caso contrário, uma hashtable não seria capaz de funcionar.

Congruent significa que duas chaves separadas podem hash para o valor equivalente, mas as chaves não são iguais.

Por exemplo: digamos que a função hash da sua hashtable era apenas hashval = mod da chave 3. Ambos 1 e 4 são mapeados para 1, mas são valores diferentes. É aqui que a sua ideia de lista entra em jogo.

Quando você precisa procurar 1, esse valor é um hash para 1, a lista é percorrida até que a Chave = 1 seja encontrada.

Se você permitisse a inserção de chaves duplicadas, não conseguiria diferenciar quais chaves são mapeadas para quais valores.

Nicholas Mancuso
fonte
2
Uma tabela de hash já lida com chaves com o mesmo valor (isso é chamado de colisão). Estou me referindo a uma situação em que você deseja mapear vários valores para a mesma chave exata.
2

O jeito que eu uso é apenas um

Dictionary<string, List<string>>

Dessa forma, você tem uma única chave segurando uma lista de cadeias.

Exemplo:

List<string> value = new List<string>();
if (dictionary.Contains(key)) {
     value = dictionary[key];
}
value.Add(newValue);
Stefan Mielke
fonte
Isso é legal e limpo.
Jerry Nixon
Esta é uma ótima solução para lidar com meu caso de uso.
dub stylee
1

Eu tropecei neste post em busca da mesma resposta e não encontrei nenhuma, então montei uma solução de exemplo básico usando uma lista de dicionários, substituindo o operador [] para adicionar um novo dicionário à lista quando todos os outros tiverem um chave fornecida (conjunto) e retorne uma lista de valores (get).
É feio e ineficiente, apenas recebe / define por chave e sempre retorna uma lista, mas funciona:

 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
fonte
1

Alterei a resposta do @Hector Correa para uma extensão com tipos genéricos e também adicionei um TryGetValue personalizado.

  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
fonte
0

Este é um dicionário simultâneo de duas maneiras. Acho que isso ajudará você:

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

exemplos:

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
            }
Ali Yousefi
fonte
0

eu uso essa classe simples:

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

uso:

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

Você pode criar seu próprio wrapper de dicionário, algo como este, como um bônus que suporta valor nulo como chave:

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

A amostra de uso:

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 }
Alexander Tolstikov
fonte
Você pode dar uma explicação sobre o que seu código faz, como ele responde à pergunta e alguns exemplos de uso?
Enigmatividade
@Enigmativity, ele faz exatamente o que foi solicitado, a pergunta era sugerir algum dicionário que suporte duplicatas, então eu me ofereci para criar um wrapper em torno do dicionário .net que suportasse essa funcionalidade e, por exemplo, crie esse wrapper, como um bônus possível manipula nulo como uma chave (mesmo que seja uma má prática, com certeza) O uso é bastante simples: # 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 }
Alexander Tolstikov
Você pode adicionar os detalhes à sua resposta?
Enigmatividade
@Enigmativity, se você quer dizer que a resposta original, então tudo bem
Alexander Tolstikov
-1

Você pode definir um método para criar uma chave de cadeia de caracteres composta em todos os lugares em que você deseja usar o dicionário. Você deve usar esse método para criar sua chave, por exemplo:

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

para usar:

myDict.ContainsKey(keyBuilder(key1, key2))
Alireza Esrari
fonte
-3

Chaves duplicadas quebram todo o contrato do Dicionário. Em um dicionário, cada chave é única e mapeada para um único valor. Se você deseja vincular um objeto a um número arbitrário de objetos adicionais, a melhor aposta pode ser algo semelhante a um DataSet (na linguagem comum, uma tabela). Coloque suas chaves em uma coluna e seus valores na outra. Isso é significativamente mais lento que um dicionário, mas essa é sua desvantagem por perder a capacidade de fazer o hash dos objetos principais.

Ryan
fonte
5
O objetivo principal de usar um dicionário não é o ganho de desempenho? Usar um DataSet não parece melhor que uma List <KeyValuePair <T, U >>.
Doug
-4

Também isso é possível:

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

Dessa forma, podemos ter chaves únicas. Espero que funcione para voce.

Shan
fonte
O OP solicitou um dicionário que permita chaves duplicadas.
Skaparate 24/03
-10

Você pode adicionar as mesmas chaves com diferentes casos, como:

key1
Key1
KEY1
KeY1
kEy1
keY1

Eu sei que é uma resposta idiota, mas funcionou para mim.

user4459653
fonte
4
Não, não funcionou para você. Os dicionários permitem uma pesquisa muito rápida - também classificada como O (1) - por chave. Você perde isso quando adiciona várias chaves com caixas diferentes, porque como recuperá-las? Experimente todas as combinações de maiúsculas / minúsculas? Não importa como você o faça, o desempenho não será o da pesquisa normal de dicionário único. Isso além de outras deficiências mais óbvias, como a limitação de valores por chave, dependendo do número de caracteres disponíveis na chave.
Eugene Beresovsky