Non-Generic Collections

The System.Collections namespace in the .NET Framework Class Library is the primary source for non-generic collections. These classes provide standard implementations of many of the data structures discussed in Chapter 25 with collections that store references of type object. In this section, we demonstrate classes ArrayList, Stack and Hashtable.

27.4.1. Class ArrayList

In most programming languages, conventional arrays have a fixed sizethey cannot be changed dynamically to conform to an application's execution-time memory requirements. In some applications, this fixed-size limitation presents a problem for programmers. They must choose between using fixed-size arrays that are large enough to store the maximum number of elements the application may require and using dynamic data structures that can grow and shrink the amount of memory required to store data in response to the changing requirements of an application at execution time.

The .NET Framework's ArrayList collection class mimics the functionality of conventional arrays and provides dynamic resizing of the collection through the class's methods. At any time, an ArrayList contains a certain number of elements less than or equal to its capacitythe number of elements currently reserved for the ArrayList. An application can manipulate the capacity with ArrayList property Capacity. If an ArrayList needs to grow, it by default doubles its Capacity.

ArrayLists store references to objects. All classes derive from class object, so an ArrayList can contain objects of any type. Figure 27.4 lists some useful methods and properties of class ArrayList.

Figure 27.5 demonstrates class ArrayList and several of its methods. Class ArrayList belongs to the System.Collections namespace (line 4). Lines 811 declare two arrays of strings (colors and removeColors) that we will use to fill two ArrayList objects. Recall from Section 9.11 that constants must be initialized at compile-time, but readonly variables can be initialized at execution time. Arrays are objects created at execution time, so we declare colors and removeColors with readonlynot constto make them unmodifiable. When the application begins execution, we create an ArrayList with an initial capacity of one element and store it in variable list (line 16). The foreach statement in lines 2021 adds the five elements of array colors to list via ArrayList's Add method, so list grows to accommodate these new elements. Line 25 uses ArrayList's overloaded constructor to create a new ArrayList initialized with the contents of array removeColors, then assigns it to variable removeList. This constructor can initialize the contents of an ArrayList with the elements of any ICollection passed to it. Many of the collection classes have such a constructor. Notice that the constructor call in line 25 performs the task of lines 2021.

Figure 27.5. Using class ArrayList.

(This item is displayed on pages 1402 - 1403 in the print version)

Line 28 calls method DisplayInformation (lines 3855) to output the contents of the list. This method uses a foreach statement to traverse the elements of an ArrayList. As we discussed in Section 27.3, the foreach statement is a convenient shorthand for calling ArrayList's GetEnumerator method and using an enumerator to traverse the elements of the collection. Also, we must use an iteration variable of type object because class ArrayList is non-generic and stores references to objects.

We use the Count and Capacity properties in line 46 to display the current number of elements and the maximum number of elements that can be stored without allocating more memory to the ArrayList. The output of Fig. 27.5 indicates that the ArrayList has capacity 8recall that an ArrayList doubles its capacity whenever it needs more space.

In line 48, we invoke method IndexOf to determine the position of the string "BLUE" in arrayList and store the result in local variable index. IndexOf returns -1 if the element is not found. The if statement in lines 5054 checks if index is -1 to determine whether arrayList contains "BLUE". If it does, we output its index. ArrayList also provides method Contains, which simply returns true if an object is in the ArrayList, and false otherwise. Method Contains is preferred if we do not need the index of the element.

