Hash tables in practice🐯

Today let's learn what hash tables are and how fast they are.

🤔 What are hash tables?

Hash tables, also known as hash maps or dictionaries in various programming languages, are data structures that store key-value pairs. They offer efficient insertion, deletion, and retrieval of elements, making them widely used in computer science and software development.

🚀 What are its advantages?

The main advantage of using hash tables is its fast lookup because of constant-time average-case performance for insertion, deletion, and retrieval operations.

This means that regardless of the data set size, the time it takes to find, insert, or remove an element remains relatively constant, making hash tables ideal for applications requiring fast lookups.

According to Freecodecamp in the Big O notation, when your algorithm is not dependent on the input size n, it is said to have a constant time complexity with order O(1). This means the run time will always be the same regardless of the input size.

🟣 Hash tables in ASP.NET Core

In ASP.NET Core, hash tables are typically implemented using the System.Collections namespace. There are 3 ways to implement hash tables:

1. Hashtable Class: This class is available in the System.Collections namespace and provides a classic implementation of a hash table data structure. It allows you to store key-value pairs where keys must be unique. It provides fast lookup and retrieval of elements based on the hash code of the keys.
   Example:
   

   using System.Collections;
   
   var hashtable = new Hashtable();
   hashtable.Add("key1", "value1");
   hashtable.Add("key2", "value2");
   

2. Dictionary Class: This is a generic type that provides a strongly typed implementation of a hash table. It allows the storage of key-value pairs where the keys must be unique and provides compile-time type safety.
   Example:
   

   using System.Collections.Generic;
   
   var dictionary = new Dictionary<string, string>();
   dictionary.Add("key1", "value1");
   dictionary.Add("key2", "value2");
   

3. ConcurrentDictionary Class: This class is similar to Dictionary<TKey, TValue> but is designed to be used in multi-threaded scenarios. It provides thread-safe operations without the need for external synchronization.
   Example:
   

   using System.Collections.Concurrent;
   
   var concurrentDictionary = new ConcurrentDictionary<string, string>();
   concurrentDictionary.TryAdd("key1", "value1");
   concurrentDictionary.TryAdd("key2", "value2");
   

These are the most commonly used hash table implementations in ASP.NET Core applications, and each one has its advantages and use cases depending on your specific requirements, such as performance, thread safety, and type safety.

🥊 Hash tables VS Lists

To see how fast hash tables are compared to lists, let's implement a simple code in C#.

So, to create a new console application, you can use the following command:

dotnet new console -n HashTableInPractice

Open the project and in the Program.cs file put the code below:

List<Contact> contactsList =
[
    new Contact("John", "123-456-7890"),
    new Contact("Alice", "987-654-3210"),
    new Contact("Bob", "555-123-4567"),
    new Contact("Zoe", "999-888-7777"),
];

string targetContact = "Alice";

DateTime startList = DateTime.Now;
string phoneNumberFromList = contactsList.FirstOrDefault(c => c.Name == targetContact).PhoneNumber;
DateTime endList = DateTime.Now;
TimeSpan listTime = endList - startList;

Dictionary<string, string> contactsDictionary = new Dictionary<string, string>();
contactsDictionary["John"] = "123-456-7890";
contactsDictionary["Alice"] = "987-654-3210";
contactsDictionary["Bob"] = "555-123-4567";
contactsDictionary["Zoe"] = "999-888-7777";

DateTime startDictionary = DateTime.Now;
string phoneNumberFromDictionary = contactsDictionary.ContainsKey(targetContact) ? contactsDictionary[targetContact] : "Contact not found";
DateTime endDictionary = DateTime.Now;
TimeSpan dictionaryTime = endDictionary - startDictionary;

Console.WriteLine("Phone number for " + targetContact + " from List: " + phoneNumberFromList);
Console.WriteLine("Search time in List: " + listTime.TotalMilliseconds + " ms");

Console.WriteLine("Phone number for " + targetContact + " from Dictionary: " + phoneNumberFromDictionary);
Console.WriteLine("Search time in Dictionary: " + dictionaryTime.TotalMilliseconds + " ms");

class Contact
{
    public string Name { get; set; }
    public string PhoneNumber { get; set; }

    public Contact(string name, string phoneNumber)
    {
        Name = name;
        PhoneNumber = phoneNumber;
    }
}

In the code above we defined a List which is a collection class provided by the .NET framework that can store elements of any data type and dynamically resize itself.

We also define a Dictionary which is a collection that stores key/value pairs and is more efficient than the List for accessing elements by key.

Then we populate both with the same data, then we define the variable targetContact which represents the name of the contact whose phone number we want to find.

We then measure the time needed to look up the phone number associated with targetContact in both the List and the Dictionary.

Finally, the code prints the phone number associated with the targetContact and the time needed to look it up in both the List and the Dictionary.

Now let's run the application and see how each one performs. So, to execute the application, you can use the following command:

dotnet run

So your terminal will display the following result:

Note that the search time in List was 13,5219 milliseconds 😪 while in Dictionary it was only 0,004 milliseconds 😎.

☕ Conclusion

The Dictionary is a data structure that uses an internal hash table to store its elements, which allows much faster access to items by key. Therefore, the search is practically instantaneous, even with a large number of elements.

In scenarios where fast key lookup is crucial, like in this case, Dictionary is the superior choice compared to List.