- Collection Interfaces
- Concrete Collections
- The Collections Framework
- Algorithms
- Legacy Collections
This chapter is from the book
This chapter is from the book
This chapter is from the book
Legacy Collections
In this section, we discuss the collection classes that existed in the Java programming language since the beginning: the Hashtable class and its useful Properties subclass, the Stack subclass of Vector, and the BitSet class.
The Hashtable Class
The classic Hashtable class serves the same purpose as the HashMap and has essentially the same interface. Just like methods of the Vector class, the Hashtable methods are synchronized. If you do not require synchronization or compatibility with legacy code, you should use the HashMap instead.
The name of the class is Hashtable, with a lowercase t. Under Windows, you'll get strange error messages if you use HashTable, because the Windows file system is not case-sensitive but the Java compiler is.
Enumerations
The legacy collections use the Enumeration interface for traversing sequences of elements. The Enumeration interface has two methods, hasMoreElements and nextElement. These are entirely analogous to the hasNext and next methods of the Iterator interface.
For example, the elements method of the Hashtable class yields an object for enumerating the values in the table:
Enumeration<Employee> e = staff.elements();
while (e.hasMoreElements())
{
Employee e = e.nextElement();
. . .
}
You will occasionally encounter a legacy method that expects an enumeration parameter. The static method Collections.enumeration yields an enumeration object that enumerates the elements in the collection. For example,
ArrayList<InputStream> streams = . . .; SequenceInputStream in = new SequenceInputStream(Collections.enumeration(streams)); // the SequenceInputStream constructor expects an enumeration
In C++, it is quite common to use iterators as parameters. Fortunately, in programming for the Java platform, very few programmers use this idiom. It is much smarter to pass around the collection than to pass an iterator. The collection object is more useful. The recipients can always obtain the iterator from the collection when they need to do so, plus they have all the collection methods at their disposal. However, you will find enumerations in some legacy code because they were the only available mechanism for generic collections until the collections framework appeared in JDK 1.2.
java.util.Enumeration<E> 1.0
- boolean hasMoreElements()
returns true if there are more elements yet to be inspected.
- E nextElement()
returns the next element to be inspected. Do not call this method if hasMoreElements() returned false.
- Enumeration<K> keys()
returns an enumeration object that traverses the keys of the hash table.
- Enumeration<V> elements()
returns an enumeration object that traverses the elements of the hash table.
- Enumeration<E> elements()
returns an enumeration object that traverses the elements of the vector.
Property Sets
A property set is a map structure of a very special type. It has three particular characteristics.
- The keys and values are strings.
- The table can be saved to a file and loaded from a file.
- A secondary table for defaults is used.
The Java platform class that implements a property set is called Properties.
Property sets are commonly used in specifying configuration options for programs—see Volume 1, Chapter 10.
- Properties()
creates an empty property list.
- Properties(Properties defaults)
creates an empty property list with a set of defaults.
- String getProperty(String key)
gets a property association; returns the string associated with the key, or the string associated with the key in the default table if it wasn't present in the table.
- String getProperty(String key, String defaultValue)
gets a property with a default value if the key is not found; returns the string associated with the key, or the default string if it wasn't present in the table.
- void load(InputStream in)
loads a property set from an InputStream.
- void store(OutputStream out, String commentString)
stores a property set to an OutputStream.
Stacks
Since version 1.0, the standard library had a Stack class with the familiar push and pop methods. However, the Stack class extends the Vector class, which is not satisfactory from a theoretical perspective—you can apply such un-stack-like operations as insert and remove to insert and remove values anywhere, not just at the top of the stack.
- E push(E item)
pushes item onto the stack and returns item.
- E pop()
pops and returns the top item of the stack. Don't call this method if the stack is empty.
- E peek()
returns the top of the stack without popping it. Don't call this method if the stack is empty.
Bit Sets
The Java platform BitSet class stores a sequence of bits. (It is not a set in the mathematical sense—bit vector or bit array would have been more appropriate terms.) Use a bit set if you need to store a sequence of bits (for example, flags) efficiently. Because a bit set packs the bits into bytes, it is far more efficient to use a bit set than to use an ArrayList of Boolean objects.
The BitSet class gives you a convenient interface for reading, setting, or resetting individual bits. Use of this interface avoids the masking and other bit-fiddling operations that would be necessary if you stored bits in int or long variables.
For example, for a BitSet named bucketOfBits,
bucketOfBits.get(i)
returns true if the i'th bit is on, and false otherwise. Similarly,
bucketOfBits.set(i)
turns the i'th bit on. Finally,
bucketOfBits.clear(i)
turns the i'th bit off.
The C++ bitset template has the same functionality as the Java platform BitSet.
- BitSet(int initialCapacity)
constructs a bit set.
- int length()
returns the “logical length” of the bit set: 1 plus the index of the highest set bit.
- boolean get(int bit)
gets a bit.
- void set(int bit)
sets a bit.
- void clear(int bit)
clears a bit.
- void and(BitSet set)
logically ANDs this bit set with another.
- void or(BitSet set)
logically ORs this bit set with another.
- void xor(BitSet set)
logically XORs this bit set with another.
- void andNot(BitSet set)
clears all bits in this bit set that are set in the other bit set.
The “Sieve of Eratosthenes” Benchmark
As an example of using bit sets, we want to show you an implementation of the “sieve of Eratosthenes” algorithm for finding prime numbers. (A prime number is a number like 2, 3, or 5 that is divisible only by itself and 1, and the sieve of Eratosthenes was one of the first methods discovered to enumerate these fundamental building blocks.) This isn't a terribly good algorithm for finding the number of primes, but for some reason it has become a popular benchmark for compiler performance. (It isn't a good benchmark either, because it mainly tests bit operations.)
Oh well, we bow to tradition and include an implementation. This program counts all prime numbers between 2 and 2,000,000. (There are 148,933 primes, so you probably don't want to print them all out.)
Without going into too many details of this program, the key is to march through a bit set with 2 million bits. We first turn on all the bits. After that, we turn off the bits that are multiples of numbers known to be prime. The positions of the bits that remain after this process are themselves the prime numbers. Example 2-8 illustrates this program in the Java programming language, and Example 2-9 is the C++ code.
Even though the sieve isn't a good benchmark, we couldn't resist timing the two implementations of the algorithm. Here are the timing results on a 1.7-GHz IBM ThinkPad with 1 GB of RAM, running Red Hat Linux 9.
C++ (g++ 3.2.2): 330 milliseconds
Java (JDK 5.0): 105 milliseconds
We have run this test for six editions of Core Java, and in the last three editions Java easily beat C++. In previous editions, we pointed out, in all fairness, that the culprit for the bad C++ result is the lousy performance of the standard bitset template. When we reimplemented bitset, the time for C++ used to be faster than Java. Not anymore—with a handcrafted bitset, the C++ time was 140 milliseconds in our latest experiment.
Example 2-8. Sieve.java
1. import java.util.*;
2.
3. /**
4. This program runs the Sieve of Eratosthenes benchmark.
5. It computes all primes up to 2,000,000.
6. */
7. public class Sieve
8. {
9. public static void main(String[] s)
10. {
11. int n = 2000000;
12. long start = System.currentTimeMillis();
13. BitSet b = new BitSet(n + 1);
14. int count = 0;
15. int i;
16. for (i = 2; i <= n; i++)
17. b.set(i);
18. i = 2;
19. while (i * i <= n)
20. {
21. if (b.get(i))
22. {
23. count++;
24. int k = 2 * i;
25. while (k <= n)
26. {
27. b.clear(k);
28. k += i;
29. }
30. }
31. i++;
32. }
33. while (i <= n)
34. {
35. if (b.get(i))
36. count++;
37. i++;
38. }
39. long end = System.currentTimeMillis();
40. System.out.println(count + " primes");
41. System.out.println((end - start) + " milliseconds");
42. }
43. }
Example 2-9. Sieve.cpp
1. #include <bitset>
2. #include <iostream>
3. #include <ctime>
4.
5. using namespace std;
6.
7. int main()
8. {
9. const int N = 2000000;
10. clock_t cstart = clock();
11.
12. bitset<N + 1> b;
13. int count = 0;
14. int i;
15. for (i = 2; i <= N; i++)
16. b.set(i);
17. i = 2;
18. while (i * i <= N)
19. {
20. if (b.test(i))
21. {
22. count++;
23. int k = 2 * i;
24. while (k <= N)
25. {
26. b.reset(k);
27. k += i;
28. }
29. }
30. i++;
31. }
32. while (i <= N)
33. {
34. if (b.test(i))
35. count++;
36. i++;
37. }
38.
39. clock_t cend = clock();
40. double millis = 1000.0
41. * (cend - cstart) / CLOCKS_PER_SEC;
42.
43. cout << count << " primes\n"
44. << millis << " milliseconds\n";
45.
46. return 0;
47. }