Colecciones y estructuras de datos

  • Artículo

A menudo, los datos similares pueden controlarse de forma más eficaz si se almacenan y manipulan como si fuesen una colección. Puede utilizar la clase System.Array o las clases de los espacios de nombres System.Collections, System.Collections.Generic,System.Collections.Concurrent y System.Collections.Immutable para agregar, quitar y modificar elementos individuales o un intervalo de elementos de una colección.

Hay dos tipos principales de colecciones: las colecciones genéricas y las colecciones no genéricas. Las colecciones genéricas son de seguridad de tipos en tiempo de compilación. Debido a esto, las colecciones genéricas normalmente ofrecen un mejor rendimiento. Las colecciones genéricas aceptan un parámetro de tipo cuando se construyen y no requieren conversiones con el tipo Object al agregar o quitar elementos de la colección. Además, la mayoría de colecciones genéricas son compatibles con las aplicaciones de la Tienda Windows. Las colecciones no genéricas almacenan elementos como Object, requieren una conversión y la mayoría de ellas no son compatibles con el desarrollo de aplicaciones de la Tienda Windows. Sin embargo, puede que vea colecciones no genéricas en código antiguo.

A partir de .NET Framework 4, las colecciones del espacio de nombres System.Collections.Concurrent proporcionan operaciones eficaces y seguras para subprocesos para acceder a los elementos de la colección desde varios subprocesos. Las clases de colección inmutables en el espacio de nombres System.Collections.Immutable (paquete de NuGet) son intrínsecamente seguras para los subprocesos, ya que las operaciones se realizan en una copia de la colección original, mientras que la colección original no se puede modificar.

Características comunes de las colecciones

Todas las colecciones ofrecen métodos para agregar, quitar o buscar elementos en la colección. Además, todas las colecciones que implementan directa o indirectamente las interfaces ICollection o ICollection<T> comparten estas características:

Además, muchas clases de colecciones contienen las siguientes características:

  • Propiedades de capacidad y recuento

    La capacidad de una colección es el número de elementos que puede contener. El recuento de una colección es el número de elementos que realmente contiene. Algunas colecciones ocultan la capacidad, el recuento, o ambos.

    La mayoría de las colecciones expanden automáticamente su capacidad cuando se alcanza la capacidad actual. La memoria se reasigna y los elementos de la antigua colección se copian en la nueva. Esto reduce el código necesario para utilizar la colección; sin embargo, el rendimiento de la colección podría verse afectado negativamente. Por ejemplo, en List<T>, si Count es menor que Capacity, el agregar un elemento supone una operación O(1). Si es necesario aumentar la capacidad para alojar el nuevo elemento, agregar un elemento se convierte en una operación O(n), donde n es Count. La mejor manera de evitar el rendimiento deficiente provocado por múltiples reasignaciones es establecer la capacidad inicial el tamaño estimado de la colección.

    BitArray es un caso especial; su capacidad es igual que su longitud, que es la misma que su recuento.

  • Límite inferior coherente

    El límite inferior de una colección es el índice de su primer elemento. Todas las colecciones indizadas en el espacio de nombres System.Collections tienen un límite inferior de cero, lo que significa que están indizadas en 0. De forma predeterminada, Array tiene un límite inferior de cero, pero se puede definir un límite inferior diferente mediante la creación de una instancia de la clase Array con Array.CreateInstance.

  • Sincronización para el acceso de varios subprocesos (solo clases System.Collections).

    Los tipos de colecciones no genéricas del espacio de nombres System.Collections proporcionan una seguridad de subprocesos con sincronización; normalmente se exponen a través de los miembros SyncRoot y IsSynchronized. Estas colecciones no son seguras para subprocesos de forma predeterminada. Si necesita un acceso multiproceso escalable y eficaz a una colección, utilice una de las clases del espacio de nombres System.Collections.Concurrent o considere el uso de una colección inmutable. Para obtener más información, consulte Colecciones seguras para subprocesos.

Elija una colección.

En general, debería utilizar colecciones genéricas. En la tabla siguiente se describen algunos escenarios habituales de las colecciones y las clases de colección que puede utilizar en esos escenarios. Si es la primera vez que usa colecciones genéricas, con esta tabla le será más fácil elegir la colección genérica que funciona mejor para su tarea.

Deseo... Opciones de colección genérica Opciones de colección no genérica Opciones de colección de subprocesos o inmutable
Almacenar elementos como pares clave/valor para una consulta rápida por clave Dictionary<TKey,TValue> Hashtable

(Colección de pares clave/valor que se organizan en función del código hash de la clave).		 ConcurrentDictionary<TKey,TValue>

ReadOnlyDictionary<TKey,TValue>

ImmutableDictionary<TKey,TValue>
Acceso a elementos por índice List<T> Array

ArrayList		 ImmutableList<T>

