Hash Table Implementation in C++ With Example

Introduction

Hash tables, also known as hash maps, are fundamental data structures in computer science that provide efficient key-value pair storage and retrieval. They are widely used to build data storage and indexing systems, databases, and various algorithms and applications that require quick data access. In this article, we will delve into the implementation of a hash table in C++.

What is a Hash Table in C++?

A hash table is a data structure that stores key-value pairs. It uses a hash function to map each key to an index in an array. This index is used to store and retrieve the corresponding value. 

The key idea behind hash tables is to achieve constant-time O(1) average complexity for insertion, deletion, and retrieval operations.

Working of Hash Tables.

To understand the inner workings of a Hash Table, you need to understand the three important terms explained below:

Hash Function: When a key is provided, a hash function converts the key into an integer called a hash code. This hash code is used to determine the index in the hash table where the value associated with the key will be stored.

Index Mapping: The hash code is mapped to an index in the hash table's underlying array. This process ensures that different keys are distributed uniformly across the array.

Collision Handling: Since hash functions can produce the same hash code for different keys (known as collisions), hash tables need collision resolution strategies. There are various methods to handle collisions, such as chaining or open addressing. 

You can read our detailed article on "How To Resolve Collision in Hash Table?" to get a better understanding.

Chaining Method: This strategy involves storing multiple values at the same index using a data structure like a linked list. (alert-passed)

Open Addressing Method: In this approach, when a collision occurs, the algorithm searches for the next available slot (based on a predefined sequence) and places the data there. (alert-passed)

So these are the steps and working of a hash table that we use for solving many complex coding problems.

Implementation of Hash Table in C++.

Implementing a hash table from scratch involves designing the data structure, defining hash functions, handling collisions, and providing methods for insertion, retrieval, and deletion. 

Below we have implemented a simple Hash Table in C++ using Array and Linked List for collision resolution. 

C++ Example Code: 

// C++ code for the implementation of Hash Table
#include <iostream>
#include <list>
using namespace std;

// HashTable class
class HashTable {
private: 
    // Size of the hash table
    static const int tableSize = 10;
    // Array of linked lists
    list<pair<int, int>> table[tableSize];
    
    // Hash function to map key to an index
    int hashFunction(int key) {
        return key % tableSize;
    }

public:
    // Insert a key-value pair into the hash table
    void insert(int key, int value) {
        int index = hashFunction(key);
        table[index].emplace_back(key, value);
    }
    
    // Get the value associated with a key
    int search(int key) {
        int index = hashFunction(key);
        for (const auto& pair : table[index]) {
            if (pair.first == key) {
                return pair.second;
            }
        }
        return -1; // Key not found
    }
    
    // Remove a key-value pair from the hash table
    void remove(int key) {
        int index = hashFunction(key);
        table[index].remove_if([&key](const std::pair<int, int>& pair) {
            return pair.first == key;
        });
    }
};

int main() {
    HashTable ht;

    ht.insert(101, 10);
    ht.insert(201, 20);
    ht.insert(302, 30);

    cout << "Value at key 201: " << ht.search(201) << endl;

    ht.remove(201);
    cout << "Value at key 201 after removal: " << ht.search(201) << endl;

    return 0;
}

Output:

Value at key 201: 20
Value at key 201 after removal: -1

Explanation:

1. We define a HashTable class that contains an array of linked lists (table) to store the key-value pairs.

2. The hashFunction method calculates the index for a given key using the modulo operation.

3. The insert method inserts a key-value pair into the appropriate linked list.

4. The get method searches for a key and returns its associated value.

5. The remove method removes a key-value pair from the linked list.

6. In the example usage, we create a hash table, insert key-value pairs, search for a value, and remove a key.

This is the basic working and implementation of the Hash Table (Hash Map) in C++ and implementing it from scratch gives us a better understanding of how it works and its application.

C++ Standard Library (STL) Hash Containers.

In real-life usage, we need not to implement a complete Hash Table from the beginning because C++ provides hash containers as part of the Standard Template Library (STL) that make it easy to use hash tables:

• std::unordered_map: This is an implementation of a hash table that stores key-value pairs. It provides fast access, insertion, and deletion operations.

• std::unordered_set: This is a hash table that stores unique elements, allowing efficient membership checking.

Here's an C++ example of how to use std::unordered_map and std::unordered_set:

// C++ code for working of unordered_map and unordered_list
#include <iostream>
#include <unordered_map>
#include <unordered_set>
using namespace std;

