A 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, others are optimized for retrieval. One example of a dictionary type is the hashtable.
A
hashtable
is a dictionaryoptimized for fast retrieval.
The principal methods and properties of Hashtable
are summarized in Table 9-6.
Table 9-6. Hashtable methods and properties
Method or Property |
Purpose |
---|---|
Synchronized( ) |
Public
static method that returns a |
Count |
Public
property that gets the number of elements in the
|
IsReadOnly |
Public property that gets a value indicating if the
|
IsSynchronized |
Public property that gets a value indicating if the
|
Item( ) |
The indexer for the |
Keys |
Public property that gets an |
SyncRoot |
Public property that returns an object that can be used to
synchronize access to the |
Values |
Public property that gets an |
Add( ) |
Adds an entry with a specified |
Clear( ) |
Removes all objects from the |
Clone( ) |
Creates a shallow copy. |
Contains( ) |
Determines if an element is in the |
ContainsKey( ) |
Determines whether the |
CopyTo( ) |
Copies the |
GetEnumerator( ) |
Returns an enumerator for the |
GetObjectData( ) |
Implements |
OnDeserialization( ) |
Implements |
Remove( ) |
Removes the entry with the specified |
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.
You will 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 we provide. 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
.
Hash 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 operators
namespace Programming_CSharp
{
using System;
using System.Collections;
// a simple class to store in the array
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("myHastTable["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.
Dictionary
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 collections
namespace Programming_CSharp
{
using System;
using System.Collections;
// a simple class to store in the array
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.
IDictionary
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 interface
namespace Programming_CSharp
{
using System;
using System.Collections;
// a simple class to store in the array
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( " {0}: {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
18.119.138.202