4.8 Using Hashtables

4.8 Using Hashtable s

You want to use a data structure that allows you to associate a key object with a value object.

Technique

Create a HashTable object, which is a class in the System.Collections namespace. Each value added to the collection needs to be associated with a key object, which you do by calling the Add method, passing the key and value objects. To remove a item, call the Remove method, passing the key object as the parameter. To remove all the items within the entire hash table, you can use the Clear method:

 using System; using System.Collections; namespace _7_HashTable {     class Class1     {         [STAThread]         static void Main(string[] args)         {             Hashtable dir = new Hashtable();             dir.Add( 'N', "You travel north." );             dir.Add( 'S', "You are now travelling south." );             dir.Add( 'W', "You are facing west." );             dir.Add( 'E', "You run towards the east." );             dir.Add( 'Q', "Goodbye" );             char input;             do             {                 Console.Write("Enter a direction (N,S,E,W) or Q to quit: ");                 input = Char.ToUpper(Console.ReadLine()[0]);                 Console.WriteLine( dir[Char.ToUpper(input)]);             } while( input != 'Q' );             PrintHashtable( dir );             dir.Remove( 'Q' );             dir.Clear();         }     } } 

To enumerate a hash table, declare a IDictionaryEnumerator object and assign it the result of calling the GetEnumerator method on an instance of a hash table. Next, create a loop that breaks when the MoveNext method of the IDictionaryEnumerator returns false . If successful, the Key property and the Value property of the IDictionaryEnumerator object contain a key and value from the associated hash table respectively:

 static void PrintHashtable( Hashtable ht ) {     IDictionaryEnumerator htEnum = ht.GetEnumerator();     Console.WriteLine( "\nHashtable Contents\n------------------" );     while( htEnum.MoveNext() )     {         Console.WriteLine( "Key: {0}\tValue: {1}",             htEnum.Key, htEnum.Value );     } } 

Comments

Up to this point, all of the collections have been linear in nature, meaning the elements are arranged in a list. Hash tables, on the other hand, use a dictionary arrangement, which means each value added to the collection is placed based on an associated key. One of the methods in System.Object is GetHashCode . This method, which all classes within the .NET Framework contain, generates a unique integer based on information about the key object. For example, a String object can use an algorithm that uses information about each individual character to produce the hash code. Although you are not guaranteed to receive a different hash code for every differing object, the algorithms within the .NET Framework are robust enough to minimize hash-table collisions. By using a hash code for each key object, the hash table can find the corresponding area of memory that the hash code belongs to. You might also hear the term "buckets" when referring to this method. Using a hash code and finding its corresponding bucket, the hash table can retrieve or place an object at that location. Furthermore, if it uses a good hash function, meaning a hash function that minimizes the number of collisions, the performance of a hash table rivals that of using an index lookup on a single-dimension array. A hash table is capable of performing a lookup in constant, O(1), time. Once you throw collisions into the equation, however, you start to see performance drop to linear, O( n ), time, which is equivalent to searching for a value in a single-dimension array by starting at the beginning and enumerating through the array until the value is found.

There are a couple of ways to retrieve values from a hash table. The most common way is to use the Hashtable indexer. The value used for the indexer is the key object used to find the corresponding value. You can also retrieve all the values at one time and manipulate them using a different collection class by accessing the Values property of the Hashtable class. This step returns an ICollection interface, which you can use in the constructor when you create an instance of any collection class. Furthermore, if you change a value in this collection, you are changing the value in the hash table because you are working with the actual values in the original hash table. In fact, you can also perform the same type of manipulations to the Keys collection in the hash table. Changing the value of a key also means you change the value of a key within the hash table.