La forma más rápida de obtener la clave de un diccionario por valor en C#

C# no tiene una forma integrada de encontrar la clave de un diccionario a partir de su valor, así que la escribimos nosotros. Hay cuatro enfoques de uso habitual: crear un diccionario inverso, invertir el diccionario con ToLookup(), recorrer los pares clave-valor o recorrer las claves.

Para una sola búsqueda, recorrer los pares clave-valor es lo más rápido, y además no asigna nada de memoria. Invertir el diccionario solo compensa cuando buscamos claves repetidamente en un diccionario que no cambia, y más abajo medimos ambos casos con benchmarks.

Si lo que necesitamos es el sentido contrario, un valor a partir de una clave, la respuesta es dict[key], TryGetValue() o GetValueOrDefault(), y la tratamos en su propia sección breve más abajo.

¿Puede un mismo valor pertenecer a varias claves de un diccionario en C#?

Sí. Un Dictionary<TKey, TValue> solo exige que las claves sean únicas. Agregar la misma clave dos veces lanza una excepción, pero dos claves distintas pueden tener el mismo valor, y nada en el tipo lo impide.

Una clave tiene como máximo un valor, así que dict[key] puede devolverlo. Un valor puede pertenecer a ninguna clave, a una o a cincuenta, así que una búsqueda inversa honesta devuelve una colección y no una sola clave.

Todos los métodos que vemos aquí devuelven solo la primera clave que coincide. “Primera” quiere decir primera en el orden de enumeración, y un diccionario no promete ningún orden: el orden depende del historial de inserciones y de cómo se reutilizaron las posiciones internas después de las eliminaciones. Con valores duplicados, la clave que obtenemos es arbitraria.

Cuando puede haber duplicados y los queremos todos, la respuesta es un filtro en lugar de una búsqueda: conservar todos los pares cuyo valor coincide y devolver sus claves.

Creamos cuatro métodos para buscar en un diccionario de forma inversa, cada uno en su propia sección:

• Con un diccionario inverso
• Con un Lookup inverso
• Recorrer los pares clave-valor del diccionario
• Recorrer las claves del diccionario

Muchos lectores llegan aquí buscando el sentido contrario, un valor a partir de su clave, así que lo tratamos antes de crear los métodos.

¿Cómo obtener el valor de un diccionario por su clave en C#?

El sentido habitual es el que nos da el lenguaje, y hay tres llamadas para ello.

El indexador, dict[key], devuelve el valor y lanza KeyNotFoundException cuando la clave no existe. Úsalo cuando la ausencia de una clave indique un error.

dict.TryGetValue(key, out var value) devuelve false en lugar de lanzar una excepción y entrega el valor a través del parámetro out. Úsalo cuando sea normal que falte una clave, que es lo que ocurre la mayoría de las veces.

El método de extensión dict.GetValueOrDefault(key) devuelve default(TValue) cuando falta la clave, o un valor alternativo que pasamos como segundo argumento.

Las tres son de tiempo constante en promedio: el diccionario calcula el hash de la clave y va directamente a su cubeta (bucket), así que el tamaño del diccionario no importa.

Eso es justo lo que no podemos hacer en sentido inverso. Los valores no tienen hash ni índice, así que encontrar una clave por su valor implica revisar los pares uno por uno, y todo lo que sigue trata de cómo hacerlo de la forma más barata posible.

Cada una de estas llamadas tiene su propio artículo detallado: comprobar si una clave existe antes de leerla, devolver un valor predeterminado de un diccionario y cómo almacena un Dictionary<TKey, TValue> sus pares.

¿Cómo invertir un diccionario para buscar una clave?

La primera vez que nos enfrentamos a esta tarea, una solución rápida que podríamos plantear es crear de inmediato otro diccionario que tenga como claves los valores del diccionario original y como valores sus claves. Después, con los valores originales como claves en este nuevo diccionario, invocamos el método TryGetValue() para obtener la clave deseada.

Los cuatro métodos están en una clase DictionaryHelper que recibe el diccionario y el valor que hay que buscar como parámetros del constructor principal, así que dict y value, en todos los fragmentos de código siguientes, son esos dos parámetros:

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

Este enfoque es viable, así que vamos a implementar un método que lo haga:

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

