Quick Review: Chapters 38 to 51

This chapter is going to be the Quick recap/review of the concepts we learnt in the previous chapters on collections.

So, lets get started!!!

Overriding hashCode() and equals()

* equals(), hashCode(), and toString() are public.

* Override toString() so that System.out.println() or other methods can see something useful, like your object’s state.

* Use == to determine if two reference variables refer to the same object.

* Use equals() to determine if two objects are meaningfully equivalent.

* If you don’t override equals(), your objects won’t be useful hashing keys.

* If you don’t override equals(), different objects can’t be considered equal.

* Strings and wrappers override equals() and make good hashing keys.

* When overriding equals(), use the instanceof operator to be sure you’re evaluating an appropriate class.

* When overriding equals(), compare the objects’ significant attributes.

* Highlights of the equals() contract:

      * Reflexive: x.equals(x) is true.

      * Symmetric: If x.equals(y) is true, then y.equals(x) must be true.

      * Transitive: If x.equals(y) is true, and y.equals(z) is true, then z.equals(x) is true.

      * Consistent: Multiple calls to x.equals(y) will return the same result.

      * Null: If x is not null, then x.equals(null) is false.

* If x.equals(y) is true, then x.hashCode() == y.hashCode() is true.

* If you override equals(), override hashCode().

* HashMap, HashSet, Hashtable, LinkedHashMap, & LinkedHashSet use hashing.

* An appropriate hashCode() override sticks to the hashCode() contract.

* An efficient hashCode() override distributes keys evenly across its buckets.

* An overridden equals() must be at least as precise as its hashCode() mate.

* To reiterate: if two objects are equal, their hashcodes must be equal.

* It’s legal for a hashCode() method to return the same value for all instances (although in practice it’s very inefficient).

* Highlights of the hashCode() contract:

      * Consistent: multiple calls to x.hashCode() return the same integer.

      * If x.equals(y) is true, x.hashCode() == y.hashCode() is true.

      * If x.equals(y) is false, then x.hashCode() == y.hashCode() can be either true or false, but false will tend to create better efficiency.

* transient variables aren’t appropriate for equals() and hashCode().

Collections

* Common collection activities include adding objects, removing objects, verifying object inclusion, retrieving objects, and iterating.

* Three meanings for “collection”:

      * collection Represents the data structure in which objects are stored

      * Collection java.util interface from which Set and List extend

      * Collections A class that holds static collection utility methods

      Four basic flavors of collections include Lists, Sets, Maps, Queues:

      * Lists of things Ordered, duplicates allowed, with an index.

      * Sets of things May or may not be ordered and/or sorted; duplicates not allowed.

      * Maps of things with keys May or may not be ordered and/or sorted; duplicate keys are not allowed.

      * Queues of things to process Ordered by FIFO or by priority.

* Four basic sub-flavors of collections Sorted, Unsorted, Ordered, Unordered.

      * Ordered Iterating through a collection in a specific, non-random order.

      * Sorted Iterating through a collection in a sorted order.

* Sorting can be alphabetic, numeric, or programmer-defined.

Key Attributes of Common Collection Classes

* ArrayList: Fast iteration and fast random access.

* Vector: It’s like a slower ArrayList, but it has synchronized methods.

* LinkedList: Good for adding elements to the ends, i.e., stacks and queues.

* HashSet: Fast access, assures no duplicates, provides no ordering.

* LinkedHashSet: No duplicates; iterates by insertion order.

* TreeSet: No duplicates; iterates in sorted order.

* HashMap: Fastest updates (key/values); allows one null key, many null values.

* Hashtable: Like a slower HashMap (as with Vector, due to its synchronized methods). No null values or null keys allowed.

* LinkedHashMap: Faster iterations; iterates by insertion order or last accessed; allows one null key, many null values.

* TreeMap: A sorted map.

* PriorityQueue: A to-do list ordered by the elements’ priority.

Using Collection Classes

* Collections hold only Objects, but primitives can be autoboxed.

