Hash Table Implementation in C#

1. Introduction

A Hash Table (also known as a HashMap in some languages) is a data structure that allows for key-value storage and retrieval. It uses a hash function to map keys to indices in an array, facilitating average constant time complexity for most operations. Collision handling can be achieved using various techniques, one of the most common being chaining (using linked lists).

2. Implementation Steps

1. Define the Entry class to represent key-value pairs stored in the hash table.

2. Create a HashTable class to manage the array of entries and handle collisions using chaining.

3. Implement basic operations:

- Put: Add a key-value pair to the table.

- Get: Retrieve the value associated with a given key.

- Remove: Remove a key-value pair from the table.

4. Implement the hash function to determine where to store entries.

5. Test the Hash Table with various operations.

3. Implementation in C#

using System;
using System.Collections.Generic;
public class Entry {
    public string Key { get; set; }
    public string Value { get; set; }
    public Entry(string key, string value) {
        Key = key;
        Value = value;
    }
}
public class HashTable {
    private readonly LinkedList<Entry>[] _items;
    public HashTable(int size) {
        _items = new LinkedList<Entry>[size];
    }
    public void Put(string key, string value) {
        int index = GetHash(key);
        if (_items[index] == null) {
            _items[index] = new LinkedList<Entry>();
        }
        var linkedList = _items[index];
        foreach (var entry in linkedList) {
            if (entry.Key == key) {
                entry.Value = value;  // Update the existing value
                return;
            }
        }
        linkedList.AddLast(new Entry(key, value));
    }
    public string Get(string key) {
        int index = GetHash(key);
        var linkedList = _items[index];
        if (linkedList == null) return null;
        foreach (var entry in linkedList) {
            if (entry.Key == key) {
                return entry.Value;
            }
        }
        return null;
    }
    public void Remove(string key) {
        int index = GetHash(key);
        var linkedList = _items[index];
        if (linkedList == null) return;
        for (var item = linkedList.First; item != null; item = item.Next) {
            if (item.Value.Key == key) {
                linkedList.Remove(item);
                return;
            }
        }
    }
    private int GetHash(string key) {
        return key.Length % _items.Length;
    }
}
public class Program {
    public static void Main() {
        var hashTable = new HashTable(5);
        hashTable.Put("name", "John");
        hashTable.Put("age", "30");
        hashTable.Put("city", "New York");
        Console.WriteLine(hashTable.Get("name"));  // Output: John
        Console.WriteLine(hashTable.Get("age"));   // Output: 30
        Console.WriteLine(hashTable.Get("city"));  // Output: New York
        hashTable.Remove("age");
        Console.WriteLine(hashTable.Get("age"));   // Output: (blank)
    }
}

Output:

John
30
New York

Explanation:

1. The Entry class represents each key-value pair in the hash table.

2. The HashTable class contains an array of linked lists, which handle collisions using the chaining method. Each index of the array corresponds to a hash value.

3. Put method adds (or updates) a key-value pair in the table.

4. Get method retrieves a value based on its key.

5. Remove method deletes an entry based on its key.

6. GetHash is a basic hash function that determines an index in the array for storing/retrieving an entry.

7. The demonstration in the Main function showcases basic operations, such as adding key-value pairs, retrieving values, and removing entries.