Primero, creamos un objeto Dictionary<TKey, TValue>. Después, recorremos los pares clave-valor y agregamos los valores originales como claves y las claves como valores. Usar el método TryAdd() garantiza que la inserción transcurra sin excepciones cuando intentamos agregar claves duplicadas. Si intentamos agregar una clave duplicada, TryAdd() devuelve false sin modificar el diccionario, y pasamos al siguiente KeyValuePair.

Después, llamamos al método TryGetValue() sobre el diccionario inverso para obtener la clave asociada al valor indicado. Si encontramos este valor en el diccionario, guardamos su clave en el parámetro out, key. En caso contrario, guardamos el valor predeterminado de las cadenas (null) en el argumento key. Por último, devolvemos el valor de key.

Con un Lookup inverso

El método ToLookup() nos ofrece otra forma de invertir el diccionario:

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

    return reverseLookup[value].FirstOrDefault();
}

Aquí, invocamos sobre el diccionario el método de extensión ToLookup() de LINQ. Le indicamos que tome los valores y las claves del diccionario de entrada y los incorpore, respectivamente, como claves y valores en una nueva instancia de Lookup<TKey, TElement>.

Un Lookup se parece a un Dictionary en que almacena claves y sus valores asociados. Sin embargo, a diferencia de los objetos Dictionary, un Lookup puede asociar una misma clave a una colección de valores.

Ahora, después de crear el Lookup, accedemos a la colección de claves asociadas a nuestro valor de entrada y devolvemos la primera clave, o null si el valor no existe.

Obtener una clave del diccionario recorriendo los pares KeyValuePair

El tercer método recorre los pares clave-valor del diccionario:

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

    return default;
}

En el bucle foreach, recorremos todos los pares del diccionario buscando un valor que coincida con nuestro valor de entrada. En cuanto encontramos una coincidencia, devolvemos su clave. Recorrer los pares con foreach es una opción entre varias, y explicamos las otras formas de recorrer un diccionario en un artículo aparte.

Si al terminar el bucle no hemos encontrado ningún valor que coincida, devolvemos el valor default de las cadenas.

Recorrer las claves del diccionario

Del mismo modo, podemos recorrer las claves del diccionario:

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

    return default;
}

En este caso, pasamos cada clave al indexador para encontrar un valor igual a nuestro valor de entrada. Si el valor de alguna clave coincide, devolvemos esa clave. En caso contrario, devolvemos default. 

¿Cómo se comparan los cuatro métodos en velocidad y memoria?

En un diccionario de 100 000 pares, al buscar un valor que no existe, los dos recorridos superan a los dos métodos que invierten el diccionario.

Recorrer los pares clave-valor es lo más rápido y no asigna memoria. Un solo bucle foreach recorre las entradas del diccionario y compara cada valor.

Recorrer las claves tarda unas 8.5 veces más para obtener la misma respuesta. Cada iteración lee una clave y luego vuelve a buscarla mediante el indexador, así que cada elemento se paga dos veces.

Crear un diccionario inverso es aún más lento, unas 25 veces lo que tarda el recorrido de pares, y asigna una segunda copia de todo el diccionario.

Invertir con ToLookup() es lo más lento y lo que más memoria consume. Un Lookup agrupa las claves por cada valor distinto, así que un diccionario con 100 000 valores distintos implica asignar 100 000 agrupaciones.

Estos números miden una sola búsqueda, y los dos métodos que invierten el diccionario dedican todo su tiempo a construir un índice que luego usan exactamente una vez.

Medimos el rendimiento de estos métodos con el paquete BenchmarkDotNet. Si no conoces este paquete y quieres aprender a medir el rendimiento de métodos con él, consulta nuestra introducción a los benchmarks en proyectos de C#.

Para garantizar la precisión de las conclusiones que sacamos del benchmark, lo ejecutaremos con un diccionario de 100000 elementos e intentaremos obtener la clave de un valor inexistente. Intentar obtener la clave de un valor existente en el benchmark puede dar resultados sesgados, porque no podemos garantizar el orden de los pares en el diccionario. La referencia de Dictionary<TKey,TValue> en Microsoft Learn lo dice en una sola frase: “El orden en que se devuelven los elementos no está definido”.

