Usando el diccionario <Foo, Foo> en lugar de la lista <Foo> para acelerar las llamadas a los contenedores()

Question

Tengo una pregunta acerca de las colecciones genéricas en C#. Si necesito almacenar una colección de artículos, y con frecuencia voy a necesitar verificar si un artículo está en la colección, ¿sería más rápido usar el diccionario en lugar de la lista?

He oído que comprobar si un artículo está en la colección es lineal en relación con el tamaño de las listas y constante en relación con el tamaño de los diccionarios. ¿Está utilizando Dictionary y luego estableciendo Key y Value en el mismo objeto para cada par de clave-valor, algo que otros programadores hacen frecuentemente en esta situación?

Gracias por tomarse el tiempo para leer esto.

Answer 1

Sí, sí lo es. Dicho esto, es probable que desee utilizar HashSet porque no necesita una clave y un valor, solo necesita un conjunto de elementos.

Es también digno de mención que Dictionary se añadió en C# 2.0, y HashSet se añadió en 3,5, por lo que durante todo ese tiempo entre medio era en realidad bastante común el uso de un diccionario cuando se quería un Conjunto sólo porque eso era todo lo que tenía (sin rodar el suyo). Cuando me forzaron a hacer esto, simplemente puse nulo en el valor, en lugar del elemento como la clave y el valor, pero la idea es la misma.

Answer 2

Simplemente use HashSet<Foo> si lo que le preocupa son las pruebas de contención rápida.

A Dictionary<TKey, TValue> es para ver un valor basado en una clave.

A List<T> es para acceso aleatorio y propiedades de crecimiento dinámico.

A HashSet<T> es para modelar un conjunto y proporcionar pruebas de contención rápidas.

No está buscando un valor basado en una clave. No le preocupa el acceso aleatorio, sino controles de contención rápidos. El concepto correcto aquí es un HashSet<T>.

Answer 3

Un diccionario o HashSet utilizará más memoria, pero proporcionará (casi) O (1) tiempo de búsqueda.

Answer 4

Suponiendo que solo haya una copia del elemento en la lista, la estructura de datos adecuada es ISet<T>, específicamente HashSet<T>.

Dicho esto, he visto un tiempo que indica que una llamada Dictionary<TKey, TValue>ContainsKey es un poquito más rápida que incluso HashSet<T>. De cualquier forma, ambos serán más rápidos que una simple búsqueda List<T>.

Tenga en cuenta que estos dos métodos (hashset y diccionario) se basan en razonablemente bien implementadas Equals yGetHashcode implementaciones de T. List<T> solo depende de Equals

Answer 5

Es posible que desee mirar HashSet, que es una colección de objetos únicos (siempre que el objeto implemente el comparador de igualdad de IE).

Answer 6

Menciona usando List<T>, lo que implica que el orden puede ser importante. Si este es el caso, es posible que también desee buscar en el tipo SortedSet<T>.