Collections

Collections:

It holds many values or objects in a specific series.
The two types of collections in C# :

• Non-generic collections
• Generic collections

NON-GENERIC COLLECTIONS

Hierarchical structure of non-generic collections:

<interface> IEnumerator
<interface> IEnumerable
<interface> ICollection
<interface> IDictionary
Hashtable
Sorted list
<interface> IList
ArrayList
BitArray
Queue
Stack

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

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.

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

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

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

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

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.

SortedList:
It stores key and value pairs. By default, it arranges the elements in ascending order of keys.

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.

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.

Hashtable:
It stores key-value pairs. It compares the hash value of the keys to retrieve the values.

ArrayList

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.

Methods:

• Add()
  The method adds a single element at the end of the ArrayList.
• AddRange()
  The method adds all the elements from the specified collection into ArrayList
• Insert()
  The method adds a single element at the specified index in ArrayList.
• InsertRange()
  The method inserts all elements of the specified collection starting from the specified index.
• Remove()
  The method removes the specified element from the ArrayList.
• RemoveRange()
  The method removes a range of elements from the ArrayList.
• RemoveAt()
  It removes the element at the specified index from the ArrayList.
• Sort()
  Sorts entire elements of ArrayList
• Reverse()
  Reverses the order of the elements in the entire ArrayList.
• Contains
  Checks whether the specified element exists in the ArrayList or not. Returns true if exists otherwise false.
• Clear
  Removes all elements in the ArrayList.
• CopyTo
  Copies all elements or range of elements to a compatible array.
• GetRange
  Returns a specified number of elements from the specified index of ArrayList.
• IndexOf
  Search specified element and returns zero-based index if found. Returns -1 if element not found.
• ToArray
  Returns a compatible array from an ArrayList.

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.
Properties:

• capacity :
  Gets or sets the number of elements that the SortedList instance can store.
• Count :
  Gets the number of elements actually contained in the SortedList.
• IsFixedSize :
  Gets a value indicating whether the SortedList has a fixed size.
• IsReadOnly :
  Gets a value indicating whether the SortedList is read-only.
• Item :
  Gets or sets the element at the specified index.
• Keys :
  Gets the list of keys of SortedList.
• Values :
  Get a list of values in SortedList.

Methods:

• Add(object key, object value)
  The method adds a single element at the end of the SortedList.
• Remove(object key)
  The method removes the element with the specified key from the SortedList.
• RemoveAt(int index)
  It removes the element at the specified index from the SortedList.
• Contains(object key)
  Checks whether the specified key exists in the SortedList or not. Returns true if exists otherwise false.
• Clear
  Removes all elements in the SortedList.
• GetByIndex(int index)
  Returns the value stored at the specified index.
• GetKey(int index)
  Returns the key stored at the specified index.
• IndexOfKey(object key)
  Returns an index of the specified key stored.
• IndexOfValue(object value)
  Returns an index of specified value stored.

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.

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.

Methods:

• Add
  Adds an item with a key and value into the hashtable
• Remove
  Removes the item with the specified key from the hashtable.
• Contains
  Checks whether the hashtable contains a specific key.
• ContainsKey
  Checks whether the hashtable contains a specific key
• ContainsValue
  Checks whether the hashtable contains a specific value
• Clear
  Removes all items from the hashtable.
• GetHash
  Returns the hashcode for the specified key.

Stack

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.
Properties:

• Count :
  Returns the total count of elements in the stack

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.

Queue

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.
Properties:

• Count :
  Returns the total count of elements in 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.

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.

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>

Methods:

• Add
  The method adds a single element at the end of the List<T>.
• AddRange
  The method adds all the elements from the specified collection into List<T>
• Insert
  The method adds a single element at the specified index in List<T>.
• InsertRange
  The method inserts all elements of the specified collection at the specified index.
• Remove
  The method removes the first occurrence of the specified element from the List<T>.
• RemoveRange
  The method removes all the elements that match with the supplied predicate function from the List<T>.
• RemoveAt
  It removes the element at the specified index from the List<T>.
• Sort
  Sorts entire elements of List<T>
• Contains
  Checks whether the specified element exists in the List<T> or not. Returns true if exists otherwise false.
• Clear
  Removes all elements in the List<T>.
• BinarySearch
  Search the element and return the index of the element.
• Find
  Finds the first element based on the specified predicate function
• Foreach
  Iterates through a List<T>
• TrimExcess
  Sets the capacity to the actual number of elements.
• TrueForAll
  Determines whether every element in the List matches the conditions defined by the specified predicate.

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.

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.

<datatype> [] <ArrayName> = new <datatype>[size];
Properties:

• Length
  Returns the total number of elements in the array.

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.

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.

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.

Best Practices for implementing Equals() and HashCode() method

• Use the same properties in both equals() and hashCode() method implementations, so that their contract doesn’t violate when any properties are updated.
• It’s better to use immutable objects as Hash table keys so that we can cache the hash code rather than calculating it on every call. That’s why String is a good candidate for a Hash table key because it’s immutable and can cache the hash code value.
• Implement hashCode() method so that the least number of hash collisions occurs and entries are evenly distributed across all the buckets.

BEST PRACTICES FOR COLLECTIONS:

• Use strongly typed collections(generic i.e which gives compile-time error for typecasting and should have used a single type of keys).
• Use ArrayList or List<T> only in internal implementation.
• Use IDictionary <TKey, TValue> and not Hashtable or Dictionary<TKey,TValue>.
• Do prefer collections over arrays.
• Consider using arrays in low-level APIs to minimize memory consumption and maximize performance.
• Use the “Collection” suffix in names of types implementing.
• Use the “ReadOnly” prefix in the names of read-only collections.
• 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.