Hash Tables in C#

Hash tables are an important data structure used to organize data in a way that can be quickly accessed and stored. They are used in many applications including databases, caches, and memory allocation. In this tutorial, we will explore the basics of hash tables in C#. We will discuss how to implement hash tables using arrays, different hash functions, collision handling, and some applications of hash tables. 

Overview of Hash Tables

A hash table is a data structure used to store key-value pairs. In a hash table, the keys are stored in an array, and the values are stored in another array. The key is used to find the value associated with it, which is done by using a hashing function. The hashing function is used to calculate an index for the key, and the value is stored at the index. This allows for fast retrieval of the value associated with a given key, since the index of the value is already known.

Implementing Hash Tables Using Arrays

When implementing a hash table, we first need to create an array to store the keys and values. The array will have a certain size, which will determine the amount of elements that can be stored in the hash table. The size of the array should be large enough to store the data that will be stored in the hash table, but small enough to not waste memory. 

Once the array has been created, we need to implement a hashing function. The hashing function is used to calculate an index for a given key. The index is used to store the value associated with the key in the array. The hashing function should be chosen carefully, as it can have a large impact on the performance of the hash table. 

The following is a simple example of a hashing function written in C#. This function takes in an integer key and returns an index for the key.

int HashFunction(int key) 
{ 
    return key % 10; 
} 

This function will return the remainder of the key divided by 10. This means that any key that ends in the same number will map to the same index in the array. For example, if the key is 23, the index will be 3. If the key is 33, the index will also be 3. This is known as a collision. 

Hash Functions

A hash function is used to calculate an index for a given key. The hash function should be chosen carefully, as it can have a large impact on the performance of the hash table. The hash function should be deterministic, meaning that it should always return the same index for the same key. It should also be fast, since it is used to find the index of the value associated with a given key.

The following is an example of a more sophisticated hash function written in C#. This function takes in a string key and returns an index for the key.

int HashFunction(string key) 
{ 
    int hash = 0; 
    for (int i = 0; i < key.Length; i++) 
    { 
        hash += key[i]; 
    } 
    return hash % 10; 
} 

This function loops through each character in the key and adds its ASCII value to the hash. The hash is then modulo divided by 10 to get the index for the key. This function will return the same index for the same key, but it will also spread out the keys more evenly than the first example.

Collision Handling

When implementing a hash table, collisions can occur when two keys map to the same index in the array. This means that the value associated with one of the keys will not be stored in the array, which is not ideal. To avoid this, we must implement a collision handling algorithm.

The simplest collision handling algorithm is chaining. In this algorithm, a linked list is used to store the values associated with the keys that map to the same index. The linked list is stored at the index, and the values are added to the list. This allows for multiple values to be stored at the same index.

The following is an example of a linked list node written in C#. This node will be used to store the values associated with the keys.

class Node 
{ 
    public int Value; 
    public Node Next; 
  
    public Node(int value) 
    { 
        this.Value = value; 
        this.Next = null; 
    } 
} 

This node will store an integer value and a reference to the next node in the list. This node can then be used to store the values associated with the keys that map to the same index.

Applications of Hash Tables

Hash tables are used in many different applications. They are used in databases to store data in a way that can be quickly accessed. They are also used in caches to store frequently used data so that it can be quickly retrieved. Hash tables are also used in memory allocation to quickly map memory addresses to blocks of memory.

Conclusion

In this tutorial, we have discussed the basics of hash tables in C#. We have explored how to implement hash tables using arrays, different hash functions, collision handling, and some applications of hash tables. Hash tables are a powerful data structure that can be used to quickly store and access data.

Exercises

// Hash table of size 10
int[] keys = new int[10]; 
int[] values = new int[10]; 
  
// Hash function 
int HashFunction(int key) 
{ 
    return key % 10; 
} 
  
// Insert key-value pair into hash table 
void Insert(int key, int value) 
{ 
    // Calculate index 
    int index = HashFunction(key); 
  
    // Insert key and value 
    keys[index] = key; 
    values[index] = value; 
} 
  
// Search for a value associated with a given key 
int Search(int key) 
{ 
    // Calculate index 
    int index = HashFunction(key); 
  
    // Return value at index 
    return values[index]; 
} 

int HashFunction(string key) 
{ 
    int hash = 0; 
    for (int i = 0; i < key.Length; i++) 
    { 
        hash += key[i]; 
    } 
    return hash % 10; 
} 

// Linked list node class 
class Node 
{ 
    public int Value; 
    public Node Next; 
  
    public Node(int value) 
    { 
        this.Value = value; 
        this.Next = null; 
    } 
} 
  
// Handle collisions using linked list 
void HandleCollision(int key, int value, Node[] list) 
{ 
    // Calculate index 
    int index = HashFunction(key); 
  
    // Check if list at index is empty 
    if (list[index] == null) 
    { 
        // Create new node 
        Node node = new Node(value); 
  
        // Set list at index to node 
        list[index] = node; 
    } 
    else 
    { 
        // Create new node 
        Node node = new Node(value); 
  
        // Set new node's Next to current head 
        node.Next = list[index]; 
  
        // Set list at index to new node 
        list[index] = node; 
    } 
} 

// Delete key-value pair from hash table 
void Delete(int key, int[] keys, int[] values) 
{ 
    // Calculate index 
    int index = HashFunction(key); 
  
    // Set key and value at index to 0 
    keys[index] = 0; 
    values[index] = 0; 
} 

// Search for a value in a hash table using a linked list 
int Search(int key, Node[] list) 
{ 
    // Calculate index 
    int index = HashFunction(key); 
  
    // Get head of list 
    Node head = list[index]; 
  
    // Loop through list 
    while (head != null) 
    { 
        // Check if value is found 
        if (head.Value == key) 
        { 
            // Return value 
            return head.Value; 
        } 
  
        // Move to next node 
        head = head.Next; 
    } 
  
    // Value not found 
    return -1; 
}