Collections in C#

Collections:

Collection classes are specialized classes for data storage and retrieval. These classes provide support for stacks, queues, lists, and hash tables. Most collection classes implement the same interfaces.

Collection classes serve various purposes, such as allocating memory dynamically to elements and accessing a list of items on the basis of an index etc. These classes create collections of objects of the Object class, which is the base class for all data types in C#.

Collection represents group of objects. By the help of collections, we can perform various operations on objects such as

• store object

• update object

• delete object

• retrieve object

• search object, and

• sort object

Ways to Work with Collection

There are 3 ways to work with collections. The three namespaces are given below:

1. System.Collections.Generic classes

2. System.Collections classes (Now deprecated)

3. System.Collections.Concurrent classes

1) System.Collections.Generic classes

The System.Collections.Generic namespace has following classes:

• List

• Stack

• Queue

• LinkedList

• HashSet

• SortedSet

• Dictionary

• SortedDictionary

• SortedList

2) System.Collections classes

These classes are legacy. It is suggested now to use System.Collections.Generic classes. The System.Collections namespace has following classes:

• ArrayList

• Stack

• Queue

• Hashtable

3) System.Collections.Concurrent classes

The System.Collections.Concurrent namespace provides classes for thread-safe operations. Now multiple threads will not create problem for accessing the collection items.

The System.Collections.Concurrent namespace has following classes:

• BlockingCollection

• ConcurrentBag

• ConcurrentStack

• ConcurrentQueue

• ConcurrentDictionary

• Partitioner

• Partitioner

• OrderablePartitioner

Types of Collection

The two types of collections in C# :

• Non-generic collections

• Generic collections

NON-GENERIC COLLECTIONS

Hierarchical structure of non-generic collections:

IEnumerator,IEnumerable and ICollection are the top level interfaces for all collections in C#.

1. IEnumerator:

A simple iteration over a non-generic array is supported by the interface. It includes methods and properties which can be implemented to support easy iteration using foreach loop.

2. IEnumerable:

The interface includes GetEnumerator() method which returns an object if IEnumerator.

3. ICollection:

This is the base interface for all non-generic arrays, defining sizes, enumerators, and synchronization methods.

4. IList:

The interface includes properties and methods to add, insert, remove elements in the collection and also individual elements can be accessed by index.

5. IDictionary:

The interface represents a non-generic collection of key-value pairs.

6. ArrayList:

It stores objects of any type, for example, an array. However, there is no need to specify the size of ArrayList as it grows automatically.

Properties:

• capacity : Gets or sets the maximum number of elements an ArrayList can hold.

• Count : Gets the number of elements in the ArrayList that are currently present.

• IsFixedSize : Gets a value indicating whether the ArrayList has a fixed size.

• IsReadOnly : Gets a value indicating whether the ArrayList is read-only.

• Item : Gets or sets the element at the specified index.

7. SortedList:

The SortedList collection stores key-value pairs in the ascending order of keys by default. It implements IDictionary and ICollection interfaces, so elements can be accessed both by key and index. It stores key and value pairs. By default, it arranges the elements in ascending order of keys.

Methods:

SortedList key can be any data type but it should be of the same type, as it arranges items on the basis of ascending order of keys SortedList includes key-value pairs. So the type of element would be DictionaryEntry in foreach loop. Key-value pairs can be cast to DictionaryEntry. Key must be unique and cannot be null whereas value can be null or duplicate. Access individual values using an indexer. SortedList indexer accepts a key to return the value associated with it.

8. Stack:

Stack stores the values in LIFO style(Last In First Out). It provides a Push() method to add a value and Pop() and Peek() methods to retrieve values.

It is a special type of collection that stores elements in LIFO style(Last In First Out). It allows null or duplicate values. It provides a Push() method to add a value and Push() and Peek() methods to retrieve values.

Methods:

• Push Inserts an item at the top of the stack.

• Peek Returns the top item from the stack.

• Pop Removes and returns items from the top of the stack.

• Contains Checks whether an item exists in the stack or not.

• Clear Removes all items from the stack.

9. Queue:

It uses the first-in, first-out (FIFO) method to store the value. It keeps the order in which values were added. It provides an Enqueue() method to add values and Dequeue() method to retrieve values.

It stores elements in FIFO style(First In First Out). It contains the elements in the order they were added. It allows null or duplicate values. It provides a Enqueue() method to add a value and Dequeue() method to retrieve values from the queue.

Methods:

• Enqueue Inserts an item in the queue.