int main() {
    unordered_map<string, int> scores;
    scores["Alice"] = 95;
    scores["Bob"] = 85;

    cout << "Alice's score: " << scores["Alice"] << endl;

    unordered_set<int> uniqueNumbers;
    uniqueNumbers.insert(5);
    uniqueNumbers.insert(10);

    if (uniqueNumbers.find(5) != uniqueNumbers.end()) {
        cout << "Number 5 found!" << endl;
    }

    return 0;
}

Output:

Alice's score: 95
Number 5 found!

In this example, we've used std::unordered_map to store student scores and std::unordered_set to store unique numbers.

Usage of Hash Tables.

Hash tables have a wide range of applications due to their fast retrieval times. Some common use cases include:

• Databases: Hash tables are used for indexing and searching records in databases.

• Caching: They are used to cache frequently accessed data for quick retrieval.

• Compiler Symbol Tables: Hash tables store identifiers (variable names, function names) and their corresponding attributes in compilers.

• Implementing Sets and Maps: Hash tables are used to implement set and map data structures.

• Network Routing Tables: Hash tables can help route network packets efficiently.

Conclusion.

Hash tables are powerful data structures that enable efficient storage and retrieval of key-value pairs. Remember that real-world hash tables may require handling more complex collision resolution methods, resizing, and more advanced hash functions.

C# Program to Check if a given Year is a Leap Year or Not.

A leap year is a year that contains an extra day, February 29th, making it 366 days instead of the usual 365 days. Leap years are important to ensure that our calendar remains in sync with the solar year.

In this article, we will explore how to write a C# program to determine if a given year is a leap year or not.

Problem Statement.

Write a C# program to check whether a given year is a leap year or not.

Leap Year Criteria

A year is a leap year if it meets one of the following criteria:

• The year is evenly divisible by 4, but not divisible by 100.
• The year is divisible by 400.

Example

Let's say we want to check whether the year 2024 is a leap year or not.

Steps to check Leap Year:

• Check if the year is divisible by 4: 2024 % 4 = 0
• Check if the year is not divisible by 100: 2024 % 100 != 0
• Since both conditions are met, 2024 is a leap year.

C# Code to Check a Leap Year.

//C-sharp program to check given year is leap year or not
using System;

class Program {
    static void Main(string[] args) {
        Console.Write("Enter a year: ");
        int year = int.Parse(Console.ReadLine());

        bool isLeapYear = (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);

        if (isLeapYear) {
            Console.WriteLine($"{year} is a leap year.");
        } else {
            Console.WriteLine($"{year} is not a leap year.");
        }
    }
}

Output:

Enter a year: 2023
2023 is not a leap year.

Explanation:

1. We take input from the user for the year.

2. We use the ternary operator (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0) to check whether the year meets the leap year criteria.

3. If the condition is true, we output that the year is a leap year. Otherwise, we output that it is not a leap year.

C# Program to Find the Maximum of Three Numbers using Ternary Operators.

In this article, we'll explore using the ternary operator to find the maximum of three numbers in a C# program.

Problem Statement: Using ternary operators, write a C# program to find the maximum among three given numbers.

Example: 

Input: num1 = 11, num2 =12, num3 = 7
Output: Largest Number = 12

Input: num1 = 4, num2 = -2, num3 = 5
Output: Largest Number = 5

Let's understand Ternary Operators before moving to the coding part to find the largest number among the three.

What are Ternary Operators?

The ternary operator, also known as the conditional operator, is a concise way to express simple conditional statements in programming languages like C#. It provides a compact syntax to perform an operation based on a condition. 

The general syntax of the ternary operator is:

condition ? expression_if_true : expression_if_false

Here's a breakdown of how the ternary operator works:

• The condition is an expression that evaluates to either true or false.
• If the condition is true, the value of expression_if_true is returned.
• If the condition is false, the value of expression_if_false is returned.

I hope you get a basic idea of how Ternary operators work. Now let's use them to find the largest number.

C# Code to Find a Maximum of Three Numbers using Ternary Operators.

using System;

namespace MaximumOfThreeNumbers
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("Enter the first number: ");
            int num1 = Convert.ToInt32(Console.ReadLine());

            Console.Write("Enter the second number: ");
            int num2 = Convert.ToInt32(Console.ReadLine());

            Console.Write("Enter the third number: ");
            int num3 = Convert.ToInt32(Console.ReadLine());

            int max = (num1 > num2) ? (num1 > num3 ? num1 : num3) : (num2 > num3 ? num2 : num3);

            Console.WriteLine($"The maximum number is: {max}");
        }
    }
}

