Certification Objective Using the Collections Framework (Objective 6.5)
Certification Objective —Using the Collections Framework (Objective 6.5)
6.5 Use capabilities in the java.util package to write code to manipulate a list by sorting, performing a binary search, or converting the list to an array. Use capabilities in the java.util package to write code to manipulate an array by sorting, performing a binary search, or converting the array to a list. Use the java.util. Comparator and java.lang.Comparable interfaces to affect the sorting of lists and arrays. Furthermore, recognize the effect of the "natural ordering" of primitive wrapper classes and java.lang. String on sorting.
We've taken a high-level, theoretical look at the key interfaces and classes in the Collections Framework, now let's see how they work in practice.
ArrayList Basics
The java.util.ArrayList class is one of the most commonly used of all the classes in the Collections Framework. It's like an array on vitamins. Some of the advantages ArrayList has over arrays are
-
It can grow dynamically.
-
It provides more powerful insertion and search mechanisms than arrays.
Let's take a look at using an ArrayList that contains Strings. A key design goal of the Collections Framework was to provide rich functionality at the level of the main interfaces: List, Set, and Map. In practice, you'll typically want to instantiate an ArrayList polymorphically like this:
List myList = new ArrayList();
As of Java 5 you'll want to say
List<String> myList = new ArrayList<String>();
This kind of declaration follows the object oriented programming principle of "coding to an interface", and it makes use of generics. We'll say lots more about generics later in this chapter, but for now just know that, as of Java 5, the <String> syntax is the way that you declare a collection's type. (Prior to Java 5 there was no way to specify the type of a collection, and when we cover generics, we'll talk about the implications of mixing Java 5 (typed) and pre-Java 5 (untyped) collections.)
In many ways, ArrayList<String> is similar to a String[] in that it declares a container that can hold only Strings, but it's more powerful than a String[]. Let's look at some of the capabilities that an ArrayList has:
import java.util.*; public class TestArrayList { public static void main(String[] args) { List<String> test = new ArrayList<String>(); String s = "hi"; test.add("string"); test.add(s); test.add(s+s); System.out.println(test.size()); System.out.println(test.contains(42)); System.out.println(test.contains("hihi")); test.remove("hi"); System.out.println(test.size()); } } which produces:
3 false true 2
There's lots going on in this small program. Notice that when we declared the ArrayList we didn't give it a size. Then we were able to ask the ArrayList for its size, we were able to ask it whether it contained specific objects, we removed an object right out from the middle of it, and then we re-checked its size.
Autoboxing with Collections
In general, collections can hold Objects but not primitives. Prior to Java 5, a very common use for the wrapper classes was to provide a way to get a primitive into a collection. Prior to Java 5, you had to wrap a primitive by hand before you could put it into a collection. With Java 5, primitives still have to be wrapped, but autoboxing takes care of it for you.
List myInts = new ArrayList(); // pre Java 5 declaration myInts.add(new Integer(42)); // had to wrap an int
As of Java 5 we can say
myInts.add(42); // autoboxing handles it!
In this last example, we are still adding an Integer object to myInts (not an int primitive); it's just that autoboxing handles the wrapping for us.
Sorting Collections and Arrays
Sorting and searching topics have been added to the exam for Java 5. Both collections and arrays can be sorted and searched using methods in the API.
Sorting Collections
Let's start with something simple like sorting an ArrayList of Strings alphabetically. What could be easier? Okay, we'll wait while you go find ArrayList's sort() method…got it? Of course, ArrayList doesn't give you any way to sort its contents, but the java.util.Collections class does:
import java.util.*; class TestSortl { public static void main(String[] args) { ArrayList<String> stuff = new ArrayList<String>(); // #1 stuff.add("Denver"); stuff.add("Boulder"); stuff.add("Vail") ; stuff.add("Aspen"); stuff.add("Telluride"); System.out.println("unsorted " + stuff); Collections.sort(stuff); // #2 System.out.println("sorted " + stuff); } } This produces something like this:
unsorted [Denver, Boulder, Vail, Aspen, Telluride] sorted [Aspen, Boulder, Denver, Telluride, Vail]
Line 1 is declaring an ArrayList of Strings, and line 2 is sorting the ArrayList alphabetically. We'll talk more about the Collections class, along with the Arrays class in a later section, for now let's keep sorting stuff.
Let's imagine we're building the ultimate home-automation application. Today we're focused on the home entertainment center, and more specifically the DVD control center. We've already got the file I/O software in place to read and write data between the dvdInfo.txt file and instances of class DVDInfo. Here are the key aspects of the class:
class DVDInfo { String title; String genre; String leadActor; DVDInfo(String t, String g, String a) { title = t; genre = g; leadActor = a; } public String toString() { return title + " " + genre + " " + leadActor + "\n"; } // getters and setter go here } Here's the DVD data that's in the dvdinfo.txt file:
Donnie Darko/sci-fi/Gyllenhall, Jake Raiders of the Lost Ark/action/Ford, Harrison 2001/sci-fi/?? Caddy Shack/comedy/Murray, Bill Star Wars/sci-fi/Ford, Harrison Lost in Translation/comedy/Murray, Bill Patriot Games/action/Ford, Harrison
In our home-automation application, we want to create an instance of DVDInfo for each line of data we read in from the dvdinfo.txt file. For each instance, we will parse the line of data (remember string.split()?) and populate DVDInfo's three instance variables. Finally, we want to put all of the DVDInfo instances into an ArrayList. Imagine that the populateList() method (below) does all of this. Here is a small piece of code from our application:
ArrayList<DVDInfo> dvdList = new ArrayList<DVDInfo>(); populateList(); // adds the file data to the ArrayList System.out.println(dvdList);
You might get output like this:
[Donnie Darko sci-fi Gyllenhall, Jake , Raiders of the Lost Ark action Ford, Harrison , 2001 sci-fi ?? , Caddy Shack comedy Murray, Bill , Star Wars sci-fi Ford, Harrison , Lost in Translation comedy Murray, Bill , Patriot Games action Ford, Harrison ]
(Note: We overrode DVDInfo's tostring() method, so when we invoked println() on the ArrayList it invoked tostring() for each instance.)
Now that we've got a populated ArrayList, let's sort it:
Collections.sort(dvdlist);
Oops!, you get something like this:
TestDVD.java:13: cannot find symbol symbol : method sort(java.util.ArrayList<DVDInfo>) location: class java.util.Collections Collections.sort(dvdlist);
What's going on here? We know that the Collections class has a sort() method, yet this error implies that Collections does NOT have a sort() method that can take a dvdlist. That means there must be something wrong with the argument we're passing (dvdinfo).
If you've already figured out the problem, our guess is that you did it without the help of the obscure error message shown above…How the heck do you sort instances of DVDInfo? Why were we able to sort instances of String? When you look up Collections.sort() in the API your first reaction might be to panic. Hang tight, once again the generics section will help you read that weird looking method signature. If you read the description of the one-arg sort() method, you'll see that the sort() method takes a List argument, and that the objects in the List must implement an interface called Comparable. It turns out that String implements Comparable, and that's why we were able to sort a list of Strings using the Collections.sort() method.
The Comparable Interface
The Comparable interface is used by the Collections.sort() method and the java.utils.Arrays.sort() method to sort Lists and arrays of objects, respectively. To implement Comparable, a class must implement a single method, compareTo(). Here's an invocation of compareTo():
int x = thisObject.compareTo(anotherObject);
The compareTo() method returns an int with the following characteristics:
| If thisObject < anotherObject |
| If thisObject == anotherObject |
| If thisObject > anotherObject |
The sort() method uses compareTo() to determine how the List or object array should be sorted. Since you get to implement compareTo() for your own classes, you can use whatever weird criteria you prefer, to sort instances of your classes. Returning to our earlier example for class DVDInfo, we can take the easy way out and use the String class's implementation of compareTo():
class DVDInfo implements Comparable<DVDInfo> { // #1 // existing code public int compareTo(DVDInfo d) { return title.compareTo(d.getTitle()); // #2 } } In line 1 we declare that class DVDInfo implements Comparable in such a way that DVDInfo objects can be compared to other DVDInfo objects. In line 2 we implement compareTo() by comparing the two DVDInfo object's titles. Since we know that the titles are Strings, and that String implements Comparable, this is an easy way to sort our DVDInfo objects, by title. Before generics came along in Java 5, you would have had to implement Comparable something like this:
class DVDInfo implements Comparable { // existing code public int compareTo(Object o) { // takes an Object rather // than a specific type DVDInfo d --- (DVDInfo)o; return title.compareTo(d.getTitle()); } } This is still legal, but you can see that it's both painful and risky, because you have to do a cast, and you need to verify that the cast will not fail before you try it.
 |
It's important to remember that when you override equals() you MUST take an argument of type object, but that when you override compareTo() you should take an argument of the type you're sorting.
|
Putting it all together, our DVDInfo class should now look like this:
class DVDInfo implements Comparable<DVDInfo> { String title; String genre; String leadActor; DVDInfo(String t, String g, String a) { title = t; genre = g; leadActor = a; } public String toString() { return title + " " + genre + " " + leadActor + "\n"; } public int compareTo(DVDInfo d) { return title.compareTo(d.getTitle()); } public String getTitle() { return title; } // other getters and setters } Now, when we invoke Collections.sort(dvdlist); we get
[2001 sci-fi ?? , Caddy Shack comedy Murray, Bill , Donnie Darko sci-fi Gyllenhall, Jake , Lost in Translation comedy Murray, Bill , Patriot Games action Ford, Harrison , Raiders of the Lost Ark action Ford, Harrison , Star Wars sci-fi Ford, Harrison ]
Hooray! Our ArrayList has been sorted by title. Of course, if we want our home automation system to really rock, we'll probably want to sort DVD collections in lots of different ways. Since we sorted our ArrayList by implementing the compareTo() method, we seem to be stuck. We can only implement compareTo() once in a class, so how do we go about sorting our classes in an order different than what we specify in our compareTo() method? Good question. As luck would have it, the answer is coming up next.
Sorting with Comparator
While you were looking up the Collections.sort() method you might have noticed that there is an overloaded version of sort() that takes a List, AND something called a Comparator. The Comparator interface gives you the capability to sort a given collection any number of different ways. The other handy thing about the Comparator interface is that you can use it to sort instances of any class—even classes you can't modify—unlike the Comparable interface, which forces you to change the class whose instances you want to sort. The Comparator interface is also very easy to implement, having only one method, compare(). Here's a small class that can be used to sort a List of DVDInfo instances, by genre.
import java.util.*; class GenreSort implements Comparator<DVDInfo> { public int compare(DVDInfo one, DVDInfo two) { return one.getGenre().compareTo(two.getGenre()); } } The Comparator.compare() method returns an int whose meaning is the same as the Comparable.compareTo() method's return value. In this case we're taking advantage of that by asking compareTo() to do the actual comparison work for us. Here's a test program that lets us test both our Comparable code and our new Comparator code:
import java.util.*; import java.io.*; // populateList() needs this public class TestDVD { ArrayList<DVDInfo> dvdlist = new ArrayList<DVDInfo>(); public static void main(String[] args) { new TestDVD().go(); } public void go() { populateList(); System.out.println(dvdlist); // output as read from file Collections.sort(dvdlist); System.out.println(dvdlist); // output sorted by title GenreSort gs = new GenreSort(); Collections.sort(dvdlist, gs) ; System.out.println(dvdlist); // output sorted by genre } public void populateList() { // read the file, create DVDInfo instances, and // populate the ArrayList dvdlist with these instances } } You've already seen the first two output lists, here's the third:
[Patriot Games action Ford, Harrison , Raiders of the Lost Ark action Ford, Harrison , Caddy Shack comedy Murray, Bill , Lost in Translation comedy Murray, Bill , 2001 sci-fi ?? , Donnie Darko sci-fi Gyllenhall, Jake , Star Wars sci-fi Ford, Harrison ]
Because the Comparable and Comparator interfaces are so similar, expect the exam to try to confuse you. For instance you might be asked to implement the compareTo() method in the Comparator interface. Study Table 7-3 to burn in the differences between these two interfaces.
| java.lang.Comparable | java.util.Comparator |
|---|---|
| int objOne.compareTo(objTwo) | int compare(objone, objTwo) |
| Returns negative if obj One < objTwo zero if objOne == objTwo positive if objOne > objTwo | Same as Comparable |
| You must modify the class whose instances you want to sort. | You build a class separate from the class whose instances you want to sort. |
| Only one sort sequence can be created | Many sort sequences can be created |
| Implemented frequently in the API by: String, Wrapper classes, Date, Calendar… | Meant to be implemented to sort instances of third-party classes. |
Sorting with the Arrays Class
We've been using the java.util.Collections class to sort collections; now let's look at using the java.util.Arrays class to sort arrays. The good news is that sorting arrays of objects is just like sorting collections of objects. The Arrays.sort() method is overridden in the same way the Collections.sort() method is.
-
Arrays.sort(arrayToSort)
-
Arrays.sort(arrayToSort, Comparator)
In addition, the Arrays.sort() method is overloaded about a million times to provide a couple of sort methods for every type of primitive. The Arrays.sort() methods that sort primitives always sort based on natural order. Don't be fooled by an exam question that tries to sort a primitive array using a Comparator.
Finally, remember that the sort() methods for both the Collections class and the Arrays class are static methods, and that they alter the objects they are sorting, instead of returning a different sorted object.
|
We've talked a lot about sorting by natural order and using Comparators to sort. The last rule you'll need to burn in is that, whenever you want to sort an array or a collection, the elements inside must all be mutually comparable. In other words, if you have an Object [] and you put Cat and Dog objects into it, you won't be able to sort it. In general, objects of different types should be considered NOT mutually comparable, unless specifically stated otherwise.
|
Searching Arrays and Collections
The Collections class and the Arrays class both provide methods that allow you to search for a specific element. When searching through collections or arrays, the following rules apply:
-
Searches are performed using the binarySearch() method.
-
Successful searches return the int index of the element being searched.
-
Unsuccessful searches return an int index that represents the insertion point. The insertion point is the place in the collection/array where the clement would be inserted to keep the collection/array properly sorted. Because positive return values and 0 indicate successful searches, the binarysearch() method uses negative numbers to indicate insertion points. Since 0 is a valid result for a successful search, the first available insertion point is -1. Therefore, the actual insertion point is represented as (-(insertion point) -1). For instance, if the insertion point of a search is at element 2, the actual insertion point returned will be -3.
-
The collection/array being searched must be sorted before you can search it.
-
If you attempt to search an array or collection that has not already been sorted, the results of the search will not be predictable.
-
If the collection/array you want to search was sorted in natural order, it must be searched in natural order. (This is accomplished by NOT sending a Comparator as an argument to the binarysearch() method.)
-
If the collection/array you want to search was sorted using a Comparator, it must be searched using the same Comparator, which is passed as the second argument to the binarysearch() method. Remember that Comparators cannot be used when searching arrays of primitives.
Let's take a look at a code sample that exercises the binarysearch() method:
import java.util.*; class SearchObjArray { public static void main(String [] args) { String [] sa = {"one", "two", "three", "four"}; Arrays.sort(sa); // #1 for(String s : sa) System.out.print(s + " "}; System.out.println("\none = " + Arrays.binarysearch(sa,"one")); // #2 System.out.println("now reverse sort"); ReSortComparator rs = new ReSortComparator(); // #3 Arrays.sort(sa,rs); for(String s : sa) System.out.print(s + " "); System.out.println("\none = " + Arrays.binarysearch(sa,"one")); // #4 System.out.println("one = " + Arrays.binarysearch(sa,"one",rs)); // #5 } static class ReSortComparator implements Comparator<String> { // #6 public int compare(String a, String b) { return b.compareTo(a); // #7 } } } which produces something like this:
four one three two one = 1 now reverse sort two three one four one = -1 one = 2
Here's what happened:
| Line 1 | Sort the sa array, alphabetically (the natural order). |
| Line 2 | Search for the location of element "one", which is 1. |
| Line 3 | Make a Comparator instance. On the next line we re-sort the array using the Comparator. |
| Line 4 | Attempt to search the array. We didn't pass the binarySearch () method the Comparator we used to sort the array, so we got an incorrect (undefined) answer. |
| Line 5 | Search again, passing the Comparator to binarysearch(). This time we get the correct answer, 2 |
| Line 6 | We define the Comparator; it's okay for this to be an inner class. |
| Line 7 | By switching the use of the arguments in the invocation of compareTo(), we get an inverted sort. |
|
When solving searching and sorting questions, two big gotchas are:
-
Searching an array or collection that hasn't been sorted.
-
Using a Comparator in either the sort or the search, but not both.
|
Converting Arrays to Lists to Arrays
There are a couple of methods that allow you to convert arrays to Lists, and Lists to arrays. The List and Set classes have toArray() methods, and the Arrays class has a method called asList().
The Arrays.asList() method copies an array into a List. The API says, "Returns a fixed-size list backed by the specified array. (Changes to the returned list 'write through' to the array.)" When you use the asList() method, the array and the List become joined at the hip. When you update one of them, the other gets updated automatically. Let's take a look:
String [] sa = {"one", "two", "three", "four"}; List sList = Arrays.asList(sa); // make a List System.out.println("size " + sList.size()); System.out.println("idx2 " + sList.get(2)); sList.set(3,"six"); // change List sa[l] = "five"; // change array for(String s : sa) System.out.print(s + " "); System.out.println("\nsl[1] " + sList.get(1)); This produces
size 4 idx2 three one five three six sl[1] five
Notice that when we print the final state of the array and the List, they have both been updated with each other's changes. Wouldn't something like this behavior make a great exam question?
Now let's take a look at the toArray() method. There's nothing too fancy going on with the toArray() method; it comes in two flavors: one that returns a new Object array, and one that uses the array you send it as the destination array:
List<Integer> iL = new ArrayList<Integer>(); for(int x=0; x<3; x++) iL.add(x); Object[] oa = iL.toArray(); // create an Object array Integer[] ia2 = new Integer[3]; ia2 = iL.toArray(ia2); // create an Integer array
Using Lists
Remember that Lists are usually used to keep things in some kind of order. You can use a LinkedList to create a first-in, first-out queue. You can use an ArrayList to keep track of what locations were visited, and in what order. Notice that in both of these examples it's perfectly reasonable to assume that duplicates might occur. In addition, Lists allow you to manually override the ordering of elements by adding or removing elements via the element's index. Before Java 5, and the enhanced for loop, the most common way to examine a List "element by element" was by the use of an Iterator. You'll still find Iterators in use in the Java code you encounter, and you might just find an Iterator or two on the exam. An Iterator is an object that's associated with a specific collection. It let's you loop through the collection step by step. The two Iterator methods you need to understand for the exam are
-
boolean hasNext() Returns true if there is at least one more element in the collection being traversed. Invoking hasNext() does NOT move you to the next element of the collection.
-
object next() This method returns the next object in the collection, AND moves you forward to the element after the element just returned.
Let's look at a little code that uses a List and an Iterator:
import java.util.*; class Dog { public String name; Dog(String n) { name = n; } } class ItTest { public static void main(String[1 args) { List<Dog> d = new ArrayList<Dog>(); Dog dog = new Dog("aiko"); d.add(dog); d.add(new Dog("clover")); d.add(new Dog("magnolia")); Iterator<Dog> i3 = d.iterator(); // make an iterator while (i3.hasNext()) { Dog d2 = i3.next(); // cast not required System.out.println(d2.name); } System.out.println("size " + d.size()); System.out.println("getl " + d.get(1).name); System.out.println("aiko " + d.indexOf(dog)); d.remove(2) ; Object[] oa = d.toArray(); for(Object o : oa) { Dog d2 = (Dog)o; System.out.println("oa " + d2.name); } } } This produces
aiko clover magnolia size 3 getl clover aiko 0 oa aiko oa clover
First off, we used generics syntax to create the Iterator (an Iterator of type Dog). Because of this, when we used the next() method, we didn't have to cast the Object returned by next() to a Dog. We could have declared the Iterator like this:
Iterator i3 = d.iterator(); // make an iterator
But then we would have had to cast the returned value:
Dog d2 = (Dog)i3.next();
The rest of the code demonstrates using the size(), get(), indexOf(), and toArray() methods. There shouldn't be any surprises with these methods. In a few pages Table 7-5 will list all of the List, Set, and Map methods you should be familiar with for the exam. As a last warning, remember that List is an interface!
Using Sets
Remember that Sets are used when you don't want any duplicates in your collection. If you attempt to add an element to a set that already exists in the set, the duplicate element will not be added, and the add() method will return false. Remember, HashSets tend to be very fast because, as we discussed earlier, they use hashcodes.
You can also create a TrecSet, which is a Set whose elements are sorted. You must use caution when using a TreeSet (we're about to explain why):
import java.util.*; class SetTest { public static void main(String [] args) { boolean[] ba = new boolean[5]; // insert code here ba[0] = s.add("a"); ba[1] = s.add(new Integer(42)); ba[2] = s.add("b") ; ba[3] = s.add("a") ; ba[4] = s.add(new Object()); for(int x=0; x<ba.length; x++) System.out.print(ba[x] + " "); System.out.println("\n"); for(Object o : s) System.out.print(o + " "); } } If you insert the following line of code you'll get output something like this:
Set s = new HashSet(); // insert this code true true true false true a java.lang.Object@e09713 42 b
It's important to know that the order of objects printed in the second for loop is not predictable: HashSets and LinkedHashSets do not guarantee any ordering. Also, notice that the fourth invocation of add() failed, because it attempted to insert a duplicate entry (a String with the value a) into the Set.
If you insert this line of code you'll get something like this:
Set s = new TreeSet(); // insert this code Exception in thread "main" java.lang.ClassCastException: java. lang.String at java.lang.Integer.compareTo(Integer.java:35) at Java.util.TreeMap.compare(TreeMap.java:1093) at java.util.TreeMap.put(TreeMap.java:465) at java.util.TreeSet.add(TreeSet.java:210)
The issue is that whenever you want a collection to be sorted, its elements must be mutually comparable. Remember that unless otherwise specified, objects of different types are not mutually comparable.
Using Maps
Remember that when you use a class that implements Map, any classes that you use as a part of the keys for that map must override the hashCode() and equals() methods. (Well, you only have to override them if you're interested in retrieving stuff from your Map. Seriously, it's legal to use a class that doesn't override equals() and hashCode() as a key in a Map; your code will compile and run, you just won't find your stuff.) Here's some code demonstrating the use of a HashMap:
import java.util.*; class Dog { public Dog(String n) { name = n; } public String name; public boolean equals(Object o) { if( (o instanceof Dog) && (((Dog)o).name == name)) { return true; } else { return false; } } public int hashCode() {return name.length(); } } class Cat { } enum Pets {DOG, CAT, HORSE } class MapTest { public static void main(String[] args) { Map<Object, Object> m = new HashMap<Object, Object>(); m.put("kl", new Dog("aiko")); // add some key/value pairs m.put("k2", Pets.DOG); m.put(Pets.CAT, "CAT key"); Dog d1 = new Dog("clover"); // let's keep this reference m.put(d1, "Dog key"); m.put(new Cat(), "Cat key"); System.out.println(m.get("kl")); // #1 String k2 = "k2"; System.out.println(m.get(k2)); // #2 Pets p = Pets.CAT; System.out.println(m.get(p)); // #3 System.out.println(m.get(dl)); // #4 System.out.println(m.get(new Cat())); // #5 System.out.println(m.size()); // #6 } } which produces something like this:
Dog@1c DOG CAT key Dog key null 5
Let's review the output. The first value retrieved is a Dog object (your value will vary). The second value retrieved is an enum value (DOG). The third value retrieved is a String; note that the key was an enum value. Pop quiz: What's the implication of the fact that we were able to successfully use an enum as a key?
The implication of this is that enums override equals() and hashcode(). And, if you look at the java.lang.Enum class in the API, you will see that, in fact, these methods have been overridden.
The fourth output is a String. The important point about this output is that the key used to retrieve the String was made of a Dog object. The fifth output is null. The important point here is that the get() method failed to find the Cat object that was inserted earlier. (The last line of output confirms that indeed, 5 key/value pairs exist in the Map.) Why didn't we find the Cat key String? Why did it work to use an instance of Dog as a key, when using an instance of Cat as a key failed?
It's easy to see that Dog overrode equals() and hashCode() while Cat didn't.
Let's take a quick look at hashcodes. We used an incredibly simplistic hashcode formula in the Dog class—the hashcode of a Dog object is the length of the instance's name. So in this example the hashcode = 4. Let's compare the following two hashCode() methods:
public int hashCode() {return name.length(); } // #1 public int hashCode() {return 4; } // #2 Time for another pop quiz: Are the preceding two hashcodes legal? Will they successfully retrieve objects from a Map? Which will be faster?
The answer to the first two questions is Yes and Yes. Neither of these hashcodes will be very efficient (in fact they would both be incredibly inefficient), but they are both legal, and they will both work. The answer to the last question is that the first hashcode will be a little bit faster than the second hashcode. In general, the more unique hashcodes a formula creates, the faster the retrieval will be. The first hashcode formula will generate a different code for each name length (for instance the name Robert will generate one hashcode and the name Benchley will generate a different hashcode). The second hashcode formula will always produce the same result, 4, so it will be slower than the first.
Our last Map topic is what happens when an object used as a key has its values changed? If we add two lines of code to the end of the earlier MapTest.main(),
d1.name = "magnolia" System.out.printIn(m.get(d1));
we get something like this:
Dog@4 DOG CAT key Dog key null 5 null
The Dog that was previously found now cannot be found. Because the Dog.name variable is used to create the hashcode, changing the name changed the value of the hashcode. As a final quiz for hashcodes, determine the output for the following lines of code if they're added to the end of MapTest.main():
d1.name = "magnolia"; System.out.println(m.get(dl)); // #1 d1.name = "clover"; System.out.println(m.get(new Dog("clover"))); // #2 dl.name = "arthur"; System.out.println(m.get(new Dog("clover"})); // #3 Remember that the hashcode is equal to the length of the name variable. When you study a problem like this, it can be useful to think of the two stages of retrieval:
-
Use the hashcode() method to find the correct bucket
-
Use the equals() method to find the object in the bucket
In the first call to get(), the hashcode is 8 (magnolia) and it should be 6 (clover), so the retrieval fails at step 1 and we get null. In the second call to get (), the hashcodes are both 6, so step 1 succeeds. Once in the correct bucket (the "length of name = 6" bucket), the equals() method is invoked, and since Dog's equals() method compares names, equals() succeeds, and the output is Dog key. In the third invocation of get(), the hashcode test succeeds, but the equals() test fails because arthur is NOT equal to clover.
In a few pages Table 7-5 will summarize the Map methods you should be familiar with for the exam.
Using the PriorityQueue Class
The last collection class you'll need to understand for the exam is the PriorityQueue. Unlike basic queue structures that are first-in, first-out by default, a PriorityQueue orders its elements using a user-defined priority. The priority can be as simple as natural ordering (in which, for instance, an entry of 1 would be a higher priority than an entry of 2). In addition, a PriorityQueue can be ordered using a Comparator, which lets you define any ordering you want. Queues have a few methods not found in other collection interfaces: peek(), poll(), and offer().
import java.util.*; class PQ { static class PQsort implements Comparator<Integer> { // inverse sort public int compare(Integer one, Integer two) { return two - one; // unboxing } } public static void main(String[] args) { int[] ia= {1,5,3,7,6,9,8}; // unordered data PriorityQueue<Integer> pq1 = new PriorityQueue<Integer>(); // use natural order for(int x : ia) // load queue pq1.offer(x); for(int x : ia) // review queue System.out.print(pql.poll() + " "); System.out.println("") ; PQsort pqs = new PQsort(); // get a Comparator PriorityQueue<Integer> pq2 = new PriorityQueue<Integer>(10,pqs); // use Comparator for(int x : ia) // load queue pq2.offer(x); System.out.println("size " + pq2.size()); System.out.println("peek " + pq2.peek()); System.out.println("size " + pq2.size()); System.out.println("poll " + pq2.poll()); System.out.println("size " + pq2.size()); for(int x : ia) // review queue System.out.print(pql.poll() + " ") ; } } This code produces something like this:
1 3 5 6 7 8 9 size 7 peek 9 size 7 poll 9 size 6 8 7 6 5 3 1 null
Let's look at this in detail. The first for loop iterates through the ia array, and uses the offer() method to add elements to the PriorityQueue named pq1. The second for loop iterates through pq1 using the poll() method, which returns the highest priority entry in pq1 AND removes the entry from the queue. Notice that the elements are returned in priority order (in this case, natural order). Next, we create a Comparator—in this case, a Comparator that orders elements in the opposite of natural order. We use this Comparator to build a second PriorityQueue, pq2, and we load it with the same array we used earlier. Finally, we check the size of pq2 before and after calls to peek() and poll(). This confirms that peek() returns the highest priority element in the queue without removing it, and poll() returns the highest priority element, AND removes it from the queue. Finally, we review the remaining elements in the queue.
Method Overview for Arrays and Collections
For these two classes, we've already covered the trickier methods you might encounter on the exam. Table 7-4 lists a summary of the methods you should be aware of. (Note: The T[] syntax will be explained later in this chapter; for now, think of it as meaning "any array that's NOT an array of primitives.")
Table 7-4: Key Methods in Arrays and Collections
| Key Methods in java.util.Arrays | Descriptions |
|---|---|
| static List asList(T[]) | Convert an array to a List, (and bind them). |
| static int binarySearch(Object [], key) static int binarySearch(primitive [], key) | Search a sorted array for a given value, return an index or insertion point. |
| static int binarySearch(T[], key, Comparator) | Search a Comparator-sorted array for a value. |
| static boolean equals(Object[], Object[] ) static boolean equals(primitive[], primitive[] ) | Compare two arrays to determine if their contents are equal. |
| public static void sort(Object[] ) public static void sort(primitive[] ) | Sort the elements of an array by natural order. |
| public static void sort(T[], Comparator) | Sort the elements of an array using a Comparator. |
| public static String toString(Object[]) public static String toString(primitive[]) | Create a String containing the contents of an array. |
| Key Methods in java.util.Collections | Descriptions |
|---|---|
| static int binarySearch(List, key) static int binarySearch(List, key, Comparator) | Search a "sorted" List for a given value, return an index or insertion point. |
| static void reverse(List) | Reverse the order of elements in a List. |
| static Comparator reverseOder() static Comparator reverseOder(Comparator) | Return a Comparator that sorts the reverse of the collection's current sort sequence. |
| static void sort(List) static void sort(List, Comparator) | Sort a List either by natural order or by a Comparator. |
Method Overview for List, Set, Map, and Queue
For these four interfaces, we've already covered the trickier methods you might encounter on the exam. Table 7-5 lists a summary of the List, Set, and Map methods you should be aware of.
| Key Interface Methods | List | Set | Map | Descriptions |
|---|---|---|---|---|
| boolean add(element) | X | X | Add an element. For Lists, optionally add the element at an index point. | |
| boolean add(index, element) | X | |||
| boolean contains (object) | X | X | Search a collection for an object (or, optionally for Maps a key), return the result as a boolean. | |
| boolean containsKey(object key) | X | |||
| boolean containsValue(object value) | X | |||
| object get(index) | X | Get an object from a collection, via an index or a key. | ||
| object get(key) | X | |||
| int indexOf(object) | X | Get the location of an object in a List. | ||
| Iterator iterator() | X | X | Get the Iterator for a List or a Set. | |
| Set keyset() | X | Return a Set containing a Map's keys. | ||
| put(key, value) | X | Add a key/value pair to a Map. | ||
| remove(index) | X | Remove an element via an index, or via the element's value, or via a key. | ||
| remove(object) | X | X | ||
| remove(key) | X | |||
| int size() | X | X | X | Return the number of elements in a collection. |
| object[] toArray() T[] toArray(T[]) | X | X | Return an array containing the elements of the collection. |
For the exam, the PriorityQueue methods that are important to understand are offer() (which is similar to add()), peek() (which retrieves the element at the head of the queue, but doesn't delete it), and poll() (which retrieves the head element and removes it from the queue).
|
It's important to know some of the details of natural ordering. The following code will help you understand the relative positions of uppercase characters, lowercase characters, and spaces in a natural ordering:
String[] sa = {">ff<", "> f<", ">f <", ">FF<" }; // ordered? PriorityQueue<String> pq3 = new PriorityQueue<String>(); for(String s : sa) pq3.offer(s); for(String s : sa) System.out.print(pq3.poll() + " "); This produces:
> f< >FF< >f < >ff<
If you remember that spaces sort before characters and that uppercase letters sort before lowercase characters, you should be good to go for the exam.
|
EAN: 2147483647
Pages: 131