ImmutableArray
Utilizar elementos FIFO (el primero en entrar es el primero en salir) Queue<T> Queue ConcurrentQueue<T>

ImmutableQueue<T>
Utilizar datos LIFO (el último en entrar es el primero en salir) Stack<T> Stack ConcurrentStack<T>

ImmutableStack<T>
Acceso a elementos de forma secuencial LinkedList<T> Sin recomendación Sin recomendación
Recibir notificaciones cuando se quitan o se agregan elementos a la colección. (implementa INotifyPropertyChanged y INotifyCollectionChanged) ObservableCollection<T> Sin recomendación Sin recomendación
Una colección ordenada SortedList<TKey,TValue> SortedList ImmutableSortedDictionary<TKey,TValue>

ImmutableSortedSet<T>
Un conjunto de funciones matemáticas HashSet<T>

SortedSet<T>		 Sin recomendación ImmutableHashSet<T>

ImmutableSortedSet<T>

Complejidad algorítmica de colecciones

Al elegir una clase de colección, vale la pena tener en cuenta las posibles compensaciones en cuanto al rendimiento. Use la siguiente tabla para hacer referencia a la comparación de varios tipos de colecciones mutables por lo que respecta a la complejidad algorítmica con sus equivalentes inmutables correspondientes. A menudo, los tipos de colecciones inmutables son menos efectivos, pero proporcionan inmutabilidad, lo que a menudo es un beneficio comparativo válido.

Mutable Amortizado El peor caso Inmutable Complejidad
Stack<T>.Push O(1) O(n) ImmutableStack<T>.Push O(1)
Queue<T>.Enqueue O(1) O(n) ImmutableQueue<T>.Enqueue O(1)
List<T>.Add O(1) O(n) ImmutableList<T>.Add O(log n)
List<T>.Item[Int32] O(1) O(1) ImmutableList<T>.Item[Int32] O(log n)
List<T>.Enumerator O(n) O(n) ImmutableList<T>.Enumerator O(n)
HashSet<T>.Add, búsqueda O(1) O(n) ImmutableHashSet<T>.Add O(log n)
SortedSet<T>.Add O(log n) O(n) ImmutableSortedSet<T>.Add O(log n)
Dictionary<T>.Add O(1) O(n) ImmutableDictionary<T>.Add O(log n)
Búsqueda de Dictionary<T> O(1) O(1), o bien O(n) de manera estricta ImmutableDictionary<T> lookup O(log n)
SortedDictionary<T>.Add O(log n) O(n log n) ImmutableSortedDictionary<T>.Add O(log n)

Un objeto List<T> se puede enumerar eficientemente utilizando un bucle for o un bucle foreach. Sin embargo, un objeto ImmutableList<T> realiza un trabajo insuficiente dentro de un bucle for, debido al tiempo de O(log n) de su indizador. Enumerar un objeto ImmutableList<T> usando un bucle foreach es eficiente porque ImmutableList<T> usa un árbol binario para almacenar sus datos en lugar de una matriz simple como la que usa List<T>. Una matriz se puede indexar muy rápidamente, mientras que un árbol binario debe desplazarse hasta que se encuentre el nodo con el índice deseado.

Además, SortedSet<T> tiene la misma complejidad que ImmutableSortedSet<T>. Esto es porque ambos usan árboles binarios. La diferencia significativa, por supuesto, es que ImmutableSortedSet<T> usa un árbol binario inmutable. Dado que ImmutableSortedSet<T> también ofrece una clase System.Collections.Immutable.ImmutableSortedSet<T>.Builder que permite la mutación, puede obtener tanto inmutabilidad como rendimiento.

Title Descripción
Seleccionar una clase de colección Describe las diferentes colecciones y le ayuda a seleccionar una para su escenario.
Tipos de colección utilizados normalmente Describe los tipos de colección genéricos y no genéricos más utilizados, como System.Array, System.Collections.Generic.List<T> y System.Collections.Generic.Dictionary<TKey,TValue>.
Cuándo utilizar colecciones genéricas Describe el uso de los tipos de colección genéricos.
Comparaciones y ordenaciones en colecciones Describe el uso de las comparaciones de igualdad y ordenación en las colecciones.
Tipos de colecciones ordenadas Describe las características y el funcionamiento de colecciones ordenadas.
Tipos de las colecciones Hashtable y Dictionary Describe las características de los tipos de diccionarios basados en hash genéricos y no genéricos.
Colecciones seguras para subprocesos Describe los tipos de colección, como System.Collections.Concurrent.BlockingCollection<T> y System.Collections.Concurrent.ConcurrentBag<T>, que admiten un acceso simultáneo seguro y eficaz desde varios subprocesos.
System.Collections.Immutable Presenta las colecciones inalterables y proporciona vínculos a los tipos de colección.

Referencia

System.Array System.Collections System.Collections.Concurrent System.Collections.Generic System.Collections.Specialized System.Linq System.Collections.Immutable