Output:

Enter the first number: 20
Enter the second number: 10
Enter the third number: 9
The maximum number is: 20

Ternary operators offer a concise way to perform conditional operations and are especially useful when comparing multiple values.

Similar articles:

• C# Program to Calculate the Simple Interest.
• C# Program to Calculate the Factorial of a Number using Loop.
• C# Program to check if a given number is Even or Odd.

C# Program to Calculate the Simple Interest.

Calculating simple interest is a basic financial calculation used to determine the interest earned or paid on a principal amount over a specific period. In this article, we'll learn how to write a C# program to calculate simple interest.

Problem Statement: Write a C# program to calculate the simple interest given the principal amount, rate, and time.

Example:

Suppose the principal amount is $1000, the interest rate is 5%, and the time is 3 years. The program should output:

Simple Interest: $150.00

Steps to Find Simple Interest.

Below are steps that you need to follow to calculate simple interest:

Step 1: Take inputs for principal amount, rate, and time from the user.

Step 2: Calculate simple interest using the formula: Simple Interest = (Principal * Rate * Time) / 100.

Step 3: Print the calculated simple interest.

C# Code to Find Simple Interest.

// C-sharp code implementation to calculate simple interest
using System;

namespace SimpleInterestCalculator
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("Enter the principal amount: ");
            double principal = Convert.ToDouble(Console.ReadLine());

            Console.Write("Enter the interest rate (in percentage): ");
            double rate = Convert.ToDouble(Console.ReadLine());

            Console.Write("Enter the time (in years): ");
            double time = Convert.ToDouble(Console.ReadLine());

            double simpleInterest = (principal * rate * time) / 100;

            Console.WriteLine($"Simple Interest: ${simpleInterest:F2}");
        }
    }
}

Output:

Enter the principal amount: 1000
Enter the interest rate (in percentage): 8
Enter the time (in years): 4
Simple Interest: $320.00

Similar articles:

• C# Program to Find the largest among three numbers.
• C# Program to check if a given number is Even or Odd.
• C# Program to Calculate the Factorial of a Number.

C# Program to Find the largest among three numbers.

In many programming scenarios, you might need to determine the largest number among a set of values. This is a common problem and can be solved using conditional statements. In this article, we'll learn how to write a C# program to find the largest among three numbers.

Problem Statement: Write a C# program that finds the largest among three given numbers.

Example:

Input: num1 = 10, num2 =12, num3 = 7
Output: Largest Number = 12

Input: num1 = 8, num2 = -2, num3 = 5
Output: Largest Number = 8

C# Code to Find the Largest Number Among Three.

//C-sharp code to find largest among three numbers
using System;

namespace LargestNumberFinder
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("Enter three numbers: ");
            int num1 = Convert.ToInt32(Console.ReadLine());
            int num2 = Convert.ToInt32(Console.ReadLine());
            int num3 = Convert.ToInt32(Console.ReadLine());

            int largest = num1;

            if (num2 > largest)
            {
                largest = num2;
            }

            if (num3 > largest)
            {
                largest = num3;
            }

            Console.WriteLine($"Largest number among {num1}, {num2}, and {num3} is {largest}.");
        }
    }
}

Output:

Enter three numbers: 10
23
9
Largest number among 10, 23, and 9 is 23.

Code Explanation:

• The program takes three integers as input using the Console.Write and Console.ReadLine functions.

• It initializes the largest variable with the value of the first input.

• Using a series of if statements, it compares the other two inputs with the largest variable and updates it if a larger value is found.

C# Program to Calculate the Factorial of a Number using Loop.

Factorial is a mathematical operation that is used quite often in programming. It involves multiplying a given number by all positive integers that are less than it. In this article, we'll explore how to write a C# program to calculate the factorial of a given number.

Problem Statement: Write a C# program that calculates the factorial of a positive integer.

Example:

Input: num = 5
Output: Factorial of 5 = 120

Explanation: 5 x 4 x 3 x 2 x 1 = 120

Input: num = 7
Output: Factorial of 7 = 5040

Steps to Find Factorial of a Number.

Below are the steps that need to be followed to Find a Factorial of a number in C-Sharp.

Step 1: Take a positive integer input from the user.

Step 2: Initialize a variable factorial to 1. This will store the result of the factorial operation.

Step 3: Use a loop to iterate from 1 to the input number.