• Dequeue Removes and returns items from the beginning of the queue.

• Peek Returns the first item from the queue.

• Contains Checks whether an item exists in the queue or not.

• Clear Removes all items from the queue.

• TrimToSize Sets the capacity of the queue to the actual number of items in the queue.

10. Hashtable:

The Hashtable collection stores key-value pairs. It optimizes lookups by computing the hashcode of each key and stores it in a different bucket internally and then matches the hashcode of the specified key at the time of accessing values. It implements IDictionary and ICollection interfaces, so elements can be accessed both by key and index.

Properties:

• Count : Gets the total count of key-value pairs in the Hashtable.

• IsReadOnly : Gets a boolean value indicating whether the Hashtable is read-only.

• Item : Gets or sets the element at the specified key.

• Keys : Gets an ICollection of keys in the Hashtable.

• Values : Gets an ICollection of values in the Hashtable. It stores key-value pairs. It compares the hash value of the keys to retrieve the values.

GENERIC COLLECTIONS

The non-generic types of collections can store any type of item. The limitation of these collections is that while retrieving items, you need to cast them into the appropriate data type, otherwise the program will throw a runtime exception. It also affects the performance, because of boxing and unboxing.

To overcome this problem, C# includes generic collection classes in the System.Collections.Generic namespace.

