Introduction To Hashing and the HashTable Class: Part 3

In previous articles, I gave a partial introduction to Hashing and Hashtables. So, here is the next and final part of the article.

Introduction To Hashing and the HashTable Class: Part 1 

Introduction To Hashing and the HashTable Class: Part 2 

 

The Hashtable Class

 

The Hashtable class is a special type of Dictionary object, storing key/value pairs, where the values are stored based on the hash code derived from the key. You can specify a hash function or use the one built in (we'll explain it later) for the datatype of the key. The Hashtable class is very efficient and should be used instead of custom implementations whenever possible.

 

The strategy that the class uses to avoid collisions is the concept of a bucket. A bucket is a virtual grouping of objects together that have the same hash code, much like we used an ArrayList to handle collisions when we discussed separate chaining. If two keys have the same hash code, they are placed in the same bucket. Otherwise, each key with a unique hash code is placed in its own bucket.

 

The number of buckets used in a Hashtable object is called the load factor. The load factor is the ratio of the elements to the number of buckets. Initially, the factor is set to 1.0. When the actual factor reaches the initial factor, the load factor is increased to the smallest prime number that is twice the current number of buckets. The load factor is important because the smaller the load factor, the better the performance of the Hashtable object.

 

Instantiating and Adding Data to a Hashtable Object 

 

The Hashtable class is part of the System.Collections namespace, so you must import System.Collections at the beginning of your program.

 

A Hashtable object can be instantiated in one of the following three ways (actually there are several more, including various types of copy constructors, but we will remain with the three most common constructors here).

The first line creates a hash table with the default capacity and the default load factor. The second line creates a hash table with a capacity of 50 elements and the default load factor. The third line creates a hash table with an initial capacity of 25 elements and a load factor of 3.0.

 

Key/value pairs are entered into a hash table using the Add method. This method takes two arguments: the key and the value associated with the key. The key is added to the hash table after computing its hash value. Here is some example code.

 
Retrieving the keys and the values separately from the Hash Table

 

The Hashtable class has two very useful methods for retrieving the keys and values separately from a hash table: Keys and Values. These methods create an Enumerator object that allows you to use a For Each loop, or some other technique to examine the keys and the values.

 

The following program shows how these methods work.

using System;
using System.Collections;
class Hashtbl {
static void Main() {
Hashtable symbols = new Hashtable(25);
symbols.Add("salary", 25000);
symbols.Add("name", "Shubham");
symbols.Add("age", 21);
symbols.Add("dept", "Information Technology");
symbols["sex"] = "Male";
Console.WriteLine("The keys are: ");
foreach (Object key in symbols.Keys)
Console.WriteLine(key);
Console.WriteLine();
Console.WriteLine("The values are: ");
foreach (Object value in symbols.Values)
Console.WriteLine(value);
}
}

 Retrieving a Value Based on the Key 

 

Retrieving a value using its associated key can be accomplished using an indexer that works just like an indexer for an array. A key is passed in as

the index value and the value associated with the key is returned, unless the key do not exist, null is returned.

 

The following short code segment shows how this technique works.

Object value = symbols.Item["name"];
Console.WriteLine("The variable name's value is: " +
value.ToString());

 

 

We can use an indexer along with the Keys method to retrieve complete data stored in a hash table.

 

Utility Methods of the Hashtable Class

 

There are several methods in the Hashtable class that helps you to be more productive with Hashtable objects. In this section, we will examine some of them, including methods for determining the number of elements in a hash table, clearing the contents of a hash table, determining if a specified key (and value) is contained in a hash table, removing elements from a hash table and copying the elements of a hash table to an array.

 

The number of elements in a hash table is stored in the Count property that returns an integer:

int numElements;
numElements = symbols.Count;

We can immediately remove all the elements of a hash table using the Clear method:

symbols.Clear();

To remove a single element from a hash table, you can use the Remove method. This method takes a single argument, a key and the method removes both the specified key and its associated value. Here's an example:

symbols.Remove("sex");
foreach(Object key In symbols.Keys)
Console.WriteLine(key.ToString() + ": " +
symbols[key].ToString());

Before you remove an element from a hash table, you may want to check if either the key or the value is in the table. We can determine this information with the ContainsKey method and the ContainsValue method.

string aKey;
Console.Write("Enter a key to remove: ");
aKey = Console.ReadLine();
if (symbols.ContainsKey(aKey))
symbols.Remove(aKey);

Using this method ensures that the key/value pair to remove exists in the hash table. The ContainsValue method works similarly with values instead of keys.

 

Summary

 

A hash table is a very efficient data structure for storing key/value pairs. The implementation of a hash table is quite straightforward, with the tricky part having to do with choosing a strategy for collisions. This article discussed several techniques for handling collisions. For most C# applications, there is no reason to build a custom hash table, when the Hashtable class of the .NET Framework library works quite well. You can specify your own hash function for the class or you can let the class calculate hash values.