|
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 ClassThe 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. NOTE
EnumerationsThe 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 NOTE
java.util.Enumeration<E> 1.0
java.util.Hashtable<K, V> 1.0
java.util.Vector<E> 1.0
Property SetsA property set is a map structure of a very special type. It has three particular characteristics.
The Java platform class that implements a property set is called Properties. Property sets are commonly used in specifying configuration options for programssee Volume 1, Chapter 10. java.util.Properties 1.0
StacksSince 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 perspectiveyou 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. java.util.Stack<E> 1.0
Bit SetsThe Java platform BitSet class stores a sequence of bits. (It is not a set in the mathematical sensebit 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. C++ NOTE
java.util.BitSet 1.0
The "Sieve of Eratosthenes" BenchmarkAs 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. NOTE
Example 2-8. Sieve.java1. 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.cpp1. #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. } |
|