Section 26.4. Non-Generic Collections
26.4. Non-Generic CollectionsThe 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 24 with collections that store references of type Object. In this section, we demonstrate classes ArrayList, Stack and Hashtable. 26.4.1. Class ArrayListIn most programming languages, conventional arrays have a fixed sizethey cannot grow or shrink 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 dynamic data structures that can grow and shrink the amount of memory required to store data in response to an application's changing requirements 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, by default it doubles its Capacity. Performance Tip 26.1
Performance Tip 26.2
Performance Tip 26.3
Performance Tip 26.4
ArrayLists store references to Objects. All classes derive from class Object, so an ArrayList can contain objects of any reference type and boxed primitive-type values. Figure 26.4 lists some useful methods and properties of class ArrayList.
Figure 26.5 demonstrates class ArrayList and several of its methods. Class ArrayList belongs to the System.Collections namespace (line 3). Lines 68 declare two arrays of Strings (colors and removeColors) that we will use to fill two ArrayList objects. When the application begins execution, we create an ArrayList (named list) with an initial capacity of one element (line 11). The For Each statement in lines 1517 adds the five elements of array colors to list via ArrayList's Add method, so list grows to accommodate these new elements. Line 21 uses ArrayList's overloaded constructor to create a new ArrayList (named removeList) initialized with the contents of array removeColors. 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. Note that the constructor call in line 21 initializes ArrayList removeList in a manner similar to lines 1517. Figure 26.5. Using class ArrayList
Line 24 calls method DisplayInformation (lines 3553) to output the contents of the list. This method uses a For Each statement to traverse the elements of an ArrayList. As we discussed in Section 26.3, the For Each statement is a convenient shorthand for calling ArrayList's GetEnumerator method and using an enumerator to traverse the elements of the collection. Also, we use an iteration variable of type Object because class ArrayList stores references to Objects. We use properties Count and Capacity in lines 4243 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. 26.5 indicates that the ArrayList has capacity 8recall that an ArrayList doubles its capacity whenever it needs more space. In line 45, 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. Lines 4752 determine whether arrayList contains "BLUE". If it does (i.e., index is not equal to -1), we output the 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. Performance Tip 26.5
After DisplayInformation returns, we call method RemoveColorNames (lines 5662) with the two ArrayLists. Lines 5961 iterate through secondList. Line 60 uses an indexer to access an ArrayList element by following the ArrayList reference name with parentheses (()) containing the desired element's index. 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 RemoveColorNames, line 31 again outputs the contents of list, confirming that the elements of removeList were, indeed, removed. 26.4.2. Class StackThe Stack class implements a stack data structure and provides much of the functionality that we defined in our own implementation in Section 24.5. Refer to that section for a discussion of stack concepts. We created a test application in Fig. 24.14. to demonstrate our StackInheritance data structure. We adapt Fig. 24.14 in Fig. 26.6 to demonstrate the .NET Framework collection class Stack. Figure 26.6. Demonstrating class Stack
Line 3 Imports class Stack. Line 7 creates a Stack with the default initial capacity (10 elements). 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 16, 18, 20 and 22 use method Push to add four elements (a Boolean, a Char, an Integer and a String) to the stack. After each Push, we invoke method PrintStack (lines 4357) to output the contents of the stack. Note that this non-generic Stack class can store only references to Objects, so each of the value-type itemsthe Boolean, the Char and the Integerare 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. 26.6.) Method PrintStack (lines 4357) uses Stack property Count 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 For Each statement to iterate over the stack and output its contents by implicitly invoking the ToString method of each element. The For Each 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 27 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. Method Pop takes no argumentsit removes and returns the object currently on top of the Stack. An infinite loop (lines 3135) 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 3638) outputs the exception, implicitly invoking the InvalidOperationException's ToString method to obtain its error message and stack trace. Common Programming Error 26.3
Although Fig. 26.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. 26.4.3. Class HashtableWhen an application creates objects, it needs to manage those objects efficiently. This includes storing and retrieving objects. Storing and retrieving information with arrays is efficient if some aspect of your data directly matches the key value and if the 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 massive 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 store two different data records in 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, it is assumed is that an available cell will be found with just a few hashes. 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, and 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 increases. Performance Tip 26.6
The .NET Framework provides class Hashtable to enable you to easily employ hashing in applications. 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 classes 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 26.7 uses a Hashtable to count the number of occurrences of each word in a String. Figure 26.7. Application counts the number of occurrences of each word in a String and stores this information in a hash table
Lines 45 contain Imports statements for the System.Text.RegularExpressions namespace (for class Regex, discussed in Chapter 16) and the System.Collections namespace (for class Hashtable). Class HashtableTest declares three methods. Method CollectWords (lines 1740) 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 as the key. Method DisplayHashtable (lines 4354) displays in column format the Hashtable passed to it. The Main method (lines 814) invokes CollectWords (line 10), then passes the Hashtable returned by CollectWords to DisplayHashtable (line 13). Method CollectWords (lines 1740) initializes local variable table with a new Hashtable (line 18) 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 2021 prompt the user and input a String. We use Shared method Split of class Regex in line 24 to divide the String into words using whitespace characters as delimiters. This creates an array of "words," which we then store in local variable words. The For Each statement in lines 2737 iterates through the elements of array words. Each word is converted to lowercase with String method ToLower, then stored in variable wordKey (line 28). Line 31 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 35 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 the Integer value 1 to method Add, because the hash table stores both the key and value as references to Objects. Common Programming Error 26.4
If the word is already a key in the hash table, line 32 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 from an Object to an Integer. This unboxes the value so that we can increment it by 1. We then use the indexer to store the key's associated value. The incremented value is implicitly reboxed so that it can be stored in the hash table. Invoking the Get accessor of a Hashtable indexer with a key that does not exist in the hash table returns a Nothing 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 39 returns the hash table to the Main method, which then passes it to method DisplayHashtable (lines 4354), which displays all the entries. This method uses read-only property Keys (line 49) to get an ICollection that contains all the keys. Because ICollection extends IEnumerable, we can use this collection in the For Each statement in lines 4951 to iterate over the keys of the hash table. This loop accesses and outputs each key and its value in a field width of -12. The negative field width indicates that the output should be left justified. Note that a hash table is not sorted, so the keyvalue pairs are not displayed in any particular order. Line 53 uses Hashtable property Count to get the number of keyvalue pairs in the Hashtable. Lines 4951 could also have used the For Each statement with the Hashtable object itself, rather than the Keys property. If you use a For Each statement with a Hashtable object, the iteration variable will be of type Dictionary Entry. 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. Problems with Non-Generic CollectionsIn the word-counting application in Fig. 26.7, our Hashtable stores its keys and data as Object references, even though we store only String keys and Integer values by convention. This results in some awkward code. For example, line 32 was forced to unbox and box the Integer data stored in the Hashtable every time it incremented the count for a particular key. This is inefficient. A similar problem occurs in lines 49 and 50the iteration variable of the For Each 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. 26.7 by using the indexer's Set accessor instead of the Add method to add a keyvalue pair in line 41, but accidentally type: table(wordKey) = wordKey ' initialize to 1 This statement creates a new entry with a String key and String value instead of an Integer value of 1. Although the application will compile correctly, this is clearly incorrect. If a word appears twice, line 32 will try to downcast this String to an Integer, causing an InvalidCastException at execution time. The error that appears at execution time will indicate that the problem is in line 32, where the exception occurred, not in line 35. 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 25, we introduced generics. In the next two sections, we demonstrate how to use generic collections, which can prevent the problem we just discussed. |
\ch26\Fig26_06\StackTest\ StackTest.vb:line 32 
EAN: 2147483647
Pages: 435