Step 4: In each iteration, multiply the factorial by the current iteration value.

Step 5: After the loop completes, the factorial will hold the calculated factorial value.

Step 6: Print the result.

C# Code to Find Factorial of a Number.

// C-sharp code to find factorial of a number.
using System;

namespace FactorialCalculator
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("Enter a positive integer: ");
            int number = Convert.ToInt32(Console.ReadLine());

            int factorial = 1;
            for (int i = 1; i <= number; i++)
            {
                factorial *= i;
            }

            Console.WriteLine($"Factorial of {number} is {factorial}.");
        }
    }
}

Output:

Enter a positive integer: 7
Factorial of 7 is 5040.

Code Explanation:

1. The program takes a positive integer as input using the Console.Write and Console.ReadLine functions.

2. It then uses a for loop to iterate from 1 to the input number.

3. Inside the loop, the factorial variable is updated by multiplying it with the current value of i.

4. After the loop completes, the program prints the calculated factorial value.

C# Program to check if a given number is Even or Odd.

Even numbers are those that are divisible by 2 without leaving a remainder, while odd numbers are not divisible by 2 without a remainder. In this article, we will explore how to write a simple C# program to check if a given number is even or odd.

Problem Statement: Write a C# program that takes an integer as input and determines whether it is an even or odd number.

Example:

Input: num = 7
Output: 7 is an Odd Number.

Explanation: 7 % 2 = 1

Input: num = 10
Output: 10 is an Even Number.

Explanation: 10 % 2 = 0

Steps to Check Even and Odd Numbers.

Below are the steps that you need to follow to check if the given number is odd or even.

Step 1: Start by taking an integer input from the user.

Step 2: Use the modulo operator % to check if the remainder of dividing the input number by 2 is zero or not.

Step 3: If the remainder is zero, it's an even number. Otherwise, it's an odd number.

Step 4: Print the appropriate message based on the result.

C# code to check Even and Odd Numbers.

// C-sharp code check if a number is even or odd
using System;

namespace EvenOddChecker
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("Enter an integer: ");
            int number = Convert.ToInt32(Console.ReadLine());

            if (number % 2 == 0)
            {
                Console.WriteLine($"{number} is an Even number.");
            }
            else
            {
                Console.WriteLine($"{number} is an Odd number.");
            }
        }
    }
}

Output:

Enter an integer: 12
12 is an Even number.

Code Explanation:

We use the Console.Write and Console.ReadLine functions to take input from the user. The % operator calculates the remainder when the number is divided by 2. If the remainder is zero, the number is even; otherwise, it's odd.

C# Program to Convert Fahrenheit to Celsius.

In this article, we'll explore how to create a simple C# program that takes a temperature in Fahrenheit as input and converts it to Celsius.

Problem Statement: Write a C# program that converts a temperature in Fahrenheit to Celsius. Take the temperature in Fahrenheit as user input and display the converted temperature in Celsius.

Example:

Input:
Fahrenheit: 98.6

Output:
98.6°F is equal to 37°C

The formula to convert temperature from Fahrenheit (°F) to Celsius (°C) is as follows:

Celsius (°C) = (Fahrenheit (°F) - 32) × 5/9

C# Code to Convert Fahrenheit to Celsius.

// C-sharp code to calculate celsius
using System;

namespace TemperatureConverter
{
    class Program
    {
        static void Main(string[] args)
        {
            // Read temperature in Fahrenheit from the user
            Console.Write("Enter the temperature in Fahrenheit: ");
            double fahrenheit = Convert.ToDouble(Console.ReadLine());

            // Convert Fahrenheit to Celsius using the formula
            double celsius = (fahrenheit - 32) * 5 / 9;

            // Display the converted temperature
            Console.WriteLine($"{fahrenheit} F is equal to {celsius:F2} C");

            // Keep the console window open
            Console.ReadLine();
        }
    }
}

Output:

Enter the temperature in Fahrenheit: 45
45 F is equal to 7.22 C

C# Program to Calculate Area of Rectangle.

Calculating the area of a rectangle is a fundamental mathematical operation often encountered in programming. In this article, we'll explore how to write a simple C# program to calculate the area of a rectangle using user-provided input. 

Problem Statement: Write a C# program that takes the length and width of a rectangle as user input and calculates its area. Display the result to the user.

Example: 

Input:
Length (L): 8
Width (W): 5

Output: The area of the rectangle is: 40

Explanation: 
Area = L x W
     = 8 x 5
     = 40

C# Code to Calculate Area of Rectangle.

