.NET – Dictionary vs HashTable vs HashSet 📖

First things first, in computing, a hash table is a data structure that stores key-value pairs. Internally, it uses a hash function to compute an index into an array of buckets, from which the desired value can be found. This allows for efficient retrieval, insertion, and deletion of items.

To understand this concept a little better, let's look at the following example I found on Stack Overflow.

data structures - How does a hash table work? - Stack Overflow

To visualize this concept with a real-world analogy, let's imagine a library where we need to easily find books when we need them. A hash table comes to the rescue! We take the title of a book, run it through a computer program (hashing) to get the shelf and slot number, and place the book there.

Then, when we need the book, we compute the hash of the title again and immediately find the shelf number and slot where the book is located.

In our example, the key is the title of the book, the hash represents the book's location after being computed by the hash function, and the value is the content of the book.

While the concept of a hash table may seem straightforward, real-world implementations can be more complex. One such complexity involves handling collisions, where different keys hash to the same index. Despite this, our simple example illustrates the fundamental workings of a hash table.

Now that we understand how a hash table works and have a use case for implementing it in our application, we've only just scratched the surface. Hash tables are versatile and go by many names depending on the context: hash maps, dictionaries, associative arrays, hash sets, and more.

However, navigating these variations can be challenging. Different tech stacks and languages may offer their own implementations and nuances.

.NET Dictionary Collections

In .NET, collections based on the IDictionary interface represent elements that contain both a key and a value. This may sound familiar—it's the foundation of the hashtable concept.

Now, let's delve into the various collection types available in .NET.

Hashtable

The Hashtable class in .NET, found in the System.Collections namespace, is a non-generic collection that stores key-value pairs. It uses a hash function to quickly find values based on their keys, offering efficient retrieval, insertion, and deletion.

SortedList

The SortedList class in .NET, found in the System.Collections.Generic namespace, is a generic collection that stores key-value pairs in sorted order based on the keys. It combines the features of a hash table and a sorted array, allowing fast lookups and sorted access to keys and values.

Dictionary ⭐

The Dictionary class in .NET, found in the System.Collections.Generic namespace, is a generic collection that stores key-value pairs. It provides fast lookups, insertions, and deletions based on keys using a hash table internally.

HashSet

The HashSet class in .NET, found in the System.Collections.Generic namespace, is a generic collection that stores unique elements. It uses a hash table internally to provide fast lookups, insertions, and deletions.

ConcurrentDictionary

The ConcurrentDictionary class in .NET, found in the System.Collections.Concurrent namespace, is a thread-safe collection that stores key-value pairs. It provides high-performance concurrent operations, allowing multiple threads to access and modify the dictionary without needing additional synchronization.

Selecting a Type

Now that you're familiar with some of the collection types available in .NET, how do you choose the correct one for your needs? Here's a quick guide to help you make the right choice.

Generic Types > Nongeneric types

• It is generally better to use generic types, using generic collections in .NET is recommended because they provide type safety, better performance, clearer code, compiler checks, and ease of use compared to non-generic collections.
  • Dictionary and ConcurrentDictionary are the generic classes that correspond to Hashtable.
  • Use SortedList instead of the nongeneric SortedList.
  • Use HashSet instead of the nongeneric HashSet.

Sorted vs Nonsorted

The choice between using sorted and non-sorted dictionary types depends on the specific needs of your application. Use a sorted type when you require the keys to be maintained in a sorted order. These collections are beneficial when you need to iterate over the elements in a sorted manner or perform range queries. The SortedDictionary is more efficient for frequent insertions and deletions, while the SortedList is more memory-efficient for smaller datasets with infrequent modifications.

On the other hand, use a Dictionary or ConcurrentDictionary when you prioritize performance for fast lookups, insertions, and deletions without caring about the order of keys. The Dictionary is ideal for single-threaded scenarios, while the ConcurrentDictionary provides thread-safe operations for concurrent access. Each type has its strengths, and selecting the appropriate one depends on whether your primary need is ordered iteration or optimal performance for dynamic data operations.

Dictionary is Your Friend

As indicated by the star emoji above, in .NET, when you need a hash table, you should typically use the Dictionary type. It is often the preferred choice for hash tables due to its high performance, with average O(1) time complexity for lookups, insertions, and deletions. It is easy to use, offering a clear API, and supports a wide range of key types.

Here is a brief example on how to use it.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // Create a new dictionary with keys of type string and values of type int
        Dictionary<string, int> myDictionary = new Dictionary<string, int>();

        // Add some key-value pairs to the dictionary
        myDictionary.Add("apple", 10);
        myDictionary.Add("banana", 5);
        myDictionary.Add("orange", 8);

        // Access and print the value associated with the "apple" key
        Console.WriteLine("Number of apples: " + myDictionary["apple"]);

        // Check if the dictionary contains a key
        if (myDictionary.ContainsKey("banana"))
        {
            Console.WriteLine("Number of bananas: " + myDictionary["banana"]);
        }

        // Iterate over all key-value pairs in the dictionary
        foreach (var pair in myDictionary)
        {
            Console.WriteLine("Key: " + pair.Key + ", Value: " + pair.Value);
        }
    }
}

---

Understanding and effectively using collection types like hash tables, dictionaries, and hash sets in .NET is crucial for maintaining organized data and ensuring your applications run efficiently. Each collection type has its strengths, and choosing the right one can significantly impact performance and usability. Dive into these collections and discover the best fit for your .NET application needs to optimize your development process and enhance your software's functionality. 🫡