¿Cuál es la mejor estructura de datos en .NET para la búsqueda por clave de cadena o índice numérico?

Question

Estoy buscando la estructura de datos más ideal (para el rendimiento y la facilidad de uso) a partir de la cual los valores se pueden recuperar por clave de cadena o índice. El diccionario no funciona porque realmente no se puede recuperar por índice. ¿Alguna idea?

Answer 1

Desea la clase OrderedDictionary . Deberá incluir System.Collections.Specialized namespace:

    OrderedDictionary od = new OrderedDictionary(); 
    od.Add("abc", 1); 
    od.Add("def", 2); 
    od.Add("ghi", 3); 
    od.Add("jkl", 4); 

    // Can access via index or key value:      
    Console.WriteLine(od[1]);       
    Console.WriteLine(od["def"]);

Answer 2

Hay System.Collections.ObjectModel. KeyedCollection < cadena, TItem > , que deriva de la Colección < TItem & Gt ;. La recuperación es O (1) .

class IndexableDictionary<TItem> : KeyedCollection<string, TItem>
 { Dictionary<TItem, string> keys = new Dictionary<TItem, string>();

   protected override string GetKeyForItem(TItem item) { return keys[item];}

   public void Add(string key, TItem item) 
    { keys[item] = key;
      this.Add(item);
    }
 }

Answer 3

Una palabra de advertencia. El OrderedDictionary tiene realmente malas características de rendimiento para la mayoría de las operaciones, excepto la inserción y la búsqueda: tanto la eliminación como la modificación de un valor pueden requerir una búsqueda lineal de toda la lista, lo que resulta en tiempo de ejecución O ( n ). (Para modificaciones, esto depende de si el acceso se produjo por índice o por clave).

Para la mayoría de las operaciones con cantidades razonables de datos, esto es completamente inaceptable. Además, la estructura de datos almacena elementos tanto en un vector lineal como en una tabla hash, lo que genera cierta sobrecarga de memoria.

Si la recuperación por índice no ocurre con demasiada frecuencia, un SortedList o SortedDictionary tendrá características de rendimiento mucho mejores (el acceso por índice se puede lograr a través de el ElementAt método de extensión).

Si, por otro lado, el acceso por índice es la norma, entonces deje de usar las estructuras de datos del diccionario y simplemente almacene sus valores en un List<KeyValuePair<TKey, TValue>> . Aunque esto significa una búsqueda lineal de acceso por clave, todas las demás operaciones son muy baratas y el rendimiento general es difícil de superar en la práctica.

/ EDITAR: Por supuesto, este último también es una estructura de datos de diccionario en el sentido teórico. Incluso podría encapsularlo en una clase que implemente la interfaz adecuada.

Answer 4

Las colecciones basadas en hash (Dictionary, Hashtable, HashSet) están fuera porque no tendrá un índice, ya que desea un índice, usaría un genérico anidado:

List<KeyValuePair<K,V>>

Por supuesto, pierde la búsqueda de la tecla O (1) que obtiene con los hashes.

Answer 5

Un diccionario podría funcionar con linq. Aunque no sé sobre posibles problemas de rendimiento. Dictionary.ElementAt (index);

Answer 6

Recomiendo usar SortedDictionary < string, TValue > o SortedList < string, TValue > ;. Ambos tienen un rendimiento de búsqueda O (log n).

Las diferencias son, como se cita de la biblioteca MSDN :

  

SortedList < (Of   < (TKey, TValue >) >) usa menos memoria   que SortedDictionary < (Of < (TKey,   TValue & Gt;) & Gt;).

     

SortedDictionary < (Of < (TKey,   TValue & Gt;) & Gt;) tiene una inserción más rápida y   operaciones de eliminación de datos sin clasificar:   O (log n) en oposición a O (n) para   SortedList & Lt; (Of & Lt; (TKey, TValue & Gt;) & Gt;).

     

Si la lista se completa de una vez   de datos ordenados, SortedList < (Of   < (TKey, TValue >) >) es más rápido que   SortedDictionary & Lt; (Of & Lt; (TKey,   TValue & Gt;) & Gt;).

En mi experiencia, SortedDictionary es más adecuado para la mayoría de los escenarios empresariales típicos, ya que los datos generalmente no se clasifican inicialmente cuando se usan estructuras como esta, y la sobrecarga de memoria de SortedDictionary rara vez es crítica. Pero si el rendimiento es clave para usted, le sugiero que implemente ambos y realice mediciones.

Answer 7

Está buscando algo como Clase SortedList (aquí está la versión genérica también ).