* Iterate with the enhanced for, or with an Iterator via hasNext() & next().

* hasNext() determines if more elements exist; the Iterator does NOT move.

* next() returns the next element AND moves the Iterator forward.

* To work correctly, a Map’s keys must override equals() and hashCode().

* Queues use offer() to add an element, poll() to remove the head of the queue, and peek() to look at the head of a queue.

* As of Java 6 TreeSets and TreeMaps have new navigation methods like floor() and higher().

* You can create/extend “backed” sub-copies of TreeSets and TreeMaps.

Sorting and Searching Arrays and Lists

* Sorting can be in natural order, or via a Comparable or many Comparators.

* Implement Comparable using compareTo(); provides only one sort order.

* Create many Comparators to sort a class many ways; implement compare().

* To be sorted and searched, a List’s elements must be comparable.

* To be searched, an array or List must first be sorted.

Utility Classes: Collections and Arrays

* Both of these java.util classes provide

* A sort() method. Sort using a Comparator or sort using natural order.

* A binarySearch() method. Search a pre-sorted array or List.

* Arrays.asList() creates a List from an array and links them together.

* Collections.reverse() reverses the order of elements in a List.

* Collections.reverseOrder() returns a Comparator that sorts in reverse.

* Lists and Sets have a toArray() method to create arrays.

Generics

* Generics let you enforce compile-time type safety on Collections (or other classes and methods declared using generic type parameters).

* An ArrayList< Car > can accept references of type Ferrari, Bmw, or any other subtype of Car

* When using generic collections, a cast is not needed to get (declared type) elements out of the collection. With non-generic collections, a cast is required:
List< String > gList = new ArrayList< String >();
List list = new ArrayList();
// more code
String s = gList.get(0); // no cast needed
String s = (String)list.get(0); // cast required


* You can pass a generic collection into a method that takes a non-generic collection, but the results may be disastrous. The compiler can’t stop the method from inserting the wrong type into the previously type safe collection.

* If the compiler can recognize that non-type-safe code is potentially endangering something you originally declared as type-safe, you will get a compiler warning. For instance, if you pass a List< String > into a method declared as
void foo(List aList) { aList.add(anInteger); }

* You’ll get a warning because add() is potentially “unsafe”.

* “Compiles without error” is not the same as “compiles without warnings.” A compilation warning is not considered a compilation error or failure.

* Generic type information does not exist at runtime—it is for compile-time safety only. Mixing generics with legacy code can create compiled code that may throw an exception at runtime.

* Polymorphic assignments applies only to the base type, not the generic type parameter. You can say
List< Car > aList = new ArrayList< Car >(); // yes

You can’t say
List< Car > aList = new ArrayList< Ferrari >(); // no


* The polymorphic assignment rule applies everywhere an assignment can be made. The following are NOT allowed:
void foo(List< Car > aList) { } // cannot take a List
List< Car > bar() { } // cannot return a List


* Wildcard syntax allows a generic method, accept subtypes (or supertypes) of the declared type of the method argument:
void addD(List< Car > d) {} // can take only < Car >
void addD(List< ? extends Car >) {} // take a < Car > or < Ferrari >


* The wildcard keyword extends is used to mean either “extends” or “implements.” So in , Car can be a class or an interface.

* When using a wildcard, List< ? extends Car >, the collection can be accessed but not modified.

* When using a wildcard, List< ? >, any generic type can be assigned to the reference, but for access only, no modifications.

* List< Object > refers only to a List< Object >, while List< ? > or List< ? extends Object > can hold any type of object, but for access only.

* Declaration conventions for generics use T for type and E for element:
public interface List< E > // API declaration for List
boolean add(E o) // List.add() declaration


* The generics type identifier can be used in class, method, and variable declarations:
class Foo { } // a class
T anInstance; // an instance variable
Foo(T aRef) {} // a constructor argument
void bar(T aRef) {} // a method argument
T baz() {} // a return type

