Introduction:

Hash tables are fundamental data structures used to store and retrieve data efficiently. They offer fast access and retrieval times, making them essential in various programming applications. In this blog, we will explore the concept of hash tables and implement our custom hash table in C#. We will dive into the inner workings of hash functions, collision handling, and resizing techniques, ensuring a comprehensive understanding of this powerful data structure. Let's begin our journey into building a robust and efficient hash table!

Method 1: Creating the Hash Table

To start, let's create a class for our hash table and initialize its basic structure. Our hash table will be an array-based implementation, allowing us to store key-value pairs efficiently.

using System;

public class HashTable<TKey, TValue>
{
    private const int InitialCapacity = 10;
    private const double LoadFactor = 0.75;

    private Entry<TKey, TValue>[] table;
    private int size;

    // Inner class for key-value entries
    private class Entry<TKey, TValue>
    {
        public TKey Key { get; set; }
        public TValue Value { get; set; }
        public Entry<TKey, TValue> Next { get; set; }
    }

    public HashTable()
    {
        table = new Entry<TKey, TValue>[InitialCapacity];
        size = 0;
    }

    // Other methods will be added here
}

In this code, we start by defining a generic class HashTable<TKey, TValue>, which can store any data types for both keys and values. The InitialCapacity constant sets the initial size of the array. We use the LoadFactor constant to determine when to resize the hash table to maintain efficient space usage.

Method 2: Implementing the Hash Function

The hash function converts keys into array indices, distributing the data evenly across the table. An ideal hash function minimizes collisions to optimize performance.

private int GetIndex(TKey key)
{
    int hashCode = key.GetHashCode();
    int index = Math.Abs(hashCode) % table.Length;
    return index;
}

Here, we implement the GetIndex method, which calculates the index in the hash table based on the hash code of the key. The GetHashCode() method provides a unique integer for each key, and we take the absolute value and use modulo % to fit the index within the current table size.

Method 3: Handling Collisions with Chaining

Collisions occur when two keys produce the same hash code and try to occupy the same index in the hash table. We handle collisions by using a chaining approach, where each index in the table contains a linked list of entries with the same hash code.

private void AddOrUpdate(TKey key, TValue value)
{
    int index = GetIndex(key);
    var entry = table[index];

    while (entry != null)
    {
        if (entry.Key.Equals(key))
        {
            entry.Value = value;
            return;
        }
        entry = entry.Next;
    }

    Entry<TKey, TValue> newEntry = new Entry<TKey, TValue>
    {
        Key = key,
        Value = value,
        Next = table[index]
    };

    table[index] = newEntry;
    size++;

    if (size >= table.Length * LoadFactor)
        ResizeTable();
}

In the AddOrUpdate method, we first get the index using the hash function. If the entry is found with the same key, we update its value. If not, we create a new entry and chain it to the existing entry (if any) at that index. We also implement a resizing mechanism to double the size of the table if the number of elements exceeds the load factor, ensuring a proper balance between space and time complexity.

Method 4: Retrieving a Value from the Hash Table

Let's implement a method to retrieve the value associated with a given key from the hash table.

private bool TryGetValue(TKey key, out TValue value)
{
    int index = GetIndex(key);
    var entry = table[index];

    while (entry != null)
    {
        if (entry.Key.Equals(key))
        {
            value = entry.Value;
            return true;
        }
        entry = entry.Next;
    }

    value = default(TValue);
    return false;
}

The TryGetValue method searches for the entry corresponding to the provided key. If found, it returns the associated value; otherwise, it returns false.

Method 5: Removing an Entry from the Hash Table

To complete our hash table implementation, let's add a method to remove an entry based on its key.

private bool Remove(TKey key)
{
    int index = GetIndex(key);
    var entry = table[index];
    Entry<TKey, TValue> prevEntry = null;

    while (entry != null)
    {
        if (entry.Key.Equals(key))
        {
            if (prevEntry != null)
                prevEntry.Next = entry.Next;
            else
                table[index] = entry.Next;

            size--;
            return true;
        }

        prevEntry = entry;
        entry = entry.Next;
    }

    return false;
}

The Remove method finds the entry with the given key and removes it from the hash table. If the entry is found, we adjust the linked list pointers accordingly, and the method returns true. Otherwise, it returns false.

Conclusion:

In this blog, we explored the concept of hash tables and walked through the process of implementing a custom hash table in C#. We covered essential aspects such as creating the hash table, implementing the hash function, handling collisions using chaining, and enabling resizing to maintain efficiency. Hash tables are versatile data structures, widely used in various computer science applications, such as database indexing, caching mechanisms, and compiler symbol tables. Understanding their inner workings allows developers to optimize data storage and retrieval operations in their programs effectively.