C# Hash Table with Examples
Hashtable is a collection class that provides a mapping between keys and values. It is built on a hashing method that associates keys with certain locations within an internal data structure known as a bucket. There may be one or more key-value pairs in each bucket.
Key Characteristics of Hash Table
Unique keys: Hashtable enforces key uniqueness, meaning each key can only exist once within the collection.
Effective lookup: The hashing algorithm is used to quickly access the corresponding bucket when retrieving a value from the Hashtable based on a key.
Automatic resizing: As components are added or removed, the internal structure of the Hashtable dynamically adjusts to maintain optimal speed and memory usage.
Enumeration: Hashtable offers attributes and methods for enumerating through its components, enabling easy iteration and processing.
Creating and Initializing a HashTable
Syntax for creating a new Hashtable object:
Hashtable hashtable = new Hashtable();
Examples of different ways to initialize a Hashtable with key-value pairs:
1. Initializing with individual Add() method calls:
Hashtable hashtable = new Hashtable(); hashtable.Add("Key1", "Value1"); hashtable.Add("Key2", "Value2"); hashtable.Add("Key3", "Value3");
2. Initializing with object initializer syntax:
Hashtable hashtable = new Hashtable() { { "Key1", "Value1" }, { "Key2", "Value2" }, { "Key3", "Value3" } };
3. Initializing with a collection of key-value pairs:
var keyValuePairs = new Dictionary<string, string> { { "Key1", "Value1" }, { "Key2", "Value2" }, { "Key3", "Value3" } }; Hashtable hashtable = new Hashtable(keyValuePairs);
Fixing duplicate values and keys:
- Duplicate keys are not permitted in hashtables. It will throw an exception if you attempt to add an already present key.
- A hashtable allows for the duplication of values. Multiple entries with the same value linked to various keys are possible.
Example of managing duplicate keys:
using System; using System.Collections; class Program { static void Main() { Hashtable hashtable = new Hashtable(); hashtable.Add("Name", "Vardhan"); hashtable.Add("Number", "41"); hashtable.Add("Key", "Vardhan"); // Duplicate value // Retrieving all keys associated with the duplicate value var keysWithDuplicateValue = new ArrayList(); foreach (DictionaryEntry entry in Hashtable) { if (entry.Value.Equals("Vardhan")) { keysWithDuplicateValue.Add(entry.Key); } } Console.WriteLine("Keys with duplicate value 'Vardhan':"); foreach (var key in keysWithDuplicateValue) { Console.WriteLine(key); } } }
Output:
Adding and Removing Elements
Add() method can be used to add elements to the Hashtable.
using System; using System.Collections; class Program { static void Main() { Hashtable hashtable = new Hashtable(); // Adding elements using the Add() method hashtable.Add("Hobby", "Television"); hashtable.Add("Name", "Johnson"); hashtable.Add("Age", "40"); // Displaying the elements in the Hashtable foreach (DictionaryEntry entry in Hashtable) { Console.WriteLine(entry.Key + ": " + entry.Value); } } }
Output:
Note: The Add() method throws an exception if you try to add an element with a duplicate key. To handle this, you can use the indexer to update the value for an existing key or the ContainsKey() method to check if the key already exists before adding a new element.
The following is an example demonstrating the use of the ContainsKey() method
using System; using System.Collections; class Program { static void Main() { Hashtable hashtable = new Hashtable(); // Adding elements using the indexer to update existing keys hashtable["Name1"] = "Sai"; hashtable["Name2"] = "Vardhan"; hashtable["Name3"] = "Rathnam"; // Updating the value for an existing key hashtable["Name2"] = "Venkat"; // Checking if the key exists before adding a new element if (!hashtable.ContainsKey("Name3")) { hashtable.Add("Name3", "Lasya"); } // Displaying the elements in the Hashtable foreach (DictionaryEntry entry in Hashtable) { Console.WriteLine(entry.Key + ": " + entry.Value); } } }
Output:
Removing elements using the Remove() method:
using System;
using System.Collections; class Program { static void Main() { Hashtable hashtable = new Hashtable(); hashtable["Name1"] = "Sai"; hashtable["Name2"] = "Vardhan"; hashtable["Name3"] = "Rathnam"; // Removing an element by key hashtable.Remove("Name1"); hashtable.Remove("Name2"); // Displaying the elements in the Hashtable foreach (DictionaryEntry entry in Hashtable) { Console.WriteLine(entry.Key + ": " + entry.Value); } } }
Output:
Name3: Rathnam
Clearing all elements from the Hashtable:
The clear() method is used to clear all the elements from the Hashtable.
using System; using System.Collections; class Program { static void Main() { Hashtable hashtable = new Hashtable(); hashtable["Name1"] = "Sai"; hashtable["Name2"] = "Vardhan"; hashtable["Name3"] = "Rathnam"; // Clearing all elements hashtable.Clear(); // After clearing, the Hashtable will be empty Console.WriteLine("Count: " + hashtable.Count); } }
Output:
Retrieving values based on keys
The Hashtable's values can be accessed via their respective keys because of the indexer. The value linked to the supplied key is retrieved using the syntax hashtable["Key"]. It would be best to cast the received value to the correct type because Hashtable holds objects.
using System; using System.Collections; class Program { static void Main() { Hashtable hashtable = new Hashtable(); hashtable["Name1"] = "Raja"; hashtable["Name2"] = "Vardhan"; hashtable["Name3"] = "Rathnam"; string value1 = (string)hashtable["Name1"]; string value2 = (string)hashtable["Name2"]; Console.WriteLine(value1); Console.WriteLine(value2); } }
Output:
Checking if a key exists in the Hashtable
The Hashtable class contains the methods ContainsKey(key) and ContainsValue(value) to check for the existence of a key. If the Hashtable contains the supplied key or value, the functions ContainsKey(key) and ContainsValue(value) return true.
using System; using System.Collections; class Program { static void Main() { Hashtable hashtable = new Hashtable(); hashtable["Name1"] = "Raja"; hashtable["Name2"] = "Vardhan"; hashtable["Name3"] = "Rathnam"; bool containsKey = hashtable.ContainsKey("Name1"); bool containsValue = hashtable.ContainsValue("Vardhan"); Console.WriteLine(containsKey); Console.WriteLine(containsValue); } }
Output:
Modifying the values for existing keys
To update the value for an existing key in the Hashtable, assign the new value to the corresponding key using the indexer. The line hashtable["Name1"] = "Vardhan" updates the value associated with the key "Name1" to "Vardhan". This operation replaces the existing value with the new one.
using System; using System.Collections; class Program { static void Main() { Hashtable hashtable = new Hashtable(); hashtable["Name1"] = "Raja"; hashtable["Name3"] = "Rathnam"; // Update the value for an existing key hashtable["Name1"] = "Vardhan"; string updatedValue = (string)hashtable["Name1"]; Console.WriteLine(updatedValue); } }
Output:
It's possible to run into exceptions when accessing elements in a hashtable. A KeyNotFoundException will be raised if you use the indexer to try to access a key that doesn't exist. Use a try-catch block to capture the exception and treat the problem properly to handle this.
using System; using System.Collections; using System.Collections.Generic; class Program { static void Main() { Hashtable hashtable = new Hashtable(); hashtable.Add("Fruit", "Mango"); try { if (hashtable.ContainsKey("Fruit")) { hashtable["Fruit"] = "Orange"; Console.WriteLine(hashtable["Fruit"]); Console.WriteLine("Value updated successfully."); } else { Console.WriteLine("Key not found."); } } catch (KeyNotFoundException) { Console.WriteLine("Key not found."); } } }
Output:
A try-catch block is used in the provided code to catch the KeyNotFoundException and show a customised message informing the user that it could not be located. Additionally, by first determining whether the key exists using the ContainsKey(key) method, it illustrates a secure approach to alter the value of an existing key.
Time Complexity:
Addition (Add): Adding an element to a hashtable is typically thought to have an O(1) time complexity. The temporal complexity can, however, decrease to O(n) in the worst-case situation where there are several hash collisions, where n is the total number of elements in the Hashtable.
Removal (Remove): It is generally accepted that the temporal complexity of deleting an element from a hashtable is O(1). Similar to addition, the time complexity can be O(n) in the worst-case situation with several hash collisions.
Retrieval (Access): On average, it takes O(1) of time to access an entry in a hashtable using its key. Again, hash collisions might make it O(n) in the worst-case scenario.
Memory Usage:
The hashtable stores key-value pairs in memory. The amount of memory used is inversely correlated with the number of elements kept in the Hashtable. Each key-value pair uses RAM for the internal data structures utilised by the Hashtable and additional RAM for storing the key and value objects.
Applications of HashTable
1. Counting Word Frequencies
In this example, a Hashtable is used to count the frequencies of words in an array. The keys of the Hashtable represent the words, and the values represent their frequencies.
using System; using System.Collections; class Program { static void Main(string[] args) { Hashtable wordFrequencies = new Hashtable(); string[] words = { "apple", "banana", "apple", "cherry", "banana", "apple" }; foreach (string word in words) { if (wordFrequencies.ContainsKey(word)) { wordFrequencies[word] = (int)wordFrequencies[word] + 1; } else { wordFrequencies[word] = 1; } } foreach (DictionaryEntry entry in wordFrequencies) { Console.WriteLine($"{entry.Key}: {entry.Value}"); } } }
Output:
2. Caching Results
In this example, previously calculated Fibonacci numbers are stored in a Hashtable cache. The function determines whether a Fibonacci number exists in the cache before computing it. If yes, it avoids unnecessary calculations by retrieving the value from the cache.
using System; using System.Collections; class Program { static Hashtable cache = new Hashtable(); static int CalculateFibonacci(int n) { if (cache.ContainsKey(n)) { return (int)cache[n]; } int result; if (n <= 1) { result = n; } else { result = CalculateFibonacci(n - 1) + CalculateFibonacci(n - 2); } cache[n] = result; return result; } static void Main(string[] args) { int n = 10; int fibonacciNumber = CalculateFibonacci(n); Console.WriteLine($"The Fibonacci number at index {n} is {fibonacciNumber}"); } }
Output: