Classic Collections Classes

Java version 1.2 introduced the collections framework. Prior to the framework's inclusion in Java, developers had two choices where collections were concerned: create their own frameworks, or use the Vector, Enumeration, Stack, Dictionary, Hashtable, Properties, and BitSet types, which were introduced by Java version 1.0.

Vector is a concrete class that describes a growable array, much like ArrayList. Unlike an ArrayList instance, a Vector instance is synchronized. Vector has been generified and also retrofitted to support the collections framework, which makes statements such as List<String> list = new Vector<String>(); legal.

The collections framework provides Iterator for iterating over a collection's elements. In contrast, Vector's elements() method returns an instance of a class that implements the Enumeration interface for enumerating (iterating over and returning) a Vector instance's elements via Enumeration's hasMoreElements() and nextElement() methods.

Vector is subclassed by the concrete Stack class, which represents a LIFO data structure. Stack provides an E push(E item) method for pushing an object onto the stack, an E pop() method for popping an item off the top of the stack, and a few other methods, such as boolean empty() for determining whether or not the stack is empty.

Stack is a good example of bad API design. By inheriting from Vector, it is possible to call Vector's void add(int index, E element) method to add an element anywhere you wish, and violate a Stack instance's integrity. In hindsight, Stack should have used composition in its design: use a Vector instance to store a Stack instance's elements.

Dictionary is an abstract superclass for subclasses that map keys to values. The concrete Hashtable class is Dictionary's only subclass. As with Vector, HashTable instances are synchronized, HashTable has been generified, and HashTable has been retrofitted to support the collections framework.

Hashtable is subclassed by Properties, a concrete class representing a persistent set of properties (String-based key/value pairs that identify application settings). Properties provides Object setProperty(String key, String value) for storing a property, and public String getProperty(String key) for returning a property's value.

NOTE: Applications use properties for various purposes. For example, if your application has a graphical user interface, you might persist its main window's screen location and size to a file via a Properties object so that the application can restore the window's location and size when it next runs.

Properties is another good example of bad API design. By inheriting from Hashtable, you can call Hashtable's V put(K key, V value) method to store an entry with a non-String key and/or a non-String value. In hindsight, Properties should have leveraged composition: store a Properties instance's elements in a Hashtable instance.

NOTE: Chapter 3 discusses wrapper classes, which is how Stack and Properties should have been implemented.

Finally, BitSet is a concrete class that describes a variable-length set of bits. This class's ability to represent bitsets of arbitrary length contrasts with the previously described integer-based, fixed-length bitset that is limited to a maximum number of members: 32 members for an int-based bitset, or 64 members for a long-based bitset.

BitSet provides a pair of constructors for initializing a BitSet instance: BitSet() initializes the instance to initially store an implementation-dependent number of bits, whereas BitSet(int nbits) initializes the instance to initially store nbits bits. BitSet also provides various methods, including the following:

■ void and(BitSet bs) bitwise ANDs this bitset with bs. This bitset is modified such that a bit is set to 1 when it and the bit at the same position in bs are 1.

■ void andNot(BitSet bs) sets all of the bits in this bitset to 0 whose corresponding bits are set to 1 in bs.

■ void clear() sets all of the bits in this bitset to 0.

■ Object clone() clones this bitset to produce a new bitset. The clone has exactly the same bits set to one as this bitset.

■ boolean get(int bitIndex) returns the value of this bitset's bit, as a Boolean true/false value (true for 1, false for 0) at the zero-based bitIndex. This method throws IndexOutOfBoundsException when bitIndex is less than 0.

■ int length() returns the "logical size" of this bitset, which is the index of the highest 1 bit plus 1, or 0 if this bitset contains no 1 bits.

■ void or(BitSet bs) bitwise inclusive ORs this bitset with bs. This bitset is modified such that a bit is set to 1 when it or the bit at the same position in bs is 1, or when both bits are 1.

■ void set(int bitIndex, boolean value) sets the bit at the zero-based bitIndex to value (true is converted to 1; false is converted to 0). This method throws IndexOutOfBoundsException when bitIndex is less than 0.

■ int size() returns the number of bits that are being used by this bitset to represent bit values.

■ String toString() returns a string representation of this bitset in terms of the positions of bits that are 1; for example, {4, 5, 9, 10}.

■ void xor(BitSet set) bitwise exclusive ORs this bitset with bs. This bitset is modified such that a bit is set to 1 when either it or the bit at the same position in bs (but not both) is 1.

Listing 8-30 presents an application that demonstrates some of these methods, and gives you more insight into how the bitwise AND (&), bitwise inclusive OR (|), and bitwise exclusive OR (A) operators work.

Listing 8-30. Working with variable-length bitsets import java.util.BitSet;

public class BitSetDemo {

public static void main(String[] args) {

BitSet bs1 = new BitSet(); bs1.set(4, true); bs1.set(5, true); bs1.set(9, true); bs1.set(10, true);

BitSet bsTemp = (BitSet) bs1.clone(); dumpBitset(" ", bs1);

BitSet bs2 = new BitSet(); bs2.set(4, true); bs2.set(6, true); bs2.set(7, true); bs2.set(9, true); dumpBitset(" ", bs2);

dumpSeparator(Math.min(bs1.size(), 16)); dumpBitset("AND (&) ", bs1); System.out.println(); bs1 = bsTemp;

dumpSeparator(Math.min(bs1.size(), 16)); dumpBitset("OR (|) ", bs1); System.out.println(); bs1 = bsTemp;

dumpSeparator(Math.min(bs1.size(), 16)); dumpBitset("XOR (A) ", bsl);

static void dumpBitset(String preamble, BitSet bs) {

System.out.print(preamble);

for (int i = 0; i < Math.min(bs.size(), 16); i++)

System.out.print(bs.get(i) ? "1" : "0"); System.out.print(" size(" + bs.size() + "), length(" + bs.length() + ")"); System.out.println();

static void dumpSeparator(int len) {

System.out.print("-"); System.out.println();

Why did I specify Math.min(bs.size(), 16) in dumpBitset(), and pass a similar expression to dumpSeparator()? I wanted to display exactly 16 bits and 16 dashes (for aesthetics), and needed to account for a bitset's size being less than 16. Although this does not happen with the JDK's BitSet class, it might happen with a non-JDK variant.

When you run this application, it generates the following output:

0000110001100000 size(64), length(11) 0000101101000000 size(64), length(10)

AND (&) 0000100001000000 size(64), length(io)

0000110001100000 size(64), length(ll) 0000101101000000 size(64), length(10)

OR (|) 0000111101100000 size(64), length(11)

0000110001100000 size(64), length(11) 0000101101000000 size(64), length(10)

XOR (A) 0000011100100000 size(64), length(11)

CAUTION: Unlike Vector and Hashtable, BitSet is not synchronized. You must externally synchronize access to this class when using BitSet in a multithreaded context.

The collections framework has made Vector, Enumeration, Stack, Dictionary, and Hashtable obsolete. These types continue to be part of the standard class library to support legacy code. Also, the Preferences API (see Chapter 9) has made Properties largely obsolete. Because BitSet is still relevant, this class continues to be improved.

NOTE: It is not surprising that BitSet is being improved (as recently as Java version 6 at time of writing) when you realize the usefulness of variable-length bitsets. Because of their compactness and other advantages, variable-length bitsets are often used to implement an operating system's priority queues and facilitate memory page allocation. Unix-oriented file systems also use bitsets to facilitate the allocation of inodes (information nodes) and disk sectors. And bitsets are useful in Huffman coding, a data-compression algorithm for achieving lossless data compression.

EXERCISES

The following exercises are designed to test your understanding of the collections framework:

1. What is a collection?

2. What is the collections framework?

3. The collections framework largely consists of what components?

4. What is a comparable?

5. When would you have a class implement the Comparable interface?

6. What is a comparator and what is its purpose?

7. True or false: A collection uses a comparator to define the natural ordering of its elements.

8. What does the Iterable interface describe?

9. What does the Collection interface represent?

10. Identify a situation where Collection's add() method would throw an instance of the UnsupportedOperationException class.

11. Iterable's iterator() method returns an instance of a class that implements the Iterator interface. What methods does this interface provide?

12. What is the purpose of the enhanced for loop statement?

13. How is the enhanced for loop statement expressed?

14. True or false: The enhanced for loop works with arrays.

15. What is autoboxing?

16. What is unboxing?

18. What does a ListIterator instance use to navigate through a list?

20. Why would you use the subList() method?

21. What does the ArrayList class provide?

22. What does the LinkedList class provide?

24. True or false: ArrayList provides faster element insertions and deletions than LinkedList.

26. What does the TreeSet class provide?

27. What does the HashSet class provide?

28. True or false: To avoid duplicate elements in a hashset, your own classes must correctly override equals() and hashCode().

29. What is the difference between HashSet and LinkedHashSet?

30. What does the EnumSet class provide?

31. What is a sorted set?

32. True or false: HashSet is an example of a sorted set.

33. Why would a sorted set's add() method throw ClassCastException when you attempt to add an element to the sorted set?

34. What is a queue?

35. True or false: Queue's element() method throws NoSuchElementException when it is called on an empty queue.

36. What does the PriorityQueue class provide?

38. What does the TreeMap class provide?

39. What does the HashMap class provide?

40. What does a hashtable use to map keys to integer values?

41. Continuing from the previous question, what are the resulting integer values called, and what do they accomplish?

42. What is a hashtable's capacity?

43. What is a hashtable's load factor?

44. What is the difference between HashMap and LinkedHashMap?

45. What does the IdentityHashMap class provide?

46. What does the WeakHashMap class provide?

47. What does the EnumMap class provide?

48. What is a sorted map?

49. True or false: TreeMap is an example of a sorted map.

50. What is the purpose of the Arrays class's static <T> List<T> asList(T... array) method?

51. True or false: Binary search is slower than linear search.

52. Which Collections method would you use to return a synchronized variation of a hashset?

53. Identify the seven legacy collections-oriented types.

54. As an example of array list usefulness, create a JavaOuiz application that presents a multiple-choice-based quiz on Java features. The JavaOuiz class's main() method first populates the array list with the entries in the following OuizEntry array:

static OuizEntry[] quizEntries = {

new OuizEntry("What was Java's original name?", new String[] { "Oak", "Duke", "J", "None of the above" }, 'A'), new OuizEntry("Which of the following reserved words is also a literal?", new String[] { "for", "long", "true", "enum" }, 'C'), new OuizEntry("The conditional operator (?:) resembles which statement?", new String[] { "switch", "if-else", "if", "while" }, 'B')

Each OuizEntry instance consists of a question, four possible answers, and the letter (A, B, C, or D) of the correct answer.

main() then uses the array list's iterator() method to return an Iterator instance, and this instance's hasNext() and next() methods to iterate over the list. Each of the iterations outputs the question and four possible answers, and then prompts the user to enter the correct choice. After the user enters A, B, C, or D, main() outputs a message stating whether or not the user made the correct choice.

55. Why is (int) (fA(f>>>32)) used instead of (int) (fA(f>>32)) in the hash code generation algorithm?

56. Collections provides the static int frequency(Collection<?> collection, Object o) method to return the number of collection elements that are equal to o. Create a FrequencyDemo application that reads its command-line arguments and stores all arguments except for the last argument in a list, and then calls frequency() with the list and last command-line argument as this method's arguments. It then outputs this method's return value (the number of occurrences of the last command-line argument in the previous command-line arguments). For example, java FrequencyDemo should output Number of occurrences of null = 0, and java FrequencyDemo how much wood could a woodchuck chuck if a woodchuck could chuck wood wood should output Number of occurrences of wood = 2.

Was this article helpful?

0 0

Post a comment