En esos casos, el valor que queremos obtener podría ser el primer elemento del diccionario, y lo obtendríamos rápidamente. Al buscar un valor inexistente, simulamos el caso en el que los cuatro métodos tienen que recorrer todos los elementos del diccionario para obtener la clave deseada.

Resultado del benchmark

Para ver la implementación de la clase del benchmark, consulta el código fuente.

La ejecución en .NET 10 dio estos 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 |

Las dos primeras filas, con el mapa inverso ya construido, miden solo la búsqueda en ese mapa y no su construcción, así que las dejamos de lado hasta la siguiente sección.

Como vemos en los resultados del benchmark, la forma más rápida de obtener la clave de un diccionario por su valor en C# es recorrer los pares clave-valor del diccionario. Este método tiene además la ventaja de evitar asignaciones de memoria adicionales y, por tanto, una posible recolección de basura.

Después, la segunda forma más rápida de hacerlo es recorrer las claves del diccionario. Tampoco asigna memoria, pero tarda unas 8.5 veces lo que tarda el primer método.

A continuación aparece el método que invierte el diccionario manualmente. Con él obtenemos el segundo tiempo de ejecución más alto y la segunda tasa de recolección de basura más alta, debido a la gran cantidad de memoria administrada que asigna (básicamente, duplica el diccionario original).

Por último, la forma más lenta de obtener la clave de un diccionario por su valor en C# es invocar el método ToLookup() para invertir el diccionario. Este método es el que más memoria consume y el que recurre con más frecuencia al recolector de basura. Esto se debe a que, en cada objeto Lookup, creamos muchas claves, cada una con su colección de valores correspondiente.

¿Qué enfoque conviene usar y cuándo?

La comparación responde a una sola pregunta: qué método gana cuando buscamos una clave una sola vez. Los dos métodos que invierten el diccionario pierden porque pagan por construir un índice y luego lo usan una sola vez.

Si la pregunta es sobre búsquedas repetidas, la respuesta se invierte. Un diccionario inverso se construye una vez y responde a cada búsqueda posterior en tiempo constante, mientras que un recorrido paga como máximo una pasada completa por llamada.

Así que la elección depende de cuántas búsquedas atendería un mismo mapa inverso. Para una búsqueda, o para un diccionario que va cambiando mientras lo usamos, recorremos los pares clave-valor. Para muchas búsquedas en un diccionario estable, construimos el mapa inverso una vez y lo conservamos.

Los valores duplicados determinan la forma de ese mapa. Con valores únicos, basta con un Dictionary<TValue, TKey>. Con duplicados, ToLookup() resulta ser la herramienta adecuada, porque conserva todas las claves de cada valor en lugar de descartar sin ningún aviso todas menos una.

La tabla muestra los cuatro enfoques uno junto a otro, según lo que cuesta una búsqueda y cuándo encaja cada uno.

Construir el diccionario inverso cuesta aproximadamente lo mismo que 25 recorridos (4 365 653 ns frente a 173 944 ns en la salida anterior), y cada búsqueda posterior a través de él tarda unos 6.5 ns, algo insignificante al lado de cualquiera de las dos cifras. Así que, en torno a la búsqueda número 26, el diccionario inverso pasa por delante, y su ventaja crece con cada búsqueda posterior.

Si el mapa inverso ya no va a cambiar, ToFrozenDictionary() sacrifica velocidad de construcción a cambio de lecturas más rápidas que las de un Dictionary<TKey, TValue> con nuestro valor inexistente: 1.98 ns frente a 6.53 ns por búsqueda en la salida anterior, porque ese valor es más largo que cualquier valor del mapa. Con los valores que sí están en el mapa, el diccionario congelado es más lento en promedio.

Conclusión

Recorrer los pares clave-valor es el más rápido de los cuatro métodos para una sola búsqueda, y no asigna memoria. Para búsquedas repetidas en un diccionario que no cambia, un diccionario inverso construido una sola vez se adelanta a partir de la búsqueda número 26, aproximadamente. Cuando los valores se repiten, ToLookup() es el mapa inverso que conviene construir, porque conserva todas las claves que comparten un valor.

Probado con .NET 10.0.10 y BenchmarkDotNet 0.15.8.