(C# introduces two methods to Boxing and Unboxing, which links value type to reference type. Boxing is the conversion of the value type to an object type whereas Unboxing refers to the conversion of the object type to value type.)

• List<T> Generic List<T> contains elements of the specified type. It grows automatically as you add elements in it.

• Dictionary<TKey,TValue> Dictionary<TKey,TValue> contains key-value pairs.

• SortedList<TKey,TValue> SortedList stores key and value pairs. It automatically adds the elements in ascending order of key by default.

• Hashset<T> Hashset<T> contains non-duplicate elements. It eliminates duplicate elements.

• Queue<T> Queue<T> stores the values in FIFO style (First In First Out). It keeps the order in which the values were added. It provides an Enqueue() method to add values and a Dequeue() method to retrieve values from the collection.

• Stack<T> Stack<T> stores the values as LIFO (Last In First Out). It provides a Push() method to add a value and Pop() and Peek() methods to retrieve values.

1. List<T>:

List<T> is a generic collection implementation of non-generic ArrayList. The List<T> class implements different interfaces that provide different functionalities. Hence, the List<T> object can be assigned to any of its interface type variables. It is recommended to create an object of List<T> and assign it to IList<T> or List<T> type variable. List<data type> <list name> = new List<data type>(); Or IList<data type> list name = new List<data type>(); Properties:

• Items Gets or sets the element at the specified index

• Count Returns the total number of elements in the List<T>

2. Dictionary<TKey, TValue>:

The Dictionary class is a generic collection class in the System.Collection.Generics namespace. TKey denotes the type of key and TValue is the type of TValue. Dictionary cannot include duplicate or null keys, whereas values can be duplicated or set as null. Keys must be unique and not null, otherwise, it will throw a runtime exception. Properties:

• Count Gets the total number of elements in the Dictionary<TKey,TValue>.

• IsReadOnly Returns a boolean indicating whether the Dictionary<TKey,TValue> is read-only.

• Item Gets or sets the element with the specified key in the Dictionary<TKey,TValue>.

• Keys Returns collection of keys of Dictionary<TKey,TValue>.

• Values Returns collection of values in Dictionary<TKey,TValue>.

Methods:

• Add It is an overloaded method in IDictionary Add() Signature: void Add(TKey, Tvalue) Adds an item to the Dictionary collection. Add() Signature:void Add(KeyValuePair<TKey,TValue> item); This is only valid if at the time of creation you use IDictionary Add key-value pairs in Dictionary<TKey, TValue> collection.

• Remove It is also an overloaded method bool Remove(TKey key) Removes the element with the specified key. bool Remove(KeyValuePair<TKey,TValue>) Removes the first occurrence of specified item from the Dictionary<TKey, TValue>.

• ContainsKey Checks whether the specified key exists in Dictionary<TKey, TValue>.

• Contains Checks whether the specified key-value pair exists in Dictionary<TKey, TValue>.

• Clear It removes all the elements from Dictionary<TKey, TValue>.

• TryGetValue It returns true and assigns the value with the specified key, if the key doesn’t exist then return false.

3. Array:

An array is a special type of data type which can store a fixed number of values sequentially. Array in C# is a reference type that is derived from System.Array class. Array elements are stored sequentially in the memory and that’s why it performs faster.

• All arrays are dynamically allocated.

• Initialization without giving size is not valid.

• As arrays are objects, we can find their length using member length.

• Array variable can also be declared like other variables with [] after the data type.

• The variables in the array are ordered & each has an index beginning from 0.

• Array is an object of base type System.Array.

• Default values of numeric array & reference type elements are set to be respectively 0 and null.

• array elements can be of any type, including an array type.

Methods:

• GetLength Returns the number of elements.

• GetValue(int index) Returns the value at the specified index.

• GetLowerBound Returns the lowest index.

• GetUpperBound Returns the highest index.

4. MAP:

The C# language has no built-in map type. But it offers a powerful Dictionary type, which we use to map things. With a Dictionary, we must specify the type of the key (like “string”) and the type of the value (like “int”). With Add we map a key to a value. With TryGetValue we safely check this mapping. Dictionary is an important part of C# programming. It is a map collection. Usually, the best way to access it is with TryGetValue — this is safe and does not throw exceptions.

5. EQUALS AND HASHCODE

EQUALS: The equals method is used to compare two objects, but by default, it compares references of the objects and returns true if both the objects are pointing to the same reference. Equals method basic principles:

• For any object x, x.equals(x) should return true.

• For any two objects x and y, x.equals(y) should return true if and only if y.equals(x) returns true.

• For multiple objects x, y, and z, if x.equals(y) returns true and y.equals(z) returns true, then x.equals(z) should return true.

• Multiple invocations of x.equals(y) should return the same result unless any of the object properties is modified that is being used in the equals() method implementation.

• Object class equals() method implementation returns true only when both the references are pointing to the same object.

HASHCODE: HashCode() is a native method and returns the hashcode value of the object. It is mainly used in collections. When we call the Add method, the hashCode of the key is used to determine the bucket that will be used to store the mapping value. For retrieval operation, again key hashCode is used to determine the bucket to look for the value. After the bucket is identified, entries are traversed to find out the Entry using hashCode and equal method. If a match is found, the value is returned otherwise null is returned.

• Multiple invocations of hashCode() should return the same integer value unless the object property is modified that is being used in the equals() method.

• An object hashcode value can change in multiple executions of the same application.

• If two objects are equal according to the equals() method, then their hash code must be the same.

• If two objects are unequal according to the equals() method, their hash code is not required to be different. Their hash code value may or may not be equal.

HashCode() and Equals() methods are used in Hashtable-based implementations for storing and retrieving data.

The implementation of equals() and hashCode() should follow these rules.

• If o1.equals(o2), then o1.hashCode() == o2.hashCode() should always be true.

• If o1.hashCode() == o2.hashCode is true, it doesn’t mean that o1.equals(o2) will be true.

When we override equals() method, it’s almost necessary to override the hashCode() method too so that their contract is not violated by our implementation.

The program will not throw any exceptions if the equals() and hashCode() contract is violated, if you are not planning to use the class as a Hashtable key, then it will not create any problem.

If you are planning to use a class as a Hash table key, then it is a must to override both equals() and hashCode() methods.

Hash table implementations use the following logic for add and retrieve operations.

• First, identify the “Bucket” to use using the “key” hash code.

• If there are no objects present in the bucket with the same hash code, then add the object for Add operation and return null for retrieve operation.

• If there are other objects in the bucket with the same hash code, then “key” equals method is used

• If equals() returns true and it’s an add operation, then the object value is overridden.

• If equals() return false and it’s a retrieve operation, then a new entry is added to the bucket.

• If equals() return true and it’s a retrieve operation, then object value is returned.

• If equals() return false and it’s a retrieve operation, then null is returned.

Hash Collision:

The phenomenon when two keys have the same hash code is called a hash collision. If the HashCode() method is not implemented properly, there will be a higher number of hash collisions and map entries will not be properly distributed causing slowness in the retrieve and store operations.

Difference between Generic and Non-Generic Collection

	NON-GENERIC	GENERIC
Source Code Size	Larger: You need a new implementation for each type	Smaller : You need inly one implementation regardless of the number of constructed types
Executable Size	The compiled version of each stack is present, regardless of whether it is used	Only types for which there is constructed types are present in the executable
Ease of writing	easier to write because it is more concrete	Harder to write because its more abstract.
Difficulty to Maintain	More error-prone to maintain since all changes need to be applied for each applicable type	Easier to maintain because modification are needed in only one place.

Resource: Webner Solutions, javapoint, wikipedia

The Tech Platform

www.thetechplatform.com