| [ Team LiB ] |
|
9.8 DictionariesA dictionary is a collection that associates a key to a value. A language dictionary, such as Webster's, associates a word (the key) with its definition (the value). To see the value of dictionaries, start by imagining that you want to keep a list of the state capitals. One approach might be to put them in an array: string[] stateCapitals = new string[50]; The stateCapitals array will hold 50 state capitals. Each capital is accessed as an offset into the array. For example, to access the capital for Arkansas, you need to know that Arkansas is the fourth state in alphabetical order: string capitalOfArkansas = stateCapitals[3]; It is inconvenient, however, to access state capitals using array notation. After all, if I need the capital for Massachusetts, there is no easy way for me to determine that Massachusetts is the 21st state alphabetically. It would be far more convenient to store the capital with the state name. A dictionary allows you to store a value (in this case, the capital) with a key (in this case, the name of the state). A .NET Framework dictionary can associate any kind of key (string, integer, object, etc.) with any kind of value (string, integer, object, etc.). Typically, of course, the key is fairly short, the value fairly complex. The most important attributes of a good dictionary are that it is easy to add values and it is quick to retrieve values. Some dictionaries are faster at adding new values, and others are optimized for retrieval. One example of a dictionary type is the hashtable. 9.8.1 HashtablesA hashtable is a dictionary optimized for fast retrieval. The principal methods and properties of Hashtable are summarized in Table 9-6.
In a Hashtable, each value is stored in a "bucket." The bucket is numbered, much like an offset into an array. Because the key may not be an integer, it must be possible to translate the key (e.g., "Massachusetts") into a bucket number. Each key must provide a GetHashCode( ) method that will accomplish this magic. Remember that everything in C# derives from object. The object class provides a virtual method GetHashCode( ), which the derived types are free to inherit as is or to override. A trivial implementation of a GetHashCode( ) function for a string might simply add up the Unicode values of each character in the string and then use the modulus operator to return a value between 0 and the number of buckets in the Hashtable. It is not necessary to write such a method for the string type, however, as the CLR provides one for you. When you insert the values (the state capitals) into the Hashtable, the Hashtable calls GetHashCode( ) on each key provided. This method returns an int, which identifies the bucket into which the state capital is placed. It is possible, of course, for more than one key to return the same bucket number. This is called a collision. There are a number of ways to handle a collision. The most common solution, and the one adopted by the CLR, is simply to have each bucket maintain an ordered list of values. When you retrieve a value from the Hashtable, you provide a key. Once again the Hashtable calls GetHashCode( ) on the key and uses the returned int to find the appropriate bucket. If there is only one value, it is returned. If there is more than one value, a binary search of the bucket's contents is performed. Because there are few values, this search is typically very fast.
The key in a Hashtable can be a primitive type, or it can be an instance of a user-defined type (an object). Objects used as keys for a Hashtable must implement GetHashCode( ) as well as Equals. In most cases, you can simply use the inherited implementation from Object. 9.8.2 IDictionaryHash tables are dictionaries because they implement the IDictionary interface. IDictionary provides a public property Item. The Item property retrieves a value with the specified key. In C#, the declaration for the Item property is: object this[object key]
{get; set;}
The Item property is implemented in C# with the index operator ([]). Thus, you access items in any Dictionary object using the offset syntax, as you would with an array. Example 9-17 demonstrates adding items to a Hashtable and then retrieving them with the Item property. Example 9-17. The Item property as offset operatorsnamespace Programming_CSharp
{
using System;
using System.Collections;
public class Tester
{
static void Main( )
{
// Create and initialize a new Hashtable.
Hashtable hashTable = new Hashtable( );
hashTable.Add("000440312", "Jesse Liberty");
hashTable.Add("000123933", "Stacey Liberty");
hashTable.Add("000145938", "John Galt");
hashTable.Add("000773394", "Ayn Rand");
// access a particular item
Console.WriteLine("myHashTable[\"000145938\"]: {0}",
hashTable["000145938"]);
}
}
}
Output:
hashTable["000145938"]: John Galt
Example 9-17 begins by instantiating a new Hashtable. We use the simplest constructor accepting the default initial capacity and load factor (see the sidebar, Load Factor), the default hash code provider, and the default comparer. We then add four key/value pairs. In this example, the social security number is tied to the person's full name. (Note that the social security numbers here are intentionally bogus.) Once the items are added, we access the third item using its key. 9.8.3 The Keys and Values CollectionsDictionary collections provide two additional properties: Keys and Values. Keys retrieves an ICollection object with all the keys in the Hashtable, as Values retrieves an ICollection object with all the values. Example 9-18 illustrates. Example 9-18. Keys and Values collectionsnamespace Programming_CSharp
{
using System;
using System.Collections;
public class Tester
{
static void Main( )
{
// Create and initialize a new Hashtable.
Hashtable hashTable = new Hashtable( );
hashTable.Add("000440312", "George Washington");
hashTable.Add("000123933", "Abraham Lincoln");
hashTable.Add("000145938", "John Galt");
hashTable.Add("000773394", "Ayn Rand");
// get the keys from the hashTable
ICollection keys = hashTable.Keys;
// get the values
ICollection values = hashTable.Values;
// iterate over the keys ICollection
foreach(string key in keys)
{
Console.WriteLine("{0} ", key);
}
// iterate over the values collection
foreach (string val in values)
{
Console.WriteLine("{0} ", val);
}
}
}
}
Output:
000440312
000123933
000773394
000145938
George Washington
Abraham Lincoln
Ayn Rand
John Galt
Although the order of the Keys collection is not guaranteed, it is guaranteed to be the same order as returned in the Values collection. 9.8.4 IDictionaryEnumerator InterfaceIDictionary objects also support the foreach construct by implementing the GetEnumerator method, which returns an IDictionaryEnumerator. The IDictionaryEnumerator is used to enumerate through any IDictionary object. It provides properties to access both the key and value for each item in the dictionary. Example 9-19 illustrates. Example 9-19. Using the IDictionaryEnumerator interfacenamespace Programming_CSharp
{
using System;
using System.Collections;
public class Tester
{
static void Main( )
{
// Create and initialize a new Hashtable.
Hashtable hashTable = new Hashtable( );
hashTable.Add("000440312", "George Washington");
hashTable.Add("000123933", "Abraham Lincoln");
hashTable.Add("000145938", "John Galt");
hashTable.Add("000773394", "Ayn Rand");
// Display the properties and values of the Hashtable.
Console.WriteLine( "hashTable" );
Console.WriteLine( " Count: {0}", hashTable.Count );
Console.WriteLine( " Keys and Values:" );
PrintKeysAndValues( hashTable );
}
public static void PrintKeysAndValues( Hashtable table )
{
IDictionaryEnumerator enumerator = table.GetEnumerator( );
while ( enumerator.MoveNext( ) )
Console.WriteLine( "\t{0}:\t{1}",
enumerator.Key, enumerator.Value );
Console.WriteLine( );
}
}
}
Output:
hashTable
Count: 4
Keys and Values:
000440312: George Washington
000123933: Abraham Lincoln
000773394: Ayn Rand
000145938: John Galt
 |
| [ Team LiB ] |
|