After method DisplayInformation returns, we call method RemoveColors (lines 5864) with the two ArrayLists. The for statement in lines 6263 iterates over ArrayList secondList. Line 63 uses an indexer to access an ArrayList elementby following the ArrayList reference name with square brackets ([]) containing the desired index of the element. An ArgumentOutOfRangeException occurs if the specified index is not both greater than 0 and less than the number of elements currently stored in the ArrayList (specified by the ArrayList's Count property).

We use the indexer to obtain each of secondList's elements, then remove each one from firstList with the Remove method. This method deletes a specified item from an ArrayList by performing a linear search and removing (only) the first occurrence of the specified object. All subsequent elements shift toward the beginning of the ArrayList to fill the emptied position.

After the call to RemoveColors, line 34 again outputs the contents of list, confirming that the elements of removeList were, indeed, removed.

27.4.2. Class Stack

The Stack class implements a stack data structure and provides much of the functionality that we defined in our own implementation in Section 25.3. Refer to that section for a discussion of stack data structure concepts. We created a test application in Fig. 25.11 to demonstrate the StackInheritance data structure that we developed. We adapt Fig. 25.14 in Fig. 27.6 to demonstrate the .NET Framework collection class Stack.

Figure 27.6. Demonstrating class Stack.

(This item is displayed on pages 1405 - 1406 in the print version)

The using directive in line 4 allows us to use the Stack class with its unqualified name from the System.Collections namespace. Line 10 creates a Stack with the default initial capacity (10 elements). As one might expect, class Stack has methods Push and Pop to perform the basic stack operations.

Method Push takes an object as an argument and inserts it at the top of the Stack. If the number of items on the Stack (the Count property) is equal to the capacity at the time of the Push operation, the Stack grows to accommodate more objects. Lines 1926 use method Push to add four elements (a bool, a char, an int and a string) to the stack and invoke method PrintStack (lines 5064) after each Push to output the contents of the stack. Notice that this non-generic Stack class can store only references to objects, so each of the value-type itemsthe bool, the char and the intare implicitly boxed before they are added to the Stack. (Namespace System.Collections.Generic provides a generic Stack class that has many of the same methods and properties used in Fig. 27.6.)

Method PrintStack (lines 5064) uses Stack property Count (implemented to fulfill the contract of interface ICollection) to obtain the number of elements in stack. If the stack is not empty (i.e., Count is not equal to 0), we use a foreach statement to iterate over the stack and output its contents by implicitly invoking the ToString method of each element. The foreach statement implicitly invokes Stack's GetEnumerator method, which we could have called explicitly to traverse the stack via an enumerator.

Method Peek returns the value of the top stack element, but does not remove the element from the Stack. We use Peek at line 30 to obtain the top object of the Stack, then output that object, implicitly invoking the object's ToString method. An InvalidOperationException occurs if the Stack is empty when the application calls Peek. (We do not need an exception handling block because we know the stack is not empty here.)

Method Pop takes no argumentsit removes and returns the object currently on top of the Stack. An infinite loop (lines 3540) pops objects off the stack and outputs them until the stack is empty. When the application calls Pop on the empty stack, an InvalidOperationException is thrown. The catch block (lines 4246) outputs the exception, implicitly invoking the InvalidOperationException's ToString method to obtain its error message and stack trace.

Although Fig. 27.6 does not demonstrate it, class Stack also has method Contains, which returns true if the Stack contains the specified object, and returns false otherwise.

27.4.3. Class Hashtable

When an application creates objects of new or existing types, it needs to manage those objects efficiently. This includes sorting and retrieving objects. Sorting and retrieving information with arrays is efficient if some aspect of your data directly matches the key value and if those keys are unique and tightly packed. If you have 100 employees with nine-digit Social Security numbers and you want to store and retrieve employee data by using the Social Security number as a key, it would nominally require an array with 999,999,999 elements, because there are 999,999,999 unique nine-digit numbers. If you have an array that large, you could get very high performance storing and retrieving employee records by simply using the Social Security number as the array index, but it would be a large waste of memory.

Many applications have this problemeither the keys are of the wrong type (i.e., not non-negative integers), or they are of the right type, but they are sparsely spread over a large range.

What is needed is a high-speed scheme for converting keys such as Social Security numbers and inventory part numbers to unique array indices. Then, when an application needs to store something, the scheme could convert the application key rapidly to an index and the record of information could be stored at that location in the array. Retrieval occurs the same wayonce the application has a key for which it wants to retrieve the data record, the application simply applies the conversion to the key, which produces the array subscript where the data resides in the array and retrieves the data.

The scheme we describe here is the basis of a technique called hashing, in which we store data in a data structure called a hash table. Why the name? Because, when we convert a key into an array subscript, we literally scramble the bits, making a "hash" of the number. The number actually has no real significance beyond its usefulness in storing and retrieving this particular data record.

A glitch in the scheme occurs when collisions occur (i.e., two different keys "hash into" the same cell, or element, in the array). Since we cannot sort two different data records to the same space, we need to find an alternative home for all records beyond the first that hash to a particular array subscript. One scheme for doing this is to "hash again" (i.e., to reapply the hashing transformation to the key to provide a next candidate cell in the array). The hashing process is designed to be quite random, so the assumption is that with just a few hashes, an available cell will be found.

Another scheme uses one hash to locate the first candidate cell. If the cell is occupied, successive cells are searched linearly until an available cell is found. Retrieval works the same waythe key is hashed once, the resulting cell is checked to determine whether it contains the desired data. If it does, the search is complete. If it does not, successive cells are searched linearly until the desired data is found.

The most popular solution to hash-table collisions is to have each cell of the table be a hash "bucket"typically, a linked list of all the keyvalue pairs that hash to that cell. This is the solution that the .NET Framework's Hashtable class implements.

The load factor affects the performance of hashing schemes. The load factor is the ratio of the number of objects stored in the hash table to the total number of cells of the hash table. As this ratio gets higher, the chance of collisions tends to increase.

Computer science students study hashing schemes in courses called "Data Structures" and "Algorithms." Recognizing the value of hashing, the .NET Framework provides class Hashtable to enable programmers to easily employ hashing in applications.

This concept is profoundly important in our study of object-oriented programming. Classes encapsulate and hide complexity (i.e., implementation details) and offer userfriendly interfaces. Crafting classes to do this properly is one of the most valued skills in the field of object-oriented programming.

A hash function performs a calculation that determines where to place data in the hash table. The hash function is applied to the key in a keyvalue pair of objects. Class Hashtable can accept any object as a key. For this reason, class object defines method GetHashCode, which all objects inherit. Most classes that are candidates to be used as keys in a hash table override this method to provide one that performs efficient hash code calculations for a specific type. For example, a string has a hash code calculation that is based on the contents of the string. Figure 27.7 uses a Hashtable to count the number of occurrences of each word in a string.

Figure 27.7. Application counts the number of occurrences of each word in a string and stores them in a hash table.

Lines 46 contain using directives for namespaces System (for class Console), System.Text.RegularExpressions (for class Regex, discussed in Chapter 16, Strings, Characters and Regular Expressions) and System.Collections (for class Hashtable). Class HashtableTest declares three static methods. Method CollectWords (lines 2046) inputs a string and returns a Hashtable in which each value stores the number of times that word appears in the string and the word is used for the key. Method DisplayHashtable (lines 4960) displays the Hashtable passed to it in column format. The Main method (lines 1017) simply invokes CollectWords (line 13), then passes the Hashtable returned by CollectWords to DisplayHashtable in line 16.

Method CollectWords (lines 2046) begins by initializing local variable table with a new Hashtable (line 22) that has a default initial capacity of 0 elements and a default maximum load factor of 1.0. When the number of items in the Hashtable becomes greater than the number of cells times the load factor, the capacity is increased automatically. (This implementation detail is invisible to clients of the class.) Lines 2425 prompt the user and input a string. We use static method Split of class Regex in line 28 to divide the string by its whitespace characters. This creates an array of "words," which we then store in local variable words.

The foreach statement in lines 3143 loops over every element of array words. Each word is converted to lowercase with string method ToLower, then stored in variable wordKey (line 33). Then line 36 calls Hashtable method ContainsKey to determine whether the word is in the hash table (and thus has occurred previously in the string). If the Hashtable does not contain an entry for the word, line 42 uses Hashtable method Add to create a new entry in the hash table, with the lowercase word as the key and an object containing 1 as the value. Note that autoboxing occurs when the application passes integer 1 to method Add, because the hash table stores both the key and value in references to type object.

If the word is already a key in the hash table, line 38 uses the Hashtable's indexer to obtain and set the key's associated value (the word count) in the hash table. We first downcast the value obtained by the get accessor from an object to an int. This unboxes the value so that we can increment it by 1. Then, when we use the indexer's set accessor to assign the key's associated value, the incremented value is implicitly reboxed so that it can be stored in the hash table.

Notice that invoking the get accessor of a Hashtable indexer with a key that does not exist in the hash table obtains a null reference. Using the set accessor with a key that does not exist in the hash table creates a new entry, as if you had used the Add method.

Line 45 returns the hash table to the Main method, which then passes it to method DisplayHashtable (lines 4960), which displays all the entries. This method uses readonly property Keys (line 56) to get an ICollection that contains all the keys. Because ICollection extends IEnumerable, we can use this collection in the foreach statement in lines 5657 to iterate over the keys of the hash table. This loop accesses and outputs each key and its value in the hash table using the iteration variable and table's get accessor. Each key and its value is displayed in a field width of -12. The negative field width indicates that the output is left justified. Note that a hash table is not sorted, so the keyvalue pairs are not displayed in any particular order. Line 59 uses Hashtable property Count to get the number of keyvalue pairs in the Hashtable.

Lines 5657 could have also used the foreach statement with the Hashtable object itself, instead of using the Keys property. If you use a foreach statement with a Hashtable object, the iteration variable will be of type DictionaryEntry. The enumerator of a Hashtable (or any other class that implements IDictionary) uses the DictionaryEntry structure to store keyvalue pairs. This structure provides properties Key and Value for retrieving the key and value of the current element. If you do not need the key, class Hashtable also provides a read-only Values property that gets an ICollection of all the values stored in the Hashtable. We can use this property to iterate through the values stored in the Hashtable without regard for where they are stored.

Problems with Non-Generic Collections

In the word-counting application of Fig. 27.7, our Hashtable stores its keys and data as object references, even though we store only string keys and int values by convention. This results in some awkward code. For example, line 38 was forced to unbox and box the int data stored in the Hashtable every time it incremented the count for a particular key. This is inefficient. A similar problem occurs in line 56the iteration variable of the foreach statement is an object reference. If we need to use any of its string-specific methods, we need an explicit downcast.

This can cause subtle bugs. Suppose we decide to improve the readability of Fig. 27.7 by using the indexer's set accessor instead of the Add method to add a key/value pair in line 42, but accidentally type:

table[ wordKey ] = wordKey; // initialize to 1

This statement will create a new entry with a string key and string value instead of an int value of 1. Although the application will compile correctly, this is clearly incorrect. If a word appears twice, line 38 will try to downcast this string to an int, causing an InvalidCastException at execution time. The error that appears at execution time will indicate that the problem is at line 38, where the exception occurred, not at line 42. This makes the error more difficult to find and debug, especially in large software applications where the exception may occur in a different fileand even in a different assembly.

In Chapter 26, we introduced generics. In the next two sections, we demonstrate how to use generic collections.