In our exploration of data structures in C#, we have already covered arrays, lists, linked lists, stacks, and queues. Now is the time to learn about another remarkably practical and widely used data structure called Hash Tables. In C#, the hash tables are called Dictionaries.
As its name depicts, dictionaries arrange data in key-value pairs just like a normal dictionary. They provide incredibly efficient lookups, insertions, and deletions. By excelling in dictionaries, you can open up a powerful approach to solving complex programming problems in an easy way.
What is a Dictionary (Hash Table)?
A dictionary is a data structure that stores data in key-value pairs. Consider it a real-world dictionary where you look up a word to find its definition. The word represents the key, and its definition represents its value. In hash tables, each piece of data is associated with a unique identifier called Key. The data is then accessed through the key.
Keys and Values
A key represents the unique identifier that is used to retrieve data from a dictionary. It must be distinct so the associated value can be retrieved reliably. The value, on the other hand, is the actual data that is stored in the dictionary.
How Dictionaries Work?
The reason behind calling dictionaries hash tables is the magical process of hashing that helps efficiently retrieve data. When a key-value pair is stored, the key is passed through a hash function that generates an integer called hash code.
This hash code acts as a starting point for an index for an underlying array called a bucket array. The value associated with the hash code is then stored in this location. When we retrieve a value by its key, the same hash function is used on the key to calculate its hash code. This hash code directly leads you to the location of the key in the bucket array. This direct access makes the data retrieval so fast in dictionaries.
Using Dictionaries in C#
C# provides a built-in generic class Dictionary
Creating and Initializing A Dictionary
You can assign a data type, name, and values to a dictionary using the generic class Dictionary<TKey, TValue>. You must specify the data types for both keys and values in dictionaries.
Syntax:
Dictionary dictionary_name = new Dictionary(){{ key,value}, {key,value}, {key,value}};
Example:
Dictionary students = new Dictionary(){
{1, "Hafsa"},{2, "Khizer"},{3, "Kamar"}
};
Adding More Values to the Dictionary
Like a linked list, the size of a dictionary is not pre-defined. Hence, you can add more values to it using the Add() method.
Syntax:
dictionary_name.Add(key, value);
Example:
using System;
using System.Collections.Generic;
class DataStructures {
static void Main() {
Dictionary students = new Dictionary(){
{1, "Sachin"},{2, "Kumar"},{3, "Jennifer"}
};
students.Add(4, "Sanjay"); //Adds Sanjay to the dictionary
students.Add(5, "Kangana"); //Adds Kangana to the dictionary
}
}
Accessing Values by Keys
In dictionaries, we access values by keys rather than index numbers.
Syntax:
dictionary_name[key];
Example:
using System;
using System.Collections.Generic;
class DataStructures {
static void Main() {
Dictionary students = new Dictionary(){
{1, "Sachin"},{2, "Kumar"},{3, "Jennifer"}
};
Console.WriteLine(students[1]); //Prints Sachin
}
}
Checking if a Key Exists in a Dictionary
With the ContainsKey() method, you can check whether a key exists in a dictionary. It returns true if the key is found. Else returns false.
Syntax:
dictionary_name.ContainsKey(key);
Example:
using System;
using System.Collections.Generic;
class DataStructures {
static void Main() {
Dictionary students = new Dictionary(){
{1, "Sachin"},{2, "Kumar"},{3, "Jennifer"}
};
Console.WriteLine(students.ContainsKey(4)); //Prints False
}
}
Removing Data From a Dictionary
The Remove() method defined in the generic class Dictionary<TKey, TValue> allows you to remove key-value pairs from dictionaries.
Syntax:
dictionary_name.Remove(key);
Example:
using System;
using System.Collections.Generic;
class DataStructures {
static void Main() {
Dictionary students = new Dictionary(){
{1, "Sachin"},{2, "Kumar"},{3, "Jennifer"}
};
students.Remove(2); //Removes Kumar from the dictionary
}
}
Iterating Through Keys, Values, and Key-Value Pairs
There exists multiple properties for retrieving keys, values as well as the key-value pairs in Dictionary<TKey, TValue> class. For iterating through these, we use the foreach loop.
Iterating Through Keys
Syntax:
dictionary_name.Keys;
Example:
using System;
using System.Collections.Generic;
class DataStructures {
static void Main() {
Dictionary students = new Dictionary(){
{1, "Sachin"},{2, "Kumar"},{3, "Jennifer"}
};
foreach(int key in students.Keys)
{
Console.WriteLine(key); //Prints all the keys
}
}
}
Iterating Through Values
Syntax:
dictionary_name.Values;
Example:
using System;
using System.Collections.Generic;
class DataStructures {
static void Main() {
Dictionary students = new Dictionary(){
{1, "Sachin"},{2, "Kumar"},{3, "Jennifer"}
};
foreach(string value in students.Values)
{
Console.WriteLine(value); //Prints all the values
}
}
}
Iterating Through Key-Value Pairs
Syntax:
dictionary_name.KeyValuePair;
Example:
using System;
using System.Collections.Generic;
class DataStructures {
static void Main() {
Dictionary students = new Dictionary(){
{1, "Sachin"},{2, "Kumar"},{3, "Jennifer"}
};
foreach(KeyValuePair student in students)
{
Console.WriteLine(student); //Prints all the keys and values
}
}
}
Some Additional Concepts
Although we have already covered the most widely used functions and properties in Dictionaries, it is good to be familiar with some additional core concepts that come in handy in various situations. Let’s take a brief look at those:
Hash Function
A hash function plays a crucial role in using the hash tables. It generates a unique hash code for each key for easy data access.
Collisions
Collisions occur when a hash function generates the same hash code for two or more keys. A good hash function tries to avoid collisions by evenly distributing keys, but collisions still happen especially when there are too many key-value pairs.
Resolving Collisions
Since the collisions are inevitable, the hash tables use the following techniques to resolve them:
i. Separate Chaining: All the indices in the bucket array point to another data structure that stores the key-value pairs that hash to the same index.
ii. Open Addressing: The algorithm uses the next available slot in the memory to store the colliding key-value pair.
Real-World Applications of Dictionaries
Dictionaries are a widely used data structure in software development.
- Caching: The frequently accessed applications are stored in the hash tables for quick retrieval, making the application perform better.
- Storing Configuration Settings: The application configurations are stored in key-value pairs representing the dictionaries.
- Indexing in Database: Hash indexes are used to retrieve specific keys quickly.
Besides these, there are many more use cases of dictionaries. Grasping a good understanding of their structure and working brings you numerous benefits. In this article, we have covered all the core concepts of dictionaries in C#.
