Compartir a través de

Colecciones y estructuras de datos

A menudo, los datos similares se pueden controlar de forma más eficaz cuando se almacenan y manipulan como una colección. Puede usar la clase System.Array o las clases en 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; colecciones genéricas y colecciones no genéricas. Las colecciones genéricas son de seguridad de tipos en tiempo de compilación. Por este motivo, las colecciones genéricas suelen ofrecer un mejor rendimiento. Las colecciones genéricas aceptan un parámetro de tipo cuando se construyen. No requieren que se convierta con origen y destino el tipo Object al agregar o quitar elementos de la colección. Además, la mayoría de las colecciones genéricas se admiten en 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.

En .NET Framework 4 y versiones posteriores, las colecciones del espacio de nombres System.Collections.Concurrent proporcionan operaciones eficientes y seguras para acceder a elementos de colección desde múltiples 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 la colección

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

Además, muchas clases de colección 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 contiene realmente. Algunas colecciones ocultan la capacidad, el recuento, o ambos.

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

    Un BitArray es un caso especial; su capacidad es la misma 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. Array tiene un límite inferior de cero de forma predeterminada, pero se puede definir un límite inferior diferente al crear una instancia de la clase Array mediante 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 acceso multiproceso escalable y eficaz a una colección, use una de las clases del System.Collections.Concurrent espacio de nombres o considere la posibilidad de usar una colección inmutable. Para obtener más información, consulte Thread-Safe Colecciones.

Elección de una colección

En general, debería utilizar colecciones genéricas. En la tabla siguiente se describen algunos escenarios de colección comunes y las clases de colección que puede usar para esos escenarios. Si no está familiarizado con las colecciones genéricas, la tabla siguiente le ayudará a elegir la colección genérica que mejor funcione para la tarea:

Quiero... Opciones de colección genérica Opciones de colección no genéricas Opciones de colección de subprocesos o inmutable
Almacenar elementos como pares clave-valor para una búsqueda rápida por clave Dictionary<TKey,TValue> Hashtable

(Colección de pares clave-valor organizados 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>
Obtener acceso a elementos secuencialmente LinkedList<T> Sin recomendación Sin recomendación
Recibir notificaciones cuando se quitan o 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 para 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, es importante considerar posibles compensaciones en el rendimiento. Use la tabla siguiente para hacer referencia a cómo se comparan varios tipos de colección mutables en complejidad algorítmica con sus equivalentes inmutables correspondientes. A menudo, los tipos de colección inmutables son menos eficaces, pero proporcionan inmutabilidad, lo que suele ser una ventaja comparativa válida.

Cambiable Amortizado 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 estrictamente O(n) Búsqueda de ImmutableDictionary<T> O(log n)
SortedDictionary<T>.Add O(log n) O(n log n) ImmutableSortedDictionary<T>.Add O(log n)

Una List<T> se puede enumerar de forma eficaz mediante un bucle for o un bucle foreach. Un ImmutableList<T>, sin embargo, realiza un trabajo deficiente dentro de un bucle for, debido al tiempo de O(log n) para su indexador. Enumerar un ImmutableList<T> usando un bucle foreach es eficaz porque ImmutableList<T> usa un árbol binario para almacenar sus datos en lugar de una matriz como List<T> usa. Una matriz se puede indexar rápidamente en, mientras que un árbol binario se debe recorrer hasta que se encuentre el nodo con el índice deseado.

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

Título Descripción
Seleccionar una clase de colección Describe las distintas colecciones y le ayuda a seleccionar una para su escenario.
Tipos de colección usados habitualmente Describe los tipos de colección genéricos y no genéricos usados habitualmente, como System.Array, System.Collections.Generic.List<T>y System.Collections.Generic.Dictionary<TKey,TValue>.
Cuándo usar colecciones genéricas Describe el uso de tipos de colección genéricos.
Comparaciones y ordenaciones dentro de colecciones Describe el uso de comparaciones de igualdad y comparaciones de ordenación en colecciones.
Tipos de colección ordenados Describe el rendimiento y las características de las colecciones ordenadas.
Tipos de las colecciones Hashtable y Dictionary Describe las características de los tipos de diccionario genéricos y no genéricos basados en hash.
Colecciones deThread-Safe Describe los tipos de colección, como System.Collections.Concurrent.BlockingCollection<T> y System.Collections.Concurrent.ConcurrentBag<T> que admiten el acceso simultáneo seguro y eficaz desde varios subprocesos.
System.Collections.Immutable Presenta las colecciones inmutables y proporciona vínculos a los tipos de colección.

Referencia