146 votos

¿Las estructuras de datos de .net: ArrayList, lista, HashTable, Dictionary, SortedList, SortedDictionary--velocidad, memoria y cuándo usar cada uno?

.Net tiene un montón de estructuras de datos complejas. Por desgracia, algunos de ellos son muy similares y no siempre estoy seguro de cuándo usar uno y cuando uso otro. La mayor parte de mi C# y VB libros hablan acerca de ellos, hasta cierto punto, pero nunca ir en cualquier reales detalle.

¿Cuál es la diferencia entre la Matriz, ArrayList, Lista, tabla Hash, Diccionario, SortedList, y SortedDictionary?

Cuáles son enumerables (IList -- puede hacer 'foreach' bucles)? Que el uso de pares clave/valor (IDict)?

¿Qué sobre la memoria de la huella? La velocidad de inserción? La recuperación de la velocidad?

Existen otras estructuras de datos que vale la pena mencionar?

EDIT: aún sigo buscando más detalles sobre el uso de la memoria y de la velocidad (Big-O la notación)

106voto

Sam Schutte Puntos 2962

La parte superior de mi cabeza:

Array - , representa una de la vieja escuela matriz de memoria - algo así como un alias para un normal type[] de la matriz. Puede enumerar. No se puede crecer de forma automática. Quiero suponer muy rápida inserción y retriv. velocidad.

ArrayList - aumento automático de la matriz. Añade más gastos. Puede enum., probablemente más lento que una matriz normal, pero aún así es bastante rápido. Estos se utilizan mucho en .NET

List - uno de mis favoritos - puede ser utilizado con los genéricos, así que usted puede tener un establecimiento inflexible de tipos de matriz, por ejemplo. List<string>. Aparte de eso, actúa muy parecido ArrayList.

Hashtable - plain old hashtable. O(1) O(n) en el peor caso. Puede enumerar el valor y las teclas de propiedades, y hacer de clave/val pares.

Dictionary - igual que el anterior sólo inflexible a través de los genéricos, tales como Dictionary<string, string>

SortedList - una ordenada la lista genérica. Se desaceleró en la inserción, ya que tiene que averiguar dónde poner las cosas. Puede enum., probablemente la misma en la recuperación, ya que no tiene que recurrir, pero la eliminación es más lenta que una simple lista anterior.

Yo tiendo a usar List y Dictionary todo el tiempo - una vez que usted comience a usar ellos inflexible con los genéricos, es realmente duro para volver a la norma de la no-generic.

Hay un montón de otras estructuras de datos también - hay KeyValuePair , que puede utilizar para hacer algunas cosas interesantes, hay un SortedDictionary que puede ser útil así.

16voto

blackwing Puntos 1492

Aquí hay algunos consejos generales para usted:

  • Usted puede utilizar foreach en los tipos que implementan IEnumerable. IList es esencialmente un IEnumberable con Count y Item (acceder a los elementos con un índice basado en cero) propiedades. IDictionary en el otro lado significa que usted puede obtener acceso a los elementos por cualquier hashable índice.

  • Array, ArrayList, List y SortedList todas implementar IList. Dictionary, SortedDictionaryy Hashtable implementar IDictionary.

  • Si usted está usando .NET 2.0 o superior, se recomienda el uso de equivalentes genéricos de los tipos mencionados.

  • Para el tiempo y el espacio de la complejidad de las diversas operaciones sobre estos tipos, usted debe consultar su documentación.

  • .NET las estructuras de datos están en System.Collections de espacio de nombres. Hay bibliotecas de tipos, tales como PowerCollections que ofrecen las estructuras de datos.

  • Para obtener una comprensión completa de las estructuras de datos, consulte recursos como la CLR.

15voto

Adam Tegen Puntos 8563

Si es posible, utilizar genéricos. Esto incluye:

  • La lista en lugar de ArrayList
  • Diccionario en vez de HashTable

15voto

Abe Heidebrecht Puntos 16417

En primer lugar, en todas las colecciones en .NET implemente IEnumerable.

Segundo, muchas de las colecciones son duplicados debido a que los medicamentos genéricos fueron agregados en la versión 2.0 del framework.

Así que, a pesar de las colecciones genéricas probable agregar características, para la mayoría de la parte:

  • La lista es una implementación genérica de ArrayList.
  • El diccionario es una implementación genérica de Hashtable

Las matrices son de un tamaño fijo de la colección que se puede cambiar el valor almacenado en un determinado índice.

SortedDictionary es un IDictionary que se ordena en función de las claves. SortedList es un IDictionary que se ordena en función de una necesaria IComparer.

Así, el IDictionary implementaciones (aquellos que apoyan KeyValuePairs) son: * Hashtable * Diccionario * SortedList * SortedDictionary

Otra colección que se agregó en el .NET 3.5 es el Hashset. Es una colección que soporta el conjunto de las operaciones.

También, el LinkedList es un estándar vinculado lista de la aplicación (la Lista es una matriz de la lista para una recuperación más rápida).

5voto

Andy Brown Puntos 1686

Yo simpatizamos con la pregunta - yo también encontrar (?) la elección desconcertante, así que me puse científicamente para ver que la estructura de datos es el más rápido (yo hice la prueba con VB, pero me imagino que C# sería el mismo, ya que ambos idiomas que hagan lo mismo en el nivel CLR). Usted puede ver algunos de evaluación comparativa de resultados llevada a cabo por mí aquí (también hay cierta discusión sobre el tipo de datos que es mejor para el uso en qué circunstancias).

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X