//C-sharp code to calculate area of Rectangle
using System;

namespace RectangleAreaCalculator
{
    class Program
    {
        static void Main(string[] args)
        {
            // Read length and width from the user
            Console.Write("Enter the length of the rectangle: ");
            double length = Convert.ToDouble(Console.ReadLine());

            Console.Write("Enter the width of the rectangle: ");
            double width = Convert.ToDouble(Console.ReadLine());

            // Calculate the area
            double area = length * width;

            // Display the area
            Console.WriteLine($"The area of the rectangle is: {area}");

            // Keep the console window open
            Console.ReadLine();
        }
    }
}

Output:

Enter the length of the rectangle: 8
Enter the width of the rectangle: 4
The area of the rectangle is: 32

Code Explanation:

In the above C-sharp program, Convert.ToDouble() is used to convert the user input from strings to double values for calculations. We also need to add Console.ReadLine() at the end keeps the console window open until the user presses Enter.

This program demonstrates basic user input, data conversion, arithmetic operation, and output formatting in C#. 

C# Program to Input Two Numbers and Display their Sum.

In this C# programming example, we will learn how to take input from the user for two numbers, calculate their sum, and display the result. This basic program will help you understand how to interact with the user and perform simple arithmetic operations in C#.

Problem Statement: Write a C# program that takes two numbers as input from the user, calculates their sum, and displays the result.

Example:

Enter the first number: 5
Enter the second number: 7
The sum of 5 and 7 is: 12

C# Code to Find the Sum of Two Numbers.

//C-sharp code to print sum of two number
using System;

namespace SumCalculator
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("Enter the first number: ");
            //coverting input string to integer value
            int num1 = Convert.ToInt32(Console.ReadLine());

            Console.Write("Enter the second number: ");
            int num2 = Convert.ToInt32(Console.ReadLine());

            int sum = num1 + num2;

            Console.WriteLine($"The sum of {num1} and {num2} is: {sum}");
        }
    }
}

Output:

Enter the first number: 12
Enter the second number: 10
The sum of 12 and 10 is: 22

Code Explanation:

Inside the Main method of the above C# code:

• Console.Write("Enter the first number: "); displays a message asking the user to enter the first number.

• int num1 = Convert.ToInt32(Console.ReadLine()); reads the user's input and converts it to an integer.

• Similar steps are followed to get the second number.

• int sum = num1 + num2; calculates the sum of the two numbers.

• Console.WriteLine($"The sum of {num1} and {num2} is: {sum}"); displays the result using string interpolation.

Key Points:

• The Convert.ToInt32() method is used to convert the user's input (which is a string) into an integer.

• The $ symbol is used for string interpolation, which allows us to embed expressions within strings for dynamic output.

• The Console.ReadLine() method reads the entire line of text entered by the user, including spaces.

This program demonstrates how to interact with the user, perform arithmetic operations, and output results in C#.

C# program to print 'Hello, World!' to the console.

In this article, we will write our first C# program in which we will learn how to print the message "Hello World" on the Console screen. This is an introduction program we write whenever we start learning any new programming language as a beginner.

Example: 

Output: Hello, World!

Steps to Print a Message on Console in C#.

We need to follow the below steps to print our message to the console screen:

Step 1: Open a C# development environment such as Visual Studio or Visual Studio Code.

Step 2: Create a new C# project or open an existing one.

Step 3: Inside the project, create a new C# source code file with the ".cs" extension.

Step 4: In the source code file, use the Console.WriteLine() statement to print "Hello, World!" to the console.

Step 5: Save the file.

Step 6: Build and run the program to see the output.

C# Code Implementation to Print "Hello World!" on Console.

// C# code to print message on console
using System;

namespace HelloWorldApp
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Hello, World!");
        }
    }
}

Output:

Hello, World!

Explanation of Working:

1. The using System; directive includes the System namespace, which contains fundamental classes and base types.

2. The namespace HelloWorldApp encapsulates the program's code in a specific namespace.

3. The class Program defines a class called Program, which is the entry point of the application.

4. The static void Main(string[] args) method is the starting point of execution. It's the method that gets executed when the program is run.

5. Console.WriteLine("Hello, World!"); is a statement that prints "Hello, World!" to the console and adds a newline character at the end.

Key Note:

The Console.WriteLine() method is used to display output to the console and automatically moves to the next line after printing the message. (alert-passed)

If you want to print the message without moving to the next line, you can use Console.Write() instead. (alert-passed)