Containers in Depth

---

Full container taxonomy

• You can usually ignore any class that begins with "Abstract."

Filling containers

• This fill( ) just duplicates a single object reference throughout the container. In addition, it only works for List objects.
• The fill( ) method is made even less useful by the fact that it can only replace elements that are already in the List and will not add new elements.

A Generator solution

• Virtually all Collection subtypes have a constructor that takes another Collection object, from which it can fill the new container.
• A LinkedHashSet maintains a linked list holding the insertion order.

Using Abstract classes

• Each java.util container has its own Abstract class that provides a partial implementation of that container, so all you must do is implement the necessary methods in order to produce the desired container.
• You use a flyweight when the ordinary solution requires too many objects, or when producing normal objects takes up too much space.

Collection functionality

• There’s no get( ) method for random-access element selection.
• Thus, if you want to examine the elements of a Collection, you must use an iterator.

Optional operations

• The implementing class is not required to provide functioning definitions for these methods.
• An "optional" operation says that calling some methods will nor perform meaningful behavior.
• If an operation is optional, the compiler still restricts you to calling only the methods in that interface.
• Unsupported operations are a special case that can be delayed until necessary.
• The design does provide a "back door" if you want to create a new Collection without providing meaningful definitions for all the methods in the Collection interface, and yet still fit it into the existing library.

Unsupported operations

• Because Arrays.asList( ) produces a List that is backed by a fixed-size array, it makes sense that the only supported operations are the ones that don’t change the size of the array.
• Arrays.asList( ) returns a fixed-sized List, whereas Collections.unmodifiableList( ) produces a list that cannot be changed.

Sets and storage order

• A Set needs a way to maintain storage order.
• Different Set implementations not only have different behaviors, they have different requirements for the type of object that you can put into a particular Set.
• In the absence of other constraints, HashSet should be your default choice because it is optimized for speed.
• The HashSet keeps the elements in some mysterious order.
• The LinkedHashSet keeps the elements in the order in which they were inserted.
• The TreeSet maintains the elements in sorted order.
• The only reliable way to ensure the correctness of such a program is to incorporate unit tests into your build system.

SortedSet

• Note that SortedSet means "sorted according to the comparison function of the object," not "insertion order."

Queues

• With the exception of the priority queues, a Queue will produce elements in exactly the same order as they are placed in the Queue.
• There are methods in LinkedList that support deque operations, but there is no explicit interface for a deque in the Java standard libraries.
• You can create a Deque class using composition, and simply expose the relevant methods from LinkedList.

Understanding Maps

• The standard Java library contains different basic implementations of Maps: HashMap, TreeMap, LinkedHashMap, WeakHashMap, ConcurrentHashMap, and IdentityHashMap.
• The number of implementations of the Map interface should tell you something about the importance of this tool.
• The keys are guaranteed to be in sorted order in SortedMap.
• A LinkedHashMap can be configured in the constructor to use a leastrecently- used (LRU) algorithm based on accesses, so elements that haven’t been accessed (and thus are candidates for removal) appear at the front of the list.

Performance

• Instead of a slow search for the key, it uses a special value called a hash code.
• In the absence of other constraints, HashMap should be your default choice because it is optimized for speed.
• Note that keys must be unique, but values may contain duplicates.

Hashing and hash codes

• It is Object’s hashCode( ) method that is used to generate the hash code for each object. By default this just uses the address of its object.
• equals( ) is used by the HashMap when trying to determine if your key is equal to any of the keys in the table.
• The default Object.equals( ) simply compares object addresses.
• To use your own classes as keys in a HashMap, you must override both hashCode( ) and equals( ).
• The hashCode( ) is not required to return a unique identifier.

Hashing for speed

• One of the solutions to the problem is to keep the keys sorted and then use Collections.binarySearch( ) to perform the lookup.
• From the key object, a number will be derived that will index into the array.
• To solve the problem of the fixed-size array, more than one key may produce the same index.
• It doesn’t matter how big the array is; any key object’s hash code will land somewhere in that array.
• If you could guarantee that there were no collisions (which is possible if you have a fixed number of values), then you’d have a perfect hashing junction, but that’s a special case.
• Instead of searching through the entire list, you quickly jump to a slot where you only have to compare a few entries to find the value.

Overriding hashCode()

