Introducción
Esta serie de artículos pretende mostrar las características y peculiaridades de las colecciones en .NET. El objetivo no es mostrar las situaciones en las que cada una de los diferentes tipos de colecciones pueden utilizarse en cada contexto sino la de conocer las mismas, ventajas y desventajas, para poder seleccionar el tipo de colección más apropiado en cada momento.
La serie cubre (entre corchetes el estado):
- Colecciones No Genericas
- Colecciones Genéricas System.Collections.Generic (este post)
- Colecciones de System.Collections.ObjectModel (en desarrollo)
- Colecciones nuevas en CLR 4.0 (no es definitivo además solo hay una)
- Cota superior asintótica de las colecciones del CLI. aka Notación de Landau - O Grande- (en desarrollo)
- Power Collections y C5 (por ahí andan)
- Rx (si hay ganas y tiempo)
Colecciones Genéricas
Sin lugar a dudas, uno de los conceptos que más provecho ha sacado de la genericidad han sido las colecciones. Practicamente todas las colecciones utilizadas hasta entonces tienen su equivalente dentro del espacio de nombre System.Collections.Generic además de la aparición de nuevas colecciones fruto de la flexibilidad que otorga los tipos generéricos.
En la siguiente tabla podemos ver algunas de estas colecciones (Fuente: Blog de Krzysztof Cwalina )
No Genericas Similares de tipo Generico
ArrayList List<T>
Hashtable Dictionary<TKey,TValue>
SortedList SortedList<TKey,TValue>
Queue Queue<T>
Stack Stack<T>
IEnumerable IEnumerable<T>
ICollection N/A (use IEnumerable<T> anything that extends it)
N/A ICollection<T>
IList IList<T>
CollectionBase Collection<T>
ReadOnlyCollectionBase ReadOnlyCollection<T>
DictionaryBase N/A (just implement IDictionary<TKey,TValue>
N/A SortedDictionary<TKey,TValue>
N/A KeyedCollection<TKey,TItem>
N/A LinkedList<T>
NOTA: No todas las colecciones genéricas se encuentran en el espacio de nombres System.Collections.Generic. Algunas las veremos en el siguiente post bajo el espacio de nombre System.Collections.ObjectModel.
De la misma forma que en la colecciones no genéricas, me gustaria empezar desgranando el núcleo de toda colección: el iterador/enumerador.
El Enumerador genérico
Como es de preveer existe una interfaz IEnumerator<T> dentro del espacio de nombres System.Collections.Generic cuya firma es:
public interface IEnumerator<out T> : IDisposable, IEnumerator
{
new T Current { get; }
}
Por consiguiente, la interfaz IEnumerable<T> también tiene su equivalente genérico y se describe como:
public interface IEnumerable<out T> : IEnumerable
{
new IEnumerator<T> GetEnumerator();
}
NOTA: La importancia y funcionamiento de ambas se describe en el post anterior.
En dichas firmas ya empezamos a ver las primeras pecualiridades y es que en ambos casos cada una de las interfaces implementa su equivalente no genérico para mantener la compatibilidad hacía las colecciones no genéricas. Por otro lado IEnumerator<T> implementa IDisposable. La razón nos la explica el propio Krzysztof Cwalina aqui y no es más que para contemplar determinados escenarios dónde la colección que implementa IEnumerator<T> pueda destruir recursos “externos” utilizados tales como conexiones en base de datos para la lectura de filas o manejadores de archivos para la iteración de ficheros. Por último ambas interfaces son covariantes a T en el CLR 4.0.
Uno de los cambios más importantes es la abstracción de ICollection<T>. Si nos fijamos en la tabla de equivalencias del inicio de este post veremos que ICollection no tiene ninguna equivalencia en la parte genérica de la mismo forma que ICollection<T> tampoco la tiene en la parte no genérica. Fijémonos en su firma:
ICollection<T>
public interface ICollection<T> : IEnumerable<T>, IEnumerable
{
int Count { get; }
bool IsReadOnly { get; }
void Add(T item);
void Clear();
bool Contains(T item);
void CopyTo(T[] array, int arrayIndex);
bool Remove(T item);
}
Las unicas propiedades que tienen en común son CopyTo y Count. El método SyncRoot y la propiedad IsSynchronized se han eliminado y se han añadido los métodos Add, Contains, Clear y Remove. Queda evidente pues que lo único que comarten es el nombre ya que la abstracción es bien distinta.
NOTA: Krzysztof Cwalina lo argumenta diciendo que en realidad ICollection no tenia mucho sentido. .NET Framework no tenia ningún tipo de colección que representara una colección indexada de lectura y escritura; de ahí surge ICollection<T>.
En cuanto a las equivalencias de IList e IDictionary:
IList<T>
public interface IList<T> : ICollection<T>, IEnumerable<T>, IEnumerable
{
T this[int index] { get; set; }
int IndexOf(T item);
void Insert(int index, T item);
void RemoveAt(int index);
}
IDictionary<TKey,TValue>
public interface IDictionary<TKey, TValue> : ICollection<KeyValuePair<TKey, TValue>>,
IEnumerable<KeyValuePair<TKey, TValue>>, IEnumerable
{
TValue this[TKey key] { get; set; }
ICollection<TKey> Keys { get; }
ICollection<TValue> Values { get; }
bool ContainsKey(TKey key);
void Add(TKey key, TValue value);
bool Remove(TKey key);
bool TryGetValue(TKey key, out TValue value);
}
Podriamos afirmar, pues que ambas tienen su correspondencia en el espacio de nombre System.Collections.Generic pese a que IDictionary tiene algunas pecualiridades debido a la flexibilidad de los genéricos y que veremos más tarde. Por último siguen implementando la interfaz no genérica IEnumerable para mantener la compatibilidad con colecciones no genéricas.
Ahora veremos los diferentes tipos de colecciones en base a la interfaz que utilizan.
Colecciones Genéricas
Colecciones regulares (System.Collections.ICollection)
NOTA: Pese a que MSDN Library afirma que tanto Queue<T> y Stack<T> hacen uso de ICollection<T> esto no es cierto. Implementan ICollection.
Este tipo de colecciones también son conocidas como colecciones ordenadas o simplemente collecciones –me he permitido la libertad de denominarlas estándar o regulares para diferenciarlas de las específicas-. Hago hincapié en ello pues encontré varias formas de denomiarlas. De hecho, más allá de la colección Collection que como vimos anteriormente es abstracta y no es más que una evolución de CollectionBase utilizada en las versiones tempranas del CLR, existe un par de clases que podriamos catalogar dentro de este grupo y que vienen representadas por las clases Stack<T> y Queue<T>.
NOTA: Ambas guardan una estrecha relación ya que en ambos casos los elementos se almacenan según el orden de llegada. Nótese que el término “ordenación” utilizado anteriormente no es una ordenación lógica sobre una propiedad del conjunto de elemento; este tipo de elementos los veremos más adelante y podrían estar catalogados como colecciones especializadas.
La diferencia principal entre Stack<T> y Queue<T> reside en el orden en el que los elementos son obtenidos. En ambos casos almacenan elementos en estricto orden de llegada y mientras que en la clase Stack<T> responde a LIFO (Last Input First Output) en el caso de Queue<T> responde a FIFO (First Input First Output). Ambas clases derivan de ICollection e IClonable y cada una de ellas utiliza un método distinto para añadir y quitar un elemento de la colección. Push y Pull para Stack y Enqueue y Dequeu para Queue.
var queue = new Queue<string>();
var stack = new Stack<string>();
queue.Enqueue("A");
queue.Enqueue("B");
queue.Enqueue("C");
queue.Enqueue("D");
stack.Push("A");
stack.Push("B");
stack.Push("C");
stack.Push("D");
Console.WriteLine("Dequeue-ing...");
foreach (var elemento in queue)
Console.WriteLine(elemento);
Console.WriteLine("Pop-ing...");
foreach (var elemento in stack)
Console.WriteLine(elemento);
Colecciones (System.Collections.Generic.ICollection<T>)
LinkedList<T> es una colección de nodos enlazados que implementa, entre otros ICollection<T>. El nucleo central de LinkedList<T> es System.Collections.Generic.LinkedListNode<T> la cual es una clase cuya caracteristica fundamental es que almacena el nodo immediatamente posterior y anterior y portanto todos y cada uno de los nodos mantienen una referencia de orden. Más info: Wikipedia.
A partir de aquí el funcionamiento es relativamente sencillo. Lo que iremos almacenando son objetos del tipo LinkedListNode<T> de tipo T en una colección LinkedList<T>. Las ventajas que nos ofrece este tipo de listas que podemos insertar immediantamente antes o despues de un determinado nodo practicamente con un coste O(1) a través de los métodos AddBefore() y AddAfter(). Además podremos añadir un elemento al inicio o al final de la lista enlazada mediante AddFirst() y AddLast() respectivamente.
LinkedList<T> mantiene siempre tanto el primer como el último nodo a través de las propiedades First y Last siempre y cuando el objecto LinkedList<T> tenga más de 0 elementos (linkedList.Count => 1). En el siguiente ejemplo, aunque trivial, muestra alguna de las posibilidades de LinkedList<T>.
var linkedList = new LinkedList<string>();
//añadimos el que va a ser el primer elemento
linkedList.AddFirst("Alfa");
//mantenemos una instanacia al ultimo
//elemento insertado mediante linkedListNode
//NOTA: tambien podriamos utilizar linkedList.AddLast...
var linkedListNode = linkedList.AddAfter(linkedList.First, "Beta");
linkedListNode = linkedList.AddAfter(linkedListNode, "Eco");
linkedListNode = linkedList.AddAfter(linkedListNode, "November");
//como por ejemplo aqui
linkedList.AddLast("Romeo");
linkedList.AddLast("Zulu");
//insertamos despues de "Eco"
linkedListNode = linkedList.Find("Eco");
if (linkedListNode != null)
linkedList.AddBefore(linkedListNode, "Delta");
foreach(var elemento in linkedList)
Console.WriteLine(elemento);
//resultados...
//Alfa
//Beta
//Eco
//November
//Romeo
//Zulu
Colecciones específicas
Otro tipo de agrupamiento para las colecciones específicas (es decir, las que se extienden más allá de ICollection) es de colecciones de acceso por clave o por índice. A continuación veremos el conjunto de colecciones agrupadas por clave (a través de IDictionary<TKey, TValue>) y posteriormente las que son agrupadas por índice (a través de IList<T>) y por último aquellas colecciones que hacen uso tanto de las características de índice y de clave.
Derivadas de System.Collections.Generics.IList<T>
En el ejemplo con el que abríamos el primer post vimos un ejemplo con System.Array, un claro ejemplo de colección basado en índices, también conocido en inglés como zero-based indexed collection. System.ArrayList es otro claro ejemplo de colección indexada que surge de la necesidad de poder redimensionar el tamaño de una colección de forma dinámica, limitación encontrada en System.Array. De hecho, ArrayList podría ser descrita como un híbrido entre una colección y una matriz de elementos ya que los elemento siguen almacenándose en orden de llegada pese a que pueden ser obtenidos mediante el índice relativo de la propia colección.
System.Collections.Generics.List<T> es equivalente natural a ArrayList en la parte de genericos. Es en esencial un ArrayList mejorada en rendimiento, tamaño y velocidad. Es quizás la colección más utilizada y más adecuada a la gran mayoria de escenarios debido a su flexibilidad y características.
En cuanto a la capacidad, de la misma forma que en ArrayList, podemos indicársela en el constructor o bien no hacerlo y la propia colección irá redimensionándose. Debido al coste que tiene la operación de redimensionamiento, List<T> crece en bloques del doble de su capacidad, siendo 4 su capacidad inicial, si no se indica el tamaño por defecto. Esto significa que tras la instanciación de:
var list = new List<double> { 20.0d };
//list.Capacity = 4
//list.Count = 1
El objeto list poseerá una capacidad de 4 elementos, tres de ellos null. Tras ir añadiendo más elementos list siempre irá creciendo en orden de 4, 8, 16, 32, 64, … elementos dejando los no utilizados con el valor por defecto de cada tipo, esto es default(T), o más concretamente null para los tipos por referencia y 0 para los tipos por valor. Indentificaremos la capacidad total mediante la propiedad Capacity, siempre multiples de 4, y la cantidad de elementos no null/0 mediante Count.
Podemos exigir que un objeto List<T> tenga un tamaño fijo predefinido. Sin embargo, es muy común confundir esta limitación o característica con la cantidad de elementos que se le puede pasar por parámetro en el constructor de la clase List<T>. Otro error común es indicar una capacidad elevada en previsión de crecimiento. Si es cierto que esto es una buena practica si el numero de elementos a añadir es finalmente inferior a la capacidad inicial, no lo es si el numero de elementos final es superior puesto que el crecimiento de la ArrayList será multiple a la capacidad inicial. Es decir, por ejemplo, el siguiente ejemplo crea un List<T> con un tamaño predefinido de 100 elementos. Por un lado podemos ver como el objeto arrayList acepta 1000 elemento (10 veces más de lo inicialmente previsto) sin ningún problema. Sin embargo, tras el bucle podemos observar que la capcidad –Capacity- (no cantidad –Count- de elementos) es de 1600 y es debido a que el crecimiento ha sido de 100, 200, 400, 800 y 1600. O sea que tenemos un List<T> de 1600 elementos de capacidad y realmente se estan utilizando 1000.
var list = new List<string>(100);
for (int i = 0; i <= 1000; i++)
list.Add(i.ToString());
//list.Capacity = 1600
//list.Count = 1000
Si hacemos la misma interación sin un tamaño predefinido, la capacidad final será de 1024.
var list = new List<string>();
for (int i = 0; i <= 1000; i++)
list.Add(i.ToString());
//list.Capacity = 1024
//list.Count = 1000
Derivadas de System.Collections.Generics.IDictionary<T>
La diferencia fundamental entre SortedList<TKey,TValue> y List<T> es que mientras en List<T> se almacenan los elemento por orden de “llegada” en SortedList<TKey,TValue> se almacena una pareja valor/clave y tanto se puede acceder por clave como por índice.
Internamente, SortedList<TKey,TValue> mantiene dos objetos IList<T> internos, uno para el almacenamiento de claves y otro para el almacenamiento de valores la cuales se acceden mediante un objeto de la clase KeyValuePair<TKey,TValue>. Como su propio nombre indica, SortedList<TKey,TValue> mantiene el conjunto de elementos ordenados por clave. La clave puede ordenarse en función a una implementación específica de IComparer<T> o bien mediante la interfaz IComparable<T> que los propios tipos de las claves – de sus elementos - indican. En el siguiente ejemplo añadimos 4 elementos de tipo string y observamos el resultado. Fijémonos como el IComparer<T> por defecto es CaseSensitive es decir System.Collections.Generic.Comparer<T>.Default (ya que está utilizando la implementación IComparable<T> derivado de la clase String).
var sortedList = new SortedList<string,string>()
{
{"Z", "Z"},
{"A", "A"},
{"a", "a"},
{"B", "B"}
};
foreach (var elemento in sortedList)
Console.WriteLine(elemento.Value);
//Resultado:
//a
//A
//B
//Z
Sin embarago, si utilizáramos un IComparer<T> propio y especificaramos explicitamente que la comparación sea Case Insensitive, obtendriamos un error ya que no es posible añadir dos elemento con la misma clave al tratar de la misma forma o valor las cadenas “a” y “A”:
public class CaseInsensitiveComparerSample<T> : IComparer<T>
{
public int Compare(T x, T y)
{
return ((new CaseInsensitiveComparer())
.Compare(y, x));
}
}
//implementación
var sortedList = new SortedList<string,string>(
new CaseInsensitiveComparerSample<string>()
)
{
{"Z", "Z"},
{"A", "A"},
// Argument Exception
{"a", "a"},// Item has already been added.
// Key in dictionary: 'A' Key being added: 'a'
{"B", "B"}
};
Dictionary<TKey, TValue> es un HashTable fuertemente tipado. La diferencia entre ambos se encuentra en como gestiona las colisiones de los codigos hash de sus elementos en el algoritmo hash. Mientras que HasTable realiza un sondeo cuando existe una colision reubicando el elemento en el siguiente cubo –bucket- libre mientras que Dictionary<TKey, TValue> realiza un encadenamiento de los elementos con un mismo codigo hash almacenándolos en una lista asociada a un mismo cubo –bucket-. Para obtener más información al respecto podeis consultar el post System.Collections.Generic Dictionary Capacity, Hashing, and Collisions.
Por lo demás y como comentamos antes el funcionamiento es en esencial el de un HashTable. Todos los elementos implementan de forma explícita o implícita un código Hash, a través, por ejemplo, de la clase base System.Object. Como peculiaridad, Dictionary<TKey,TValue> utiliza la también estructura KeyValuePair<TKey,TValue> en lugar de la estructura DictionaryEntry que utiliza HasTable. Un ejemplo sencillo seria:
var dictionary = new Dictionary<int,string>
{
{616000, "Juan M."},
{616100, "Rafael H."},
{616200, "Joaquin A."},
{616210, "Alberto P."}
};
foreach (KeyValuePair<int,string> elemento in dictionary)
{
Console.WriteLine(
string.Format("Key: {0} Value:{1}",
elemento.Key, elemento.Value));
}
La colección que mezcla las capacidades del Dictonary<TKey, TValue> con un conjunto de claves ordenado como hacía SortedList<T> es SortedDictionary<TKey, TValue>. Aqui es dónde reside la mayoría de las preguntas que nos hacemos acerca de cuál tipo de colección utilizar.
Según información del MSDN Library, establece que:
Where the two classes differ is in memory use and speed of insertion and removal:
Veamos las diferencias reales de los dos primeros puntos: memoria y rendimiento.
Memoria
Para tratar de hacer una comparativa del tamaño de memoria utilizado entre uno y otro vamos a ejecutar un código que lo único que hará es añadir 1.000.000 de elementos string de clave int.
NOTA: La inserción se hace de forma secuencias con lo que el coste en la operación de agregación será mucho menor en SortedList. Esto es una excepción puesto que por norma general el valor de la clave será desordenada y es en ese punto, cuando hablemos del rendimiento lo veremos, dónde SortedDictionary es mucho más rápido.
Lo realmente importante del siguiente código es el espacio en memoria que se utiliza para la manipulación de los dos objectos SortedList y SortedDictionary:
var sortedList =
new SortedList<int, string>();
var sortedDictionary =
new SortedDictionary<int, string>();
int items = 1000000;
for (int i = 0; i < items; i++)
sortedList.Add(i,i.ToString());
for (int i = 0; i < items; i++)
sortedDictionary.Add(i,i.ToString());
Tras la ejecución con CLRProfiler vemos el grafo de asignación de bytes en memoria de:
la SortedList:
y la representacción de SortedDictionary:
Como podemos comprobar el espacio asignado en memoria es superior en el caso de SortedDictionary.
Como curiosidad podemos apreciar como cada uno de los objetos trata de forma bien distinta la información en memoria. SortedList al final acaba generando dos Arrays, una de claves y otra de valores del tipo System.Int32[] y System.String[] respectivamente. Por otro lado, SortedDictionary hace uso de un tipo utilizado internamente llamado Generic.TreeSet. Este tipo es un arbol binario utilizado, como dije antes, de forma interna para la manipulación de objetos del tipo Dictionary. La razón por la cual no está expuesta como API pública es debido a que el enfoque de este mismo tipo seria muy diferente. Básicamente Microsoft decidió utilizar únicamente de forma interna y no exponerla como API pública. Además de Generic.TreeSet podemos ver un objeto System.String que es dónde almacena el valor del objeto SortedDictionary.
internal class TreeSet<T> : ICollection<T>, IEnumerable<T>, ICollection,
IEnumerable, ISerializable, IDeserializationCallback
Rendimiento
Para trata de evaluar el rendimiento entre ambas colecciones vamos a realizar una prueba muy similar, pero no vamos a dar ventaja a SortedList añadiendo elementos ordenados y es por ello que vamos a substituir las claves del tipo int al tipo System.Guid generándose uno diferente cada vez de forma que SortedList tenga que ordenar la clave tras cada inserción.
El código podria ser algo tal que así:
var sortedList =
new SortedList<Guid, string>();
var sortedDictionary =
new SortedDictionary<Guid, string>();
int items = 100000;
for (int i = 0; i < items; i++)
sortedList.Add(Guid.NewGuid(), i.ToString());
for (int i = 0; i < items; i++)
sortedDictionary.Add(Guid.NewGuid(), i.ToString());
El resultado del Performance Profiling del VS 2010 es tal y como muestra la siguiente captura de pantalla.
La operación SortedList.Add ocupa más del 97% del tiempo total de ejecución del código mientras que SortedDictionary.Add apenas llega al 2% por lo tanto queda demostrado el rendimiento entre ambas clases en operaciones de inserción y eliminación.
Conclusión
Además de las nombradas en este post existen otras menos utilizadas dentro del espacio de nombre de colecciones genéricas.
Otras referencias
http://en.how-to.mobi/index.php?sd=es&id=221691
http://blogs.msdn.com/b/kcwalina/archive/2004/08/06/210297.aspx