The compiler will substitute the actual type.

* You can use more than one parameterized type in a declaration:
public class UseTwo { }


* You can declare a generic method using a type not defined in the class:
public void makeList(T t) { }

is NOT using T as the return type. This method has a void return type, but to use T within the method’s argument you must declare the , which happens before the return type.


Previous Chapter: Chapter 51 - Generics

Next Chapter: Self Test - Chapters 38 to 51

Chapter 50: Methods Overview for Collections

In the previous few chapters, we have covered details about the different types of collections in great detail. The purpose of this article is to highlight the other methods that these collections have which we havent covered in our previous chapters.

So, lets get started!!!

Important Methods for List, Set and Map

Method Name	Exists in			Description/Purpose
	List	Set	Map
boolean add(element)	Y	Y	-	Add an element.
boolean add(index, element)	Y	-	-	Add the element at an index point.
boolean contains(object)	Y	Y	Y	Search a collection for an object
boolean containsKey(object key)	-	-	Y	Search a Collection for a Key
boolean containsValue(object value)	-	-	Y	Search a Collection for a Value
object get(index)	Y	-	-	Get an Object from a collection using the index position
object get(key)	-	-	Y	Get an object from a Map using the Key
int indexOf(object)	Y	-	-	Get the location of an object in a List.
Iterator iterator()	Y	Y	-	Get an Iterator for a List or a Set.
Set keySet()	-	-	Y	Return a Set containing a Map’s keys.
put(key, value)	-	-	Y	Add a key/value pair to a Map.
remove(index)	Y	-	-	Remove a value at the index
remove(object)	Y	Y	Y	Remove an object from the collection
remove(key)	-	-	Y	Remove an object corresponding to the Key
int size()	Y	Y	Y	Return the number of elements in a collection.
Object[] toArray()	Y	Y	-	Return an array containing the elements of the collection.
A[] toArray(A[])	Y	Y	-	Return an array containing the elements of the collection.

Important Methods for Arrays:

For the purpose of explanation in the table that follows, A[] refers to an Array that contains objects in it.

Method Name	Description/Purpose
static List asList(A[])	Convert an array to a List
static int binarySearch(ObjecA[], key) static int binarySearch(primitive[], key)	Search a sorted array for a given value, return an index or insertion point.
static int binarySearch(A[], key, Comparator)	Search a Comparator-sorted array for a value.
static boolean equals(ObjecA[], ObjecA[]) 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(A[], Comparator)	Sort the elements of an array using a Comparator
public static String toString(ObjecA[]) public static String toString(primitive[])	Create a String containing the contents of an array.

Important Methods for Collections:

Method Name	Description/Purpose
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 int binarySearch(ObjecA[], key) static int binarySearch(primitive[], key)	Search a sorted array for a given value, return an index or insertion point.
static void reverse(List)	Reverse the order of elements in a List..
static Comparator reverseOrder() static Comparator reverseOrder(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.

Previous Chapter: Chapter 49 - Priority Queue

Next Chapter: Chapter 31 - Generics

Chapter 44: Using Lists

We saw what a list is and how useful it is and stuff like that. In this chapter we are going to take a look at how we should use them. So without any further delays, lets get started!!!

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 lets 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 Car {
public String name;
Car(String n) { name = n; }
}
class TestIteratorExample {
public static void main(String[] args) {
List d = new ArrayList();
Car Car = new Car("BMW");
d.add(Car);
d.add(new Car("Ferrari"));
d.add(new Car("Porsche"));
Iterator < car > i3 = d.iterator(); // make an iterator
while (i3.hasNext()) {
Car d2 = i3.next(); // cast not required
System.out.println(d2.name);
}
System.out.println("size " + d.size());
System.out.println("get1 " + d.get(1).name);
System.out.println("BMW " + d.indexOf(Car));
d.remove(2);
Object[] obj = d.toArray();
for(Object o : obj) {
Car d2 = (Car)o;
System.out.println("obj " + d2.name);
}
}
}

This produces
BMW
Ferrari
Porsche
size 3
get1 Ferrari
BMW 0
obj BMW
obj Ferrari

First off, we used generics syntax to create the Iterator (an Iterator of type Car). Because of this, when we used the next() method, we didn’t have to cast the Object returned by next() to a Car. 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:
Car d2 = (Car)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. As a last warning, remember that List is an interface!

Previous Chapter: Chapter 43 - Converting Arrays to List and List to Arrays

Next Chapter: Chapter 45 - Using Sets

Chapter 40: ArrayList Basics

We saw how to create and use Arrays in Chapter . Though Arrays are very efficient, the programmer has to ensure that he keeps the index in mind and has code that will handle the inserts/updates and deletes into the array. Though the previous sentence might sound simple, implementing it in code is not as simple. To help us not go through the ordeal of doing that, the java language creators provide us with the ArrayList. In this chapter we are going to take a look at this all powerful class.

So, lets get started!!!

ArrayLists

The java.util.ArrayList class is one of the most commonly used of all the classes in the Collections Framework. 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 myFirstArrayList = new ArrayList();

As of Java 5 you’ll want to say
List myFirstArrayList = new ArrayList();

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 in future, but for now just know that, as of Java 5, the 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 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

List test = new ArrayList();
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 rechecked 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 using one of the constructors of that type, 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.
Checkout the Wrapping & Boxing chapter by clicking here (If you want to refresh that topic)

List myFirstIntArray = new ArrayList(); // pre Java 5 declaration
myFirstIntArray.add(new Integer(42)); // had to wrap an int

As of Java 5 we can say
myFirstIntArray.add(42); // autoboxing handles it!

In this last example, we are still adding an Integer object to myFirstIntArray (not an int primitive); it’s just that autoboxing handles the wrapping for us.

Previous Chapter: Chapter 39 - Getting Started with Collections

Next Chapter: Chapter 41 - Sorting Collections & Arrays

Chapter 39: Getting Started with Collections

In the previous chapter, we talked about the equals(), toString() and hashCode() methods and said that they would be very useful with collections, but we never saw what these collections are. Well, here we are. This chapter and the subsequent ones will dive deep into the world of collections.

So, let’s get started!!!

Collections

The Collections Framework in Java, which took shape with the release of JDK 1.2 and was expanded in 1.4 and again in Java 5, and yet again in Java 6, gives you lists, sets, maps, and queues to satisfy most of your coding needs. They’ve been tried, tested, and tweaked to offer the best performance. Pick the best one for your job and you’ll get—at the least—reasonable performance. And when you need something a little more custom, the Collections Framework in the java.util package is loaded with interfaces and utilities.

What Do You Do with a Collection?

There are a few basic operations you’ll normally use with collections:
• Add objects to the collection.
• Remove objects from the collection.
• Find out if an object is in the collection.
• Retrieve an object from the collection
• Iterate through the collection, looking at each object one by one.

Now that we know what we can do with a collection, let’s look at more details about them.

Key Classes & Interfaces of the Collections Framework

For the exam you’ll need to know which collection to choose based on a stated requirement. The collections API begins with a group of interfaces, but also gives you a truckload of concrete classes. The core interfaces you need to know for the exam are the following nine:
1. Collection
2. List
3. Queue
4. Set
5. Map
6. NavigableSet
7. SortedSet
8. SortedMap
9. NavigableMap

The core concrete implementation classes you need to know for the exam are the following 13:
1. Maps
     a. HashMap
     b. HashTable
     c. TreeMap
     d. LinkedHashMap
2. Sets
     a. HashSet
     b. LinkedHashSet
     c. TreeSet
3. Lists
     a. ArrayList
     b. Vector
     c. LinkedList
4. Queues
     a. PriorityQueue
5. Utilities
     a. Collections
     b. Arrays

Not all collections in the Collections Framework actually implement the Collection interface. In other words, not all collections pass the IS-A test for Collection. Specifically, none of the Map-related classes and interfaces extend from Collection. So while SortedMap, Hashtable, HashMap, TreeMap, and LinkedHashMap are all thought of as collections, none are actually extended from Collection-with-a-capital-C. To make things a little more confusing, there are really three overloaded uses of the word “collection”:
• collection (lowercase c), which represents any of the data structures in which objects are stored and iterated over.
• Collection (capital C), which is actually the java.util.Collection interface from which Set, List, and Queue extend.
• Collections (capital C and ends with s) is the java.util.Collections class that holds a pile of static utility methods for use with collections.

Exam Tip: You can very easily mistake “Collections” for “Collection”—be careful. Keep in mind that Collections is a class, with static utility methods, while Collection is an interface with declarations of the methods common to most collections including add(), remove(), contains(), size(), and iterator().

Collections come in four basic flavors:

• Lists Lists of things (classes that implement List).
• Sets Unique things (classes that implement Set).
• Maps Things with a unique ID (classes that implement Map).
• Queues Things arranged by the order in which they are to be processed.

But there are sub-flavors within those four flavors of collections:
• Sorted
• Unsorted
• Ordered
• Unordered

An implementation class can be unsorted and unordered, ordered but unsorted, or both ordered and sorted. But an implementation can never be sorted but unordered, because sorting is a specific type of ordering. For example, a HashSet is an unordered, unsorted set, while a LinkedHashSet is an ordered (but not sorted) set that maintains the order in which objects were inserted.

Maybe we should be explicit about the difference between sorted and ordered, but first we have to discuss the idea of iteration. When you think of iteration, you may think of iterating over an array using, say, a for loop to access each element in the array in order ([0], [1], [2], and so on). Iterating through a collection usually means walking through the elements one after another starting from the first element. Sometimes, though, even the concept of first is a little strange—in a Hashtable there really isn’t a notion of first, second, third, and so on. In a Hashtable, the elements are placed in a random order based on the hashcode of the key. But something has to go first when you iterate; thus, when you iterate over a Hashtable, there will indeed be an order. But as far as you can tell, it’s completely arbitrary and can change in apparently random ways as the collection changes.

Ordered

When a collection is ordered, it means you can iterate through the collection in a specific (not-random) order. A Hashtable collection is not ordered. Although the Hashtable itself has internal logic to determine the order (based on hashcodes and the implementation of the collection itself), you won’t find any order when you iterate through the Hashtable. An ArrayList, however, keeps the order established by the elements’ index position (just like an array). LinkedHashSet keeps the order established by insertion, so the last element inserted is the last element in the LinkedHashSet (as opposed to an ArrayList, where you can insert an element at a specific index position). Finally, there are some collections that keep an order referred to as the natural order of the elements, and those collections are then not just ordered, but also sorted. Let’s look at how natural order works for sorted collections.

Sorted

A sorted collection means that the order in the collection is determined according to some rule or rules, known as the sort order. A sort order has nothing to do with when an object was added to the collection, or when was the last time it was accessed, or what “position” it was added at. Sorting is done based on properties of the objects themselves. You put objects into the collection, and the collection will figure out what order to put them in, based on the sort order. A collection that keeps an order (such as any List, which uses insertion order) is not really considered sorted unless it sorts using some kind of sort order. Most commonly, the sort order used is something called the natural order. What does that mean?

You know how to sort alphabetically—A comes before B, X comes before Y, and so on. For a collection of String objects, then, the natural order is alphabetical. For Integer objects, the natural order is by numeric value—1 before 2, and so on. There is no natural order for Objects (Customs ones created by programmers) unless and until the developer who coded the class provides one, through an interface (Comparable) that defines how instances of a class can be compared to one another (does instance a come before b, or does instance b come before a?). If the developer decides that objects should be compared using the value of some instance variable, then a sorted collection will order the objects according to the rules in the class for how to use the instance variable to determine the order. Of course, the class might also inherit a natural order from a superclass rather than define its own order, in some cases.

Aside from natural order as specified by the Comparable interface, it’s also possible to define other, different sort orders using another interface: Comparator. We will discuss how to use both Comparable and Comparator to define sort orders later. But for now, just keep in mind that sort order (including natural order) is not the same as ordering by insertion, access, or index.
Now that we know about ordering and sorting, we’ll look at each of the four interfaces, and we’ll dive into the concrete implementations of those interfaces.

List Interface

A List cares about the index. The one thing that List has that non-lists don’t have is a set of methods related to the index. Those key methods include things like get(int index), indexOf(Object o), add(int index, Object obj), and so on. All three List implementations are ordered by index position—a position that you determine either by setting an object at a specific index or by adding it without specifying position, in which case the object is added to the end. The three List implementations are described in the following sections.

ArrayList

Think of this as a growable array. It gives you fast iteration and fast random access. To state the obvious: it is an ordered collection (by index), but not sorted. You might want to know that as of version 1.4, ArrayList now implements the new RandomAccess interface—a marker interface (meaning it has no methods) that says, “this list supports fast (generally constant time) random access.” Choose this over a LinkedList when you need fast iteration but aren’t as likely to be doing a lot of insertion and deletion.

Vector

Vector is a holdover from the earliest days of Java; Vector and Hashtable were the two original collections, the rest were added with Java 2 versions 1.2 and 1.4. A Vector is basically the same as an ArrayList, but Vector methods are synchronized for thread safety. You’ll normally want to use ArrayList instead of Vector because the synchronized methods add a performance hit you might not need. And if you do need thread safety, there are utility methods in class Collections that can help. Vector is the only class other than ArrayList to implement RandomAccess.

LinkedList

A LinkedList is ordered by index position, like ArrayList, except that the elements are doubly-linked to one another. This linkage gives you new methods (beyond what you get from the List interface) for adding and removing from the beginning or end, which makes it an easy choice for implementing a stack or queue. Keep in mind that a LinkedList may iterate more slowly than an ArrayList, but it’s a good choice when you need fast insertion and deletion. As of Java 5, the LinkedList class has been enhanced to implement the java.util.Queue interface. As such, it now supports the common queue methods: peek(), poll(), and offer().

Set Interface

A Set cares about uniqueness i.e., it doesn’t allow duplicates. Our good friend the equals() method determines whether two objects are identical (in which case only one can be in the set). The three Set implementations are described in the following sections.

HashSet

A HashSet is an unsorted, unordered Set. It uses the hashcode of the object being inserted, so the more efficient your hashCode() implementation the better access performance you’ll get. Use this class when you want a collection with no duplicates and you don’t care about order when you iterate through it.

LinkedHashSet

A LinkedHashSet is an ordered version of HashSet that maintains a doubly-linked List across all elements. Use this class instead of HashSet when you care about the iteration order. When you iterate through a HashSet the order is unpredictable, while a LinkedHashSet lets you iterate through the elements in the order in which they were inserted.

TreeSet

The TreeSet is one of two sorted collections (the other being TreeMap). It uses a Red-Black tree structure (but you knew that), and guarantees that the elements will be in ascending order, according to natural order. Optionally, you can construct a TreeSet with a constructor that lets you give the collection your own rules for what the order should be (rather than relying on the ordering defined by the elements’ class) by using a Comparable or Comparator. As of Java 6, TreeSet implements NavigableSet.

Exam Tip:
When using HashSet or LinkedHashSet, the objects you add to them must override hashCode(). If they don’t override hashCode(), the default Object. hashCode() method will allow multiple objects that you might consider “meaningfully equal” to be added to your “no duplicates allowed” set.

Map Interface

A Map cares about unique identifiers. You map a unique key (the ID) to a specific value, where both the key and the value are, of course, objects. You’re probably quite familiar with Maps since many languages support data structures that use a key/value or name/value pair. The Map implementations let you do things like search for a value based on the key, ask for a collection of just the values, or ask for a collection of just the keys. Like Sets, Maps rely on the equals() method to determine whether two keys are the same or different.

HashMap

The HashMap gives you an unsorted, unordered Map. When you need a Map and you don’t care about the order (when you iterate through it), then HashMap is the way to go; the other maps add a little more overhead. Where the keys land in the Map is based on the key’s hashcode, so, like HashSet, the more efficient your hashCode() implementation, the better access performance you’ll get. HashMap allows one null key and multiple null values in a collection.

HashTable

Like Vector, Hashtable has existed from prehistoric Java times. For fun, don’t forget to note the naming inconsistency: HashMap vs. Hashtable. Where’s the capitalization of t? Oh well, you won’t be expected to spell it. Anyway, just as Vector is a synchronized counterpart to the sleeker, more modern ArrayList, Hashtable is the synchronized counterpart to HashMap. Remember that you don’t synchronize a class, so when we say that Vector and Hashtable are synchronized, we just mean that the key methods of the class are synchronized. Another difference, though, is that while HashMap lets you have null values as well as one null key, a Hashtable doesn’t let you have anything that’s null.

LinkedHashMap

Like its Set counterpart, LinkedHashSet, the LinkedHash-Map collection maintains insertion order (or, optionally, access order). Although it will be somewhat slower than HashMap for adding and removing elements, you can expect faster iteration with a LinkedHashMap.

TreeMap

You can probably guess by now that a TreeMap is a sorted Map. And you already know that by default, this means “sorted by the natural order of the elements.” Like TreeSet, TreeMap lets you define a custom sort order (via a Comparable or Comparator) when you construct a TreeMap, that specifies how the elements should be compared to one another when they’re being ordered. As of Java 6, TreeMap implements NavigableMap.

Queue Interface

A Queue is designed to hold a list of “to-dos,” or things to be processed in some way. Although other orders are possible, queues are typically thought of as FIFO (first-in, first-out). Queues support all of the standard Collection methods and they also add methods to add and subtract elements and review queue elements.

PriorityQueue

This class is new with Java 5. Since the LinkedList class has been enhanced to implement the Queue interface, basic queues can be handled with a LinkedList. The purpose of a PriorityQueue is to create a “priority-in, priority out” queue as opposed to a typical FIFO queue. A PriorityQueue’s elements are ordered either by natural ordering (in which case the elements that are sorted first will be accessed first) or according to a Comparator. In either case, the elements’ ordering represents their relative priority.

Exam Tip: You can easily eliminate some answers right away if you recognize that, for example, a Map can’t be the class to choose when you need a name/value pair collection, since Map is an interface and not a concrete implementation class. The wording on the exam is explicit when it matters, so if you’re asked to choose an interface, choose an interface rather than a class that implements that interface. The reverse is also true—if you’re asked to choose a class, don’t choose an interface type.

Exam Tip: For the exam, you might be expected to choose a collection based on a particular requirement, where that need is expressed as a scenario. For example, which collection would you use if you needed to maintain and search on a list of parts, identified by their unique alphanumeric serial number where the part would be of type Part? Would you change your answer at all if we modified the requirement such that you also need to be able to print out the parts in order, by their serial number? For the first question, you can see that since you have a Part class, but need to search for the objects based on a serial number, you need a Map. The key will be the serial number as a String, and the value will be the Part instance. The default choice should be HashMap, the quickest Map for access. But now when we amend the requirement to include getting the parts in order of their serial number, then we need a TreeMap—which maintains the natural order of the keys. Since the key is a String, the natural order for a String will be a standard alphabetical sort. If the requirement had been to keep track of which part was last accessed, then we’d probably need a LinkedHashMap. But since a LinkedHashMap loses the natural order (replacing it with last-accessed order), if we need to list the parts by serial number, we’ll have to explicitly sort the collection, using a utility method

Previous Chapter: Chapter 38 - Overriding toString(), hashCode() and equals() Methods

Next Chapter: ArrayList Basics