• You don’t control the creation of the actual value that’s used to index into the array of buckets.
• Regardless of when hashCode( ) is called, it produces the same value for a particular object every time it is called.
• You’ll want to use information in the object that identifies the object in a meaningful way.
• It makes sense that the hashCode( ) produced by two separate instances of the String "hello" should be identical.
• For a hashCode( ) to be effective, it must be fast and it must be meaningful; that is, it must generate a value based on the contents of the object.
• A good hashCode( ) should result in an even distribution of values.
• Writing a proper hashCode( ) and equals( ) for a new class can be tricky.

Choosing an implementation

• The distinction between containers often comes down to what they are "backed by"—that is, the data structures that physically implement the desired interface.
• You choose the implementation based on the behavior you need.
• One way to look at the differences between container implementations is with a performance test.

Choosing between Lists

• Clearly, linked lists are not a good choice if you will be performing many random accesses.
• An ArrayList must create space and copy all its references forward during an insertion. This becomes expensive as the ArrayList gets bigger.
• The output that the cost of insertion and removal in a LinkedList is quite cheap and doesn’t vary with the list size, but with an ArrayList, insertions especially are very expensive, and the cost increases with list size.
• The best approach is probably to choose an ArrayList as your default and to change to a LinkedList if you need its extra functionality or you discover performance problems due to many insertions and removals from the middle of the list.
• If you are working with a fixed-sized group of elements, either use a List backed by an array (as produced by Arrays.asList( )), or if necessary, an actual array.

Microbenchmarking dangers

• When writing so-called microbenchmarks, you must be careful not to assume too much, and to narrow your tests so that as much as possible they are only timing the items of interest.
• You should not be so concerned with absolute numbers as with the performance comparisons between one type of container and another.

Choosing between Sets

• The performance of HashSet is generally superior to TreeSet, but especially when adding elements and looking them up, which are the two most important operations.
• TreeSet exists because it maintains its elements in sorted order, so you use it only when you need a sorted Set.

Choosing between Maps

• Insertions for all the Map implementations except for IdentityHashMap get significantly slower as the size of the Map gets large.
• lookup is much cheaper than insertion.
• A TreeMap is a way to create an ordered list.
• When you’re using a Map, your first choice should be HashMap, and only if you need a constantly sorted Map will you need TreeMap.

HashMap performance factors

• HashMap and HashSet have constructors that allow you to specify the load factor.
• When this load factor is reached, the container will automatically increase the capacity (the number of buckets) by roughly doubling it and will redistribute the existing objects into the new set of buckets (this is called rehashing).
• The default load factor used by HashMap is 0.75.
• A higher load factor decreases the space required by the table but increases the lookup cost.

Utilities

• Use a ListIterator to trim off the last elements.
• If you sort using a Comparator, you must binarySearch( ) using the same Comparator.
• The Collections class allows you to do this by passing the original container into a method that hands back a read-only version.
• You must fill the container with meaningful data before you make it read-only.
• Once it is loaded, the best approach is to replace the existing reference with the reference that is produced by the "unmodifiable" call.
• The Collections class contains a way to automatically synchronize an entire container.
• It is best to immediately pass the new container through the appropriate "synchronized" method.
• The Java containers library uses a fail-fast mechanism that looks for any changes to the container other than the ones your process is personally responsible for.

Holding references

• There are three classes inherited from the abstract class Reference: SoftReference, WeakReference, and PhantomReference.
• You have an ordinary reference on the stack that goes right to the object, but you might also have a reference to an object that has a reference to the object in question.
• If an object isn’t reachable, there’s no way for your program to use it, so it’s safe to garbage collect that object.
• If the garbage collector discovers that an object is reachable through an ordinary reference, it will not release that object.
• In the order of SoftReference, WeakReference, and PhantomReference, each one is "weaker" than the last and corresponds to a different level of reachability.

The WeakHashMap

• In such a mapping, you are saving storage by creating only one instance of a particular value. When the program needs that value, it looks up the existing object in the mapping and uses that.

Java 1.0/1.1 containers

• Although you should never use the old containers when writing new code, you’ll still need to be aware of them.

Vector & Enumeration

• Even though you should always use Iterator when you can in your own code, you must be prepared for libraries that want to hand you an Enumeration.

HashTable

• There’s no reason to use Hashtable instead of HashMap in new code.

Stack

• It has all of the characteristics and behaviors of a Vector plus some extra Stack behaviors.
• By virtue of inheritance, a Stack is a Vector. Thus, all operations that can be performed on a Vector can also be performed on a Stack.

BitSet

• You’re better off creating your own class, or just an array, to hold your flags if size is an issue.
• An EnumSet is usually a better choice than a BitSet if you have a fixed set of flags that you can name.