Exercises

Solutions to selected exercises can be found in the electronic document The Thinking in Java Annotated Solution Guide, available for a small fee from www.BruceEckel.com.

1. Create an array of double and fill( ) it using RandDoubleGenerator. Print the results.
2. Create a new class called Gerbil with an int gerbilNumber that’s initialized in the constructor (similar to the Mouse example in this chapter). Give it a method called hop( ) that prints out which gerbil number this is, and that it’s hopping. Create an ArrayList and add a bunch of Gerbil objects to the List. Now use the get( ) method to move through the List and call hop( ) for each Gerbil.
3. Modify Exercise 2 so you use an Iterator to move through the List while calling hop( ).
4. Take the Gerbil class in Exercise 2 and put it into a Map instead, associating the name of the Gerbil as a String (the key) for each Gerbil (the value) you put in the table. Get an Iterator for the keySet( ) and use it to move through the Map, looking up the Gerbil for each key and printing out the key and telling the gerbil to hop( ).
5. Create a List (try both ArrayList and LinkedList) and fill it using Collections2.countries. Sort the list and print it, then apply Collections.shuffle( ) to the list repeatedly, printing it each time so that you can see how the shuffle( ) method randomizes the list differently each time.
6. Demonstrate that you can’t add anything but a Mouse to a MouseList.
7. Modify MouseList.java so that it inherits from ArrayList instead of using composition. Demonstrate the problem with this approach. Repair CatsAndDogs.java by creating a Cats container (utilizing ArrayList) that will only accept and retrieve Cat objects.
8. Fill a HashMap with key-value pairs. Print the results to show ordering by hash code. Extract the pairs, sort by key, and place the result into a LinkedHashMap. Show that the insertion order is maintained.
9. Repeat the previous example with a HashSet and LinkedHashSet.
10. Create a new type of container that uses a private ArrayList to hold the objects. Using a Class reference, capture the type of the first object you put in it, and then allow the user to insert objects of only that type from then on.
11. Create a container that encapsulates an array of String, and that only adds Strings and gets Strings, so that there are no casting issues during use. If the internal array isn’t big enough for the next add, your container should automatically resize it. In main( ), compare the performance of your container with an ArrayList holding Strings.
12. Repeat Exercise 12 for a container of int, and compare the performance to an ArrayList holding Integer objects. In your performance comparison, include the process of incrementing each object in the container.
13. Using the utilities in com.bruceeckel.util, create an array of each primitive type and of String, then fill each array by using an appropriate generator, and print each array using the appropriate print( ) method.
14. Create a generator that produces character names from your favorite movies (you can use Snow White or Star Wars as a fallback) and loops around to the beginning when it runs out of names. Use the utilities in com.bruceeckel.util to fill an array, an ArrayList, a LinkedList, and both types of Set, then print each container.
15. Create a class containing two String objects and make it Comparable so that the comparison only cares about the first String. Fill an array and an ArrayList with objects of your class by using the geography generator. Demonstrate that sorting works properly. Now make a Comparator that only cares about the second String and demonstrate that sorting works properly. Also perform a binary search using your Comparator.
16. Modify Exercise 16 so that an alphabetic sort is used.
17. Use Arrays2.RandStringGenerator to fill a TreeSet, but by using alphabetic ordering. Print the TreeSet to verify the sort order.
18. Create both an ArrayList and a LinkedList, and fill each using the Collections2.capitals generator. Print each list using an ordinary Iterator, then insert one list into the other by using a ListIterator, inserting at every other location. Now perform the insertion starting at the end of the first list and moving backward. Write a method that uses an Iterator to step through a Collection and print the hashCode( ) of each object in the container. Fill all the different types of Collections with objects and apply your method to each container.
19. Repair the problem in InfiniteRecursion.java.
20. Create a class, then make an initialized array of objects of your class. Fill a List from your array. Create a subset of your List by using subList( ), then remove this subset from your List by using removeAll( ).
21. Change Exercise 6 in Chapter 7 to use an ArrayList to hold the Rodents and an Iterator to move through the sequence of Rodents. Remember that an ArrayList holds only Objects, so you must use a cast when accessing individual Rodents.
22. Following the Queue.java example, create a Deque class and test it.
23. Use a TreeMap in Statistics.java. Now add code that tests the performance difference between HashMap and TreeMap in that program.
24. Produce a Map and a Set containing all the countries that begin with “A.”
25. Using Collections2.countries, fill a Set multiple times with the same data and verify that the Set ends up with only one of each instance. Try this with both kinds of Set.
26. Starting with Statistics.java, create a program that runs the test repeatedly and looks to see if any one number tends to appear more than the others in the results.
27. Rewrite Statistics.java using a HashSet of Counter objects (you’ll have to modify Counter so that it will work in the HashSet). Which approach seems better?
28. Fill a LinkedHashMap with String keys and objects of your choice. Now extract the pairs, sort them based on the keys, and re-insert them into the Map.
29. Modify the class in Exercise 16 so that the class will work with HashSets and as a key in HashMaps.
30. Using SlowMap.java for inspiration, create a SlowSet. Create a FastTraversalLinkedList that internally uses a LinkedList for rapid insertions and removals, and an ArrayList for rapid traversals and get( ) operations. Test it by modifying ArrayPerformance.java.
31. Apply the tests in Map1.java to SlowMap to verify that it works. Fix anything in SlowMap that doesn’t work correctly. Implement the rest of the Map interface for SlowMap. Modify MapPerformance.java to include tests of SlowMap. Modify SlowMap so that instead of two ArrayLists, it holds a single ArrayList of MPair objects. Verify that the modified version works correctly. Using MapPerformance.java, test the speed of your new Map. Now change the put( ) method so that it performs a sort( ) after each pair is entered, and modify get( ) to use Collections.binarySearch( ) to look up the key. Compare the performance of the new version with the old ones. Add a char field to CountedString that is also initialized in the constructor, and modify the hashCode( ) and equals( ) methods to include the value of this char. Modify SimpleHashMap so that it reports collisions, and test this by adding the same data set twice so that you see collisions.
32. Modify SimpleHashMap so that it reports the number of “probes” necessary when collisions occur. That is, how many calls to next( ) must be made on the Iterators that walk the LinkedLists looking for matches?
33. Implement the clear( ) and remove( ) methods for SimpleHashMap.
34. Implement the rest of the Map interface for SimpleHashMap.
35. Add a private rehash( ) method to SimpleHashMap that is invoked when the load factor exceeds 0.75. During rehashing, double the number of buckets, then search for the first prime number greater than that to determine the new number of buckets.
36. Following the example in SimpleHashMap.java, create and test a SimpleHashSet.
37. Modify SimpleHashMap to use ArrayLists instead of LinkedLists. Modify MapPerformance.java to compare the performance of the two implementations.
38. Using the HTML documentation for the JDK (downloadable from java.sun.com), look up the HashMap class. Create a HashMap, fill it with elements, and determine the load factor. Test the lookup speed with this map, then attempt to increase the speed by making a new HashMap with a larger initial capacity and copying the old map into the new one, then run your lookup speed test again on the new map.
39. In Chapter 8, locate the GreenhouseController.java example, which consists of four files. In Controller.java, the class Controller uses an ArrayList. Change the code to use a LinkedList instead, and use an Iterator to cycle through the set of events. (Challenging). Write your own hashed map class, customized for a particular key type: String for this example. Do not inherit it from Map. Instead, duplicate the methods so that the put( ) and get( ) methods specifically take String objects, not Objects, as keys. Everything that involves keys should not use generic types; instead, work with Strings to avoid the cost of upcasting and downcasting. Your goal is to make the fastest possible custom implementation. Modify MapPerformance.java to test your implementation versus a HashMap.
40. (Challenging). Find the source code for List in the Java source code library that comes with all Java distributions. Copy this code and make a special version called intList that holds only ints. Consider what it would take to make a special version of List for all the primitive types. Now consider what happens if you want to make a linked list class that works with all the primitive types.
41. Modify c08:Month.java to make it implement the Comparable interface.
42. Modify the hashCode( ) in CountedString.java by removing the multiplication by id, and demonstrate that CountedString still works as a key. What is the problem with this approach? href="TIJ313.htm">[51] It’s possible, however, to ask how big the vector is, and the at( ) method does perform bounds checking.
    

    ^[52] This is one of the places where C++ is distinctly superior to Java, since C++ supports parameterized types with the template keyword.
    

    ^[53] The C++ programmer will note how much the code could be collapsed with the use of default arguments and templates. The Python programmer will note that this entire library would be largely unnecessary in that language.
    

    ^[54] Design Patterns, Erich Gamma et al., Addison-Wesley 1995.
    

    ^[55] By Joshua Bloch at Sun.
    

    ^[56] This data was found on the Internet, then processed by creating a Python program (see www.Python.org).
    

    ^[57] This is a place where operator overloading would be nice.
    

    ^[58] If these speedups still don’t meet your performance needs, you can further accelerate table lookup by writing your own Map and customizing it to your particular types to avoid delays due to casting to and from Objects. To reach even higher levels of performance, speed enthusiasts can use Donald Knuth’s The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition to replace overflow bucket lists with arrays that have two additional benefits: they can be optimized for disk storage characteristics and they can save most of the time of creating and garbage collecting individual records.
    

    ^[59] As it turns out, a prime number is not actually the ideal size for hash buckets, and recent hashed implementations in Java uses a power of two size (after extensive testing). Division or remainder is the slowest operation on a modern processor. With a power-of-two hash table length, masking can be used instead of division. Since get( ) is by far the most common operation, the % is a large part of the cost, and the power-of-two approach eliminates this (but may also affect some hashCode( ) methods).
    

    ^[60] In a private message, Joshua Bloch wrote: “... I believe that we erred by allowing implementation details (such as hash table size and load factor) into our APIs. The client should perhaps tell us the maximum expected size of a collection, and we should take it from there. Clients can easily do more harm than good by choosing values for these parameters. As an extreme example, consider Vector’s capacityIncrement. No one should ever set this, and we shouldn’t have provided it. If you set it to any non-zero value, the asymptotic cost of a sequence of appends goes from linear to quadratic. In other words, it destroys your performance. Over time, we’re beginning to wise up about this sort of thing. If you look at IdentityHashMap, you’ll see that it has no low-level tuning parameters.”
    

    Thinking in Java
    Prev	Contents / Index	Next