Chave de um dicionário pelo valor em C#: a forma mais rápida

O C# não tem uma forma nativa de encontrar a chave de um dicionário a partir do valor, então precisamos escrever essa busca nós mesmos. Quatro abordagens são comuns: criar um dicionário invertido, inverter o dicionário com ToLookup(), percorrer os pares chave-valor ou percorrer as chaves.

Para uma única busca, percorrer os pares chave-valor vence, e não aloca nada no processo. Inverter o dicionário só compensa quando buscamos chaves repetidamente em um dicionário que não muda, e medimos o desempenho dos dois casos abaixo.

Se precisamos do sentido oposto, um valor a partir de uma chave, a resposta é dict[key], TryGetValue() ou GetValueOrDefault(), que têm uma seção curta própria mais abaixo.

Um mesmo valor pode pertencer a várias chaves de um dicionário em C#?

Sim. Um Dictionary<TKey, TValue> exige unicidade apenas nas chaves. Adicionar a mesma chave duas vezes lança uma exceção, mas duas chaves diferentes podem ter o mesmo valor, e nada no tipo impede isso.

Uma chave tem no máximo um valor, então dict[key] pode retorná-lo. Um valor pode pertencer a nenhuma chave, a uma ou a cinquenta, então uma busca reversa honesta retorna uma coleção, e não uma única chave.

Todos os métodos aqui retornam apenas a primeira chave correspondente. “Primeira” significa primeira na ordem de enumeração, e um dicionário não garante nenhuma ordem: ela segue o histórico de inserções e a forma como as posições internas foram reaproveitadas depois de remoções. Com valores duplicados, a chave que recebemos é arbitrária.

Quando duplicatas são possíveis e queremos todas elas, a resposta é filtrar em vez de buscar: manter todos os pares cujo valor corresponde e retornar essas chaves.

Vamos criar quatro métodos de busca reversa em dicionário, cada um em sua própria seção:

• Com um dicionário invertido
• Com um Lookup invertido
• Iteração pelos pares chave-valor do dicionário
• Iteração pelas chaves do dicionário

Muitos leitores chegam aqui precisando do sentido oposto, um valor a partir da chave, então tratamos disso antes de criar os métodos.

Como obter o valor de um dicionário pela chave em C#?

O sentido direto é o que a linguagem nos oferece, e há três chamadas para ele.

O indexador, dict[key], retorna o valor e lança KeyNotFoundException quando a chave não existe. Use-o quando uma chave ausente for um bug.

dict.TryGetValue(key, out var value) retorna false em vez de lançar exceção e entrega o valor pelo parâmetro out. Use-o quando uma chave ausente for esperada, o que acontece na maioria das vezes.

O método de extensão dict.GetValueOrDefault(key) retorna default(TValue) para uma chave ausente, ou um valor alternativo que passamos como segundo argumento.

As três têm tempo constante em média: o dicionário calcula o hash da chave e vai direto ao bucket dela, então o tamanho do dicionário não importa.

É exatamente isso que não conseguimos fazer no sentido inverso. Os valores não passam por hash nem são indexados, então encontrar uma chave pelo valor significa examinar os pares um por um. Tudo o que vem a seguir trata de fazer isso da forma mais barata possível.

Cada um desses temas tem um artigo próprio e completo: como verificar se uma chave existe antes de lê-la, como retornar um valor padrão de um dicionário e como um Dictionary<TKey, TValue> armazena seus pares, para começo de conversa.

Como inverter um dicionário para buscar uma chave?

Quando nos deparamos com essa tarefa pela primeira vez, uma solução rápida que vem à mente é criar logo outro dicionário que tenha os valores do dicionário original como chaves e as chaves como valores. Depois, com os valores originais como chaves nesse novo dicionário, chamamos o método TryGetValue() para obter a chave desejada.

Os quatro métodos ficam em uma classe DictionaryHelper que recebe o dicionário e o valor a buscar como parâmetros do construtor primário, então dict e value em todos os trechos de código abaixo são esses dois parâmetros:

public class DictionaryHelper(Dictionary<string, string> dict, string value)
{

Essa abordagem é viável, então vamos implementar um método que faz isso:

public string? UseReverseDictionary()
{
    var reverseDict = new Dictionary<string, string>();
    foreach (var keyValuePair in dict)
    {
        reverseDict.TryAdd(keyValuePair.Value, keyValuePair.Key);
    }

    reverseDict.TryGetValue(value, out var key);

    return key;
}

Primeiro, criamos um objeto Dictionary<TKey, TValue>. Depois, iteramos pelos pares chave-valor, adicionando os valores originais como chaves e as chaves como valores. Usar o método TryAdd() garante que a adição corra bem, sem exceções, quando tentarmos adicionar chaves duplicadas. Se tentarmos adicionar uma chave duplicada, TryAdd() retorna false sem modificar o dicionário, e seguimos para o próximo KeyValuePair.

Depois disso, chamamos o método TryGetValue() no dicionário invertido para obter a chave associada ao valor especificado. Se encontramos esse valor no dicionário, guardamos a chave correspondente no parâmetro out, key. Caso contrário, guardamos o valor padrão para strings (null) no argumento key. Por fim, retornamos o valor de key.

Com um Lookup invertido

O método ToLookup() nos dá outra forma de inverter o dicionário:

public string? UseReverseLookup()
{
    var reverseLookup = dict.ToLookup(x => x.Value, x => x.Key);

    return reverseLookup[value].FirstOrDefault();
}

Aqui, chamamos no dicionário o método de extensão ToLookup() do LINQ. Instruímos o método a pegar os valores e as chaves do dicionário de entrada e inseri-los, respectivamente, como chaves e valores em uma nova instância de Lookup<TKey, TElement>.

Um Lookup é parecido com um Dictionary porque armazena chaves e os valores associados a elas. No entanto, ao contrário de objetos Dictionary, um Lookup pode mapear uma única chave para uma coleção de valores.

Agora, depois de criar o Lookup, acessamos a coleção de chaves mapeadas para o valor de entrada e retornamos a primeira chave, ou null se o valor não existir.

Obter a chave de um dicionário percorrendo os KeyValuePairs

O terceiro método itera pelos pares chave-valor do dicionário:

public string? LoopThroughKeyValuePairs()
{
    foreach (var keyValuePair in dict)
    {
        if (keyValuePair.Value == value)
        {
            return keyValuePair.Key;
        }
    }

    return default;
}

No loop foreach, percorremos todos os pares do dicionário em busca de um valor igual ao valor de entrada. Assim que encontramos uma correspondência, retornamos a chave dela. Percorrer os pares com foreach é uma opção entre várias, e explicamos as outras formas de iterar por um dicionário em um artigo separado.

Se chegamos ao fim do loop sem encontrar um valor correspondente, retornamos o valor default para strings.

Iterar pelas chaves do dicionário

Da mesma forma, podemos iterar pelas chaves do dicionário:

public string? LoopThroughKeys()
{
    foreach (var key in dict.Keys)
    {
        if (dict[key] == value)
        {
            return key;
        }
    }

    return default;
}

Neste caso, passamos cada chave ao indexador para encontrar um valor igual ao valor de entrada. Se o valor de alguma chave corresponder, retornamos essa chave. Caso contrário, retornamos default. 

Como os quatro métodos se comparam em velocidade e memória?

Em um dicionário de 100.000 pares, na busca por um valor que não existe nele, as duas varreduras superam os dois métodos que invertem o dicionário.

Percorrer os pares chave-valor é o mais rápido e não aloca nada. Um único foreach percorre as entradas do dicionário e compara cada valor.

Percorrer as chaves leva cerca de 8,5 vezes mais tempo para dar a mesma resposta. Cada iteração lê uma chave e depois busca essa chave de novo pelo indexador, então cada item é pago duas vezes.

Criar um dicionário invertido é ainda mais lento, cerca de 25 vezes o tempo da varredura dos pares, e aloca uma segunda cópia do dicionário inteiro.

Inverter com ToLookup() é o mais lento e o que mais consome memória. Um Lookup agrupa as chaves por valor distinto, então um dicionário com 100.000 valores distintos significa 100.000 agrupamentos a alocar.

Esses números medem uma única busca, e os dois métodos que invertem o dicionário gastam todo o tempo criando um índice que depois usam exatamente uma vez.

Medimos o desempenho desses métodos com o pacote BenchmarkDotNet. Se você não conhece esse pacote e quer aprender a medir o desempenho de métodos com ele, confira nossa introdução ao benchmark de projetos C#.

Para garantir a precisão das conclusões que tiramos do benchmark, vamos executá-lo com um dicionário de 100000 itens e tentar obter a chave de um valor inexistente. Tentar obter a chave de um valor existente no benchmark pode distorcer os resultados, porque não podemos garantir a ordem dos pares no dicionário. A referência de Dictionary<TKey,TValue> no Microsoft Learn diz isso em uma frase: “A ordem em que os itens são retornados é indefinida.”

Nesse caso, o valor que queremos encontrar pode ser o primeiro item do dicionário, e o obteríamos rapidamente. Ao buscar um valor inexistente, simulamos a situação em que os quatro métodos precisam passar por todos os itens do dicionário para obter a chave desejada.

Resultado do benchmark

Para ver a implementação da classe de benchmark, consulte o código-fonte.

A execução no .NET 10 produziu estes resultados:

BenchmarkDotNet v0.15.8, Windows 10 (10.0.19045.6466/22H2/2022Update)
AMD Ryzen 5 3600 3.60GHz, 1 CPU, 12 logical and 6 physical cores
.NET SDK 10.0.302
  [Host]     : .NET 10.0.10 (10.0.10, 10.0.1026.32716), X64 RyuJIT x86-64-v3
  DefaultJob : .NET 10.0.10 (10.0.10, 10.0.1026.32716), X64 RyuJIT x86-64-v3

| Method                       | Mean              | Gen0      | Gen1      | Gen2     | Allocated  |
|----------------------------- |------------------:|----------:|----------:|---------:|-----------:|
| UsePrebuiltFrozenDictionary  |          1.984 ns |         - |         - |        - |          - |
| UsePrebuiltReverseDictionary |          6.534 ns |         - |         - |        - |          - |
| LoopThroughTheKeyValuePairs  |    173,944.209 ns |         - |         - |        - |          - |
| LoopThroughTheKeys           |  1,483,338.770 ns |         - |         - |        - |          - |
| UseReverseDictionary         |  4,365,652.930 ns |  390.6250 |  367.1875 | 367.1875 |  8452771 B |
| UseReverseLookup             | 27,954,562.740 ns | 1500.0000 | 1468.7500 | 437.5000 | 10897731 B |

As duas linhas do topo, com o mapa pré-construído, medem apenas a busca em um mapa invertido criado com antecedência, não a criação dele, então vamos deixá-las de lado até a próxima seção.

Como vemos pelos resultados do benchmark, a forma mais rápida de obter a chave de um dicionário pelo valor em C# é iterar pelos pares chave-valor do dicionário. Esse método ainda tem a vantagem de evitar alocação adicional de memória e, com isso, uma possível coleta de lixo.

Em seguida, a segunda forma mais rápida de realizar essa tarefa é iterar pelas chaves do dicionário. Ela também não aloca nada, mas leva cerca de 8,5 vezes o tempo do primeiro método.

Depois desses métodos, vem o que inverte o dicionário manualmente. Com ele, temos o segundo maior tempo de execução e a segunda maior taxa de coleta de lixo, por causa da quantidade significativa de memória gerenciada que ele aloca (basicamente duplicando o dicionário original).

Por fim, a forma mais lenta de obter a chave de um dicionário pelo valor em C# é chamar o método ToLookup() para inverter o dicionário. Esse método é o que consome mais memória e o que aciona o coletor de lixo com mais frequência. Isso acontece porque criamos muitas chaves e as coleções de valores correspondentes para cada objeto Lookup.

Qual abordagem usar, e quando?

A comparação responde a uma pergunta: qual método vence quando buscamos uma chave, uma única vez. Os dois métodos que invertem o dicionário perdem porque pagam para criar um índice e depois o usam uma vez só.

Mude a pergunta para buscas repetidas e a resposta se inverte. Um dicionário invertido é criado uma vez e responde a todas as buscas seguintes em tempo constante, enquanto uma varredura paga até uma passada completa por chamada.

Portanto, a escolha depende de quantas buscas um mapa invertido atenderia. Para uma única busca, ou para um dicionário que não para de mudar, percorremos os pares chave-valor. Para muitas buscas em um dicionário estável, criamos o mapa invertido uma vez e o mantemos.

Os valores duplicados definem o formato desse mapa. Com valores únicos, um Dictionary<TValue, TKey> basta. Com duplicatas, ToLookup() é, afinal, a ferramenta certa, porque mantém todas as chaves de cada valor em vez de descartar silenciosamente todas menos uma.

A tabela coloca as quatro abordagens lado a lado, com o custo de uma busca e a situação em que cada uma se encaixa.

Criar o dicionário invertido custa aproximadamente o mesmo que 25 varreduras (4.365.653 ns contra 173.944 ns na saída acima), e cada busca posterior nele leva cerca de 6,5 ns, o que é desprezível perto de qualquer um dos dois. Então, por volta da 26ª busca, o dicionário invertido passa à frente, e a vantagem dele cresce a cada busca seguinte.

Se o mapa invertido nunca mais vai mudar, ToFrozenDictionary() troca uma criação mais lenta por leituras mais rápidas que as de um Dictionary<TKey, TValue> ao procurar o nosso valor inexistente: 1,98 ns contra 6,53 ns por busca na saída acima, porque esse valor é mais longo que qualquer valor do mapa. Para os valores que o mapa contém, o dicionário congelado é mais lento em média.

Conclusão

Percorrer os pares chave-valor é o mais rápido dos quatro métodos para uma única busca, e não aloca nada. Para buscas repetidas em um dicionário que não muda, um dicionário invertido criado uma vez passa à frente a partir da 26ª busca, aproximadamente. Quando os valores se repetem, ToLookup() é o mapa invertido a criar, porque mantém todas as chaves que compartilham um valor.

Testado com .NET 10.0.10 e BenchmarkDotNet 0.15.8.