Welcome!

Java Authors: Liz McMillan, Elizabeth White, Torben Andersen, Patrick Carey, Srinivasan Sundara Rajan

Related Topics: Java

Java: Article

Java Collections

Managing collections

As Jason Bell pointed out in his editorial "A Modern Day Cinderella" (JDJ, Vol. 8, issue 9), the spotlight is on J2EE and as a result many programmers are ignoring the foundation of the JDK. J2SE is the Java equivalent of C/C++ standard libraries. Here we deal with the lower-level entities, like the Number types, Integer, Long, Float, and Double.

The Java Collections Framework (JCF) should be your first choice when faced with the task of managing any type of collection. The Collections API is one of the most useful parts of the JDK. Looking back at the projects I've worked on over the past 13 years, to some degree all of them involved managing collections of data structures.

In this article I'll review the collections architecture. I'll also point out some of the useful features of the collections API (sorting and searching). To begin I'll go over the class categories, followed by a more detailed explanation of each. I encourage you to review Sun's documentation at http://java.sun.com/products/jdk/1.2/docs/guide/collections/reference.html.

There are explicit class categories in the Collections Framework. The J2SE Collections Framework consists of interfaces, abstract base classes, and concrete implementations that provide a rich set of functionality for us. The implementations are the classes your application should be utilizing behind the scenes. There are implementations based on maps and others that are backed by arrays. You can make your collection read-only or you can add support for multithreaded access. How is a programmer to decide which entity to use? There are two main criteria: thread safety and usage semantics.

Usage semantics can be further broken down into collection- or map-based access. The library makes a distinction. The Map interface is not related to any of the Collection interfaces, because its main purpose in life is to map a key to an object, while the collection is just a loosely associated group of objects.

Interfaces
Figure 1 provides a class diagram showing the interfaces that make up the Collections API. The interfaces represent the ideal types you should be passing around in your application.

 

I strongly urge you to expose only the interfaces to clients of your classes. If you don't do this and instead pass around references to the concrete implementations, your code will become brittle due to the number of changes required to swap out one interface implementation for another. You should strive to expose the most general interface. For example, if a method is to return an ArrayList, first look and see if the methods exposed by the Collection interface will meet the needs of the intended usage (see Table 1). By doing this, you give yourself the opportunity to modify your method to return a LinkedList or any other type supporting the Collection interface. Who knows? You may even want to provide your own implementation of a Balanced Tree, and if you are instantiating and passing around references to a TreeMap, you'll have to alter the code at each reference.

 

Sets
The semantics of Sets are close to those of Lists. However, Sets lack the notion of direct random access. A Set is just a collection of objects that you may iterate over. A useful feature of Sets is that they do not allow duplicates as long as you override hashCode() and equals() from Object. Listings 1-3 provide a short program that will illustrate this effect. There is the main HashSetExample and two Person classes: one that does not override Object.equals()/hashCode() and one that does.

Running this program produces the follow output.

[000-11-1111, 222-23-1234, 000-11-1111]
[000-11-1111, 222-23-1234]

To remove duplicates your classes must override equals() from java.lang.Object. According to the Javadoc, overriding Object.hashCode() has more to do with performance. Interestingly, Sun's "Introduction to the Collections Framework Short Course" mentions overriding only the Object.hashCode(). Beware that if you follow the tutorial to the letter, you'll still have duplicate entries. You must override Object.equals(), as I've done in Listing 2, to prevent duplicates in your Sets.

How about sorting this list? TreeSet can do that for us, but we still have a choice to make. Will we be sorting by the natural order or do we want an ad hoc sort? For this article we'll examine the ad hoc sort (to implement your own natural order, your class should implement the Comparable interface). We can achieve an arbitrary sort order by utilizing the Comparator interface. When we employ a comparator, it's passed to the sorting object. First, we need to create our sorting algorithm (see Listing 4).

Now we can give this algorithm to the other implementation of Set; TreeSet. We add the following code to our main method at line 29 in Listing 4.

29
30 Set sortedSet =
31 new TreeSet
32 (new PersonComparator());
33
34 sortedSet.addAll(set);
35
36 // sorted
37 System.out.println(sortedSet);

Now the output becomes:

[000-11-1111, 222-23-1234, 000-11-1111]
[000-11-1111, 222-23-1234]
[222-23-1234, 000-11-1111]

Cool, eh? I won't go over this for each implementation. You should be able to apply this concept to any of the other sorting containers or utility methods (from Arrays or Collections). It's worth pointing out that even if you don't override either method, the TreeSet will use the Comparator and eliminate duplicates in the sorted set. Figure 2 provides a class diagram for the Set category.

 

The LinkedHashSet is a special implementation of HashSet that supports list operations without directly implementing the List interface. LinkedHashSet will maintain the insertion order of the list elements, yet still allow you to access elements via a key, such as a traditional Map. And, as the name implies, it is a Set that supports all of Set's operations.

Lists
Collection's other category is List; the implementations are ArrayList and LinkedList (see Figure 3).

 

The List interface supports the notion of direct index-based access to the entries, allows duplicates, and defines an order. Direct index-based access is realized via the get(int) method, which accepts an index as the only argument. You may even acquire a subset of the List by specifying a "from index" and a "to index", the semantics of which closely follow that of String. The element at "from index" will be included in the sublist while the element at "to index" will not.

ArrayList should be preferred if you don't require the ability to insert elements into the middle of the List (you're always adding to the end of the List) and you require random access to the elements. However, if you need to insert elements into the List and sequential access is your main concern, then LinkedList will be better.

Maps
Finally, we get to the Map category (see Figure 4). As mentioned earlier, Map is not related to any of the Collection classes. This is because the JCF authors wanted to make a clear distinction between Collections and Maps. The most notable difference is that Maps do not support index-based access semantics. What is the nth element of a Map?

 

If a Map is a Collection, what are the elements? The only reasonable answer is "Key-value pairs," but this provides a very limited (and not particularly useful) Map abstraction. You can't ask what value a given key maps to, nor can you delete the entry for a given key without knowing what value it maps to.

The workhorse of this category is HashMap. For inserting, deleting, and accessing elements, HashMap offers the best implementation. TreeMap is the sorted version and offers the ability to traverse the contents of the Map in a determined order.

As with the HashSet earlier, HashMap will require you to override Object.equals() and have a defined Object.hashCode() implementation on your own classes. And, of course, the objects you place in TreeMap should be comparable [or you must use the TreeMap(Comparator) constructor].

As with Sets, there's a special implementation of Map that supports a List-like view. LinkedHashMap provides for the same deterministic ordering as LinkedHashSet and supports all Map operations.

There's a another specialized implementation of Map, WeakHashMap, that uses weak references. By employing WeakReference, the garbage collector is able to destroy objects despite the Map's reference. If no other thread holds a reference to a key in the WeakHashMap, the garbage collector is free to collect the key-value pair.

Abstractions
The framework offers several opportunities for creating your own collection classes. The abstractions are for those instances where you want a more application-specific collection. There are several abstract classes implementing the interfaces with enough basic functionality to make your task less painful (see Figure 5).

 

In general, you won't be extending these classes unless you want to try some new algorithm or storage technique. Most likely you should turn your attention to the wrapper classes as implemented by the Collections class. Using the Decorator pattern, as these classes do, you may create highly specialized versions of the containers. There's an excellent example in the group of classes created by Piet Jonas for detecting type errors. Using Piet's classes, it's possible to have an exception thrown if an incorrect type is inserted into a collection. These classes employ the exact same design as the specialized wrappers available in the synchronization and read-only methods that I'll discuss next.

java.util.Collections API
Did you know that many of the Vector's methods are declared with the synchronized modifier? Are you aware of the cost of synchronization? While there have been advancements in many JVMs, there is still a slight overhead incurred with synchronization.

Unless several different threads might access your collection, forget about any of the thread-safe implementations. Use one of the nonthread-safe implementations, like ArrayList or HashMap. If you need index-based access, use the ArrayList. If you are more concerned about key-based access, use the HashMap.

While I may mention Vector and Hashtable from time to time, you should be aware that these two classes are now referred to as legacy code. The API has been reworked of late and all of the collection APIs are now unsynchronized. Special synchronized wrappers have been implemented (and hidden from us) for creating polymorphic, thread-safe implementations of the unsynchronized classes. You gain access to these thread-safe versions via static methods on the Collections class.

Collection Collections.synchronizedCollection(Collection);
List Collections.synchronizedList(List);
Map Collections.synchronizedMap(Map);
Set Collections.synchronizedSet(Set);
SortedMap Collections.synchronizedSortedMap(SortedMap);
SortedSet Collections.synchronizedSortedSet(SortedSet);

Notice that all of these methods accept the most general interface and return the same interface. If you make judicious use of these generalities, you'll be able to swap out implementations relatively painlessly. Now keep in mind that in theory, the implementation of collections shall be free to do whatever it wants. You don't want your code dependent upon J2SE source. If you insist on using the concrete classes, you'll have to downcast to use the results from the previous methods. Downcasting requires knowledge of implementation. Things will change over time. Try to insulate yourself from potential change points. The entire Collections Framework wreaks polymorphism, so take advantage of it, as polymorphism is a good thing.

I performed a small test to compare ArrayList, SynchronizedList, and Vector, all three of which implement the List interface. The results show that for synchronized updates, Vector is the worst performer, while SynchronizedList is much faster. Both are compared to the unsynchronized ArrayList. The test involved completing a read (get) or write (add) operation in a tight loop, 100,000 times (see Table 2).

 

Comparing Vector to SynchronizedList shows that Vector takes 138% and 40% more time than the same operations on SynchronizedList. Meanwhile, SynchronizedList takes a 12% hit over ArrayList for read operations, compared to the 167% increase for Vectors. Some people might be confused by the lack of symmetry in the numbers. If we want to compare A to B, the proper equation is (A - B)/B. Therefore if I want to compare 2 to 6, then (2 - 6)/6 gives -0.6667 or -66%. If I compare 6 to 2, then (6 - 2)/2 gives 2 or 200%. This may seem counterintuitive to saying 6 is three times as large as 2 (which is just a simple ratio, not a comparison).

All of the collections support iterator semantics. Some will bark at you if the underlying collection is altered while you are accessing the iterator by throwing a ConcurrentModification exception.

The static class Collections has many other useful methods for converting to and from certain types of collections. Of interest are those dealing with the creation of unmodifiable collections. First you create your collection and then pass it into the appropriate method and your collection is transformed into something that looks just like the original, but now it will throw an exception if anyone attempts to add or delete an object. Inner classes in Collections that simply extend the standard collection class and override the modifiers accomplish this. Now you can implement the Command pattern and employ the concept of read-only parameters and return structures. In a language that deals exclusively with object references, that's a nice-to-have feature.

List Collections.unmodifiableList(List);
Map Collections.unmodifiableMap(Map);
Set Collections.unmodifiableSet(Set);
SortedMap Collections.unmodifiableSortedMap(SortedMap);
SortedSet Collections.unmodifiableSortedSet(SortedSet);

Sorting has been taken care of with a "tuned" implementation of Merge Sort. There are routines for sorting primitives and objects. You can implement classes that have a natural order by extending Comparable. If inheritance is at a premium, use the Comparator interface. C++ programmers will feel right at home with this idiom from the STL. There are even collections that are themselves sorted. SortedTree allows you to add objects that will be sorted on the fly. The API is so flexible that you can implement the natural order.

Other utility methods in collections have to do with searching a List. The Collections class offers two binary searching methods.

Object Collections.binarySearch(List list, Object key);
Object Collections.binarySearch(List list, Object key, Comparator comparator);

These two methods, one of which employs the natural sort order of the list and the other the ad hoc, run in log(n) time where n is the number of elements in the list. However, this is true only if the list passed in implements the RandomAccess interface. Otherwise, if the list does not implement RandomAccess and is large, the search will execute an iterator-based binary search, which according to the Javadoc will "perform O(n) link traversals and O(log n) element comparisons."

Figure 6 shows the big picture with the preferred extension points highlighted. We've discussed the general categories: Collection (Set, List) and Map. We've played around a little and have seen that to take full advantage of some collections, we have to override Object.equals and Object.hashCode. Also, we went over some of the performance tradeoffs of a couple of implementations. I should mention that there are other Collection APIs available to Java programmers. There's the popular JGL and the JDSL. I haven't looked at the JGL but I have played around with the academic version of the JDSL. The JDSL gives you all those nifty data structures you talked about in your junior year algorithms class.

 

There are some new collections available in the latest JCF: LinkedHashSet, LinkedHashMap, and IdentityHashMap. In general they are highly specialized versions of the core JCF classes.

Conclusion
This article should prompt you to take another look at the Collections Framework and, if you are lucky, you'll see something that fits with your current development task. If you are really lucky, perhaps you'll see something else in the J2SE libraries that you never knew existed, collection related or not. Unfortunately, there doesn't seem to be any J2SE champion at Sun, so you'll have to make an effort to scan through the API's Javadoc every so often and perhaps even the source code as well (there are some novel snippets in there).

More Stories By David McReynolds

David McReynolds has been programming for over 12 years and is currently employed by Daugherty Business Solutions as a consultant. He has an MS in computer science from Southern Polytechnic State University.

Comments (6) View Comments

Share your thoughts on this story.

Add your comment
You must be signed in to add a comment. Sign-in | Register

In accordance with our Comment Policy, we encourage comments that are on topic, relevant and to-the-point. We will remove comments that include profanity, personal attacks, racial slurs, threats of violence, or other inappropriate material that violates our Terms and Conditions, and will block users who make repeated violations. We ask all readers to expect diversity of opinion and to treat one another with dignity and respect.


Most Recent Comments
Abelardo 02/20/04 01:36:24 PM EST

I would like to nominate this article for the "best of the year"

David McReynolds 02/13/04 12:53:04 PM EST

Thanks Bill. I know I ran the code so perhaps I missed it during the cut-and-paste operation.

Bill Sommers 02/12/04 01:32:56 PM EST

This is a very nice article. I did find what appears to be an error in the source code. The Person class is missing a getSSN() method. I fixed the problem by writing this method:

public Object getSSN() {
return this.toString();
}

Troll Fiddler 02/10/04 05:13:27 AM EST

Superbly written with lovely clear diagrams. Good work. Not many authors explain things this well.

As Einstein said "if you can''t explain your work to a 10 year old, you''re a charlatan." This author is no charlatan.

Bee 02/05/04 03:07:11 PM EST

Ditto! what Shilpi said,This author is very well organized and excelent detail!

shilpi 02/05/04 03:00:42 PM EST

One of the most articulate and intelligent publishings I have read in a long time. I look forward to reading and hearing more from this author.

@ThingsExpo Stories
“In the past year we've seen a lot of stabilization of WebRTC. You can now use it in production with a far greater degree of certainty. A lot of the real developments in the past year have been in things like the data channel, which will enable a whole new type of application," explained Peter Dunkley, Technical Director at Acision, in this SYS-CON.tv interview at @ThingsExpo, held Nov 4–6, 2014, at the Santa Clara Convention Center in Santa Clara, CA.
SYS-CON Events announced today that IDenticard will exhibit at SYS-CON's 16th International Cloud Expo®, which will take place on June 9-11, 2015, at the Javits Center in New York City, NY. IDenticard™ is the security division of Brady Corp (NYSE: BRC), a $1.5 billion manufacturer of identification products. We have small-company values with the strength and stability of a major corporation. IDenticard offers local sales, support and service to our customers across the United States and Canada. Our partner network encompasses some 300 of the world's leading systems integrators and security s...
The BPM world is going through some evolution or changes where traditional business process management solutions really have nowhere to go in terms of development of the road map. In this demo at 15th Cloud Expo, Kyle Hansen, Director of Professional Services at AgilePoint, shows AgilePoint’s unique approach to dealing with this market circumstance by developing a rapid application composition or development framework.
The major cloud platforms defy a simple, side-by-side analysis. Each of the major IaaS public-cloud platforms offers their own unique strengths and functionality. Options for on-site private cloud are diverse as well, and must be designed and deployed while taking existing legacy architecture and infrastructure into account. Then the reality is that most enterprises are embarking on a hybrid cloud strategy and programs. In this Power Panel at 15th Cloud Expo (http://www.CloudComputingExpo.com), moderated by Ashar Baig, Research Director, Cloud, at Gigaom Research, Nate Gordon, Director of T...
"BSQUARE is in the business of selling software solutions for smart connected devices. It's obvious that IoT has moved from being a technology to being a fundamental part of business, and in the last 18 months people have said let's figure out how to do it and let's put some focus on it, " explained Dave Wagstaff, VP & Chief Architect, at BSQUARE Corporation, in this SYS-CON.tv interview at @ThingsExpo, held Nov 4-6, 2014, at the Santa Clara Convention Center in Santa Clara, CA.
SYS-CON Events announced today that Windstream, a leading provider of advanced network and cloud communications, has been named “Silver Sponsor” of SYS-CON's 16th International Cloud Expo®, which will take place on June 9–11, 2015, at the Javits Center in New York, NY. Windstream (Nasdaq: WIN), a FORTUNE 500 and S&P 500 company, is a leading provider of advanced network communications, including cloud computing and managed services, to businesses nationwide. The company also offers broadband, phone and digital TV services to consumers primarily in rural areas.
The Internet of Things is not new. Historically, smart businesses have used its basic concept of leveraging data to drive better decision making and have capitalized on those insights to realize additional revenue opportunities. So, what has changed to make the Internet of Things one of the hottest topics in tech? In his session at @ThingsExpo, Chris Gray, Director, Embedded and Internet of Things, discussed the underlying factors that are driving the economics of intelligent systems. Discover how hardware commoditization, the ubiquitous nature of connectivity, and the emergence of Big Data a...

ARMONK, N.Y., Nov. 20, 2014 /PRNewswire/ --  IBM (NYSE: IBM) today announced that it is bringing a greater level of control, security and flexibility to cloud-based application development and delivery with a single-tenant version of Bluemix, IBM's platform-as-a-service. The new platform enables developers to build ap...

DevOps Summit 2015 New York, co-located with the 16th International Cloud Expo - to be held June 9-11, 2015, at the Javits Center in New York City, NY - announces that it is now accepting Keynote Proposals. The widespread success of cloud computing is driving the DevOps revolution in enterprise IT. Now as never before, development teams must communicate and collaborate in a dynamic, 24/7/365 environment. There is no time to wait for long development cycles that produce software that is obsolete at launch. DevOps may be disruptive, but it is essential.
"People are a lot more knowledgeable about APIs now. There are two types of people who work with APIs - IT people who want to use APIs for something internal and the product managers who want to do something outside APIs for people to connect to them," explained Roberto Medrano, Executive Vice President at SOA Software, in this SYS-CON.tv interview at Cloud Expo, held Nov 4–6, 2014, at the Santa Clara Convention Center in Santa Clara, CA.
Nigeria has the largest economy in Africa, at more than US$500 billion, and ranks 23rd in the world. A recent re-evaluation of Nigeria's true economic size doubled the previous estimate, and brought it well ahead of South Africa, which is a member (unlike Nigeria) of the G20 club for political as well as economic reasons. Nigeria's economy can be said to be quite diverse from one point of view, but heavily dependent on oil and gas at the same time. Oil and natural gas account for about 15% of Nigera's overall economy, but traditionally represent more than 90% of the country's exports and as...
The Internet of Things is a misnomer. That implies that everything is on the Internet, and that simply should not be - especially for things that are blurring the line between medical devices that stimulate like a pacemaker and quantified self-sensors like a pedometer or pulse tracker. The mesh of things that we manage must be segmented into zones of trust for sensing data, transmitting data, receiving command and control administrative changes, and peer-to-peer mesh messaging. In his session at @ThingsExpo, Ryan Bagnulo, Solution Architect / Software Engineer at SOA Software, focused on desi...
"At our booth we are showing how to provide trust in the Internet of Things. Trust is where everything starts to become secure and trustworthy. Now with the scaling of the Internet of Things it becomes an interesting question – I've heard numbers from 200 billion devices next year up to a trillion in the next 10 to 15 years," explained Johannes Lintzen, Vice President of Sales at Utimaco, in this SYS-CON.tv interview at @ThingsExpo, held Nov 4–6, 2014, at the Santa Clara Convention Center in Santa Clara, CA.
"For over 25 years we have been working with a lot of enterprise customers and we have seen how companies create applications. And now that we have moved to cloud computing, mobile, social and the Internet of Things, we see that the market needs a new way of creating applications," stated Jesse Shiah, CEO, President and Co-Founder of AgilePoint Inc., in this SYS-CON.tv interview at 15th Cloud Expo, held Nov 4–6, 2014, at the Santa Clara Convention Center in Santa Clara, CA.
SYS-CON Events announced today that Gridstore™, the leader in hyper-converged infrastructure purpose-built to optimize Microsoft workloads, will exhibit at SYS-CON's 16th International Cloud Expo®, which will take place on June 9-11, 2015, at the Javits Center in New York City, NY. Gridstore™ is the leader in hyper-converged infrastructure purpose-built for Microsoft workloads and designed to accelerate applications in virtualized environments. Gridstore’s hyper-converged infrastructure is the industry’s first all flash version of HyperConverged Appliances that include both compute and storag...
Today’s enterprise is being driven by disruptive competitive and human capital requirements to provide enterprise application access through not only desktops, but also mobile devices. To retrofit existing programs across all these devices using traditional programming methods is very costly and time consuming – often prohibitively so. In his session at @ThingsExpo, Jesse Shiah, CEO, President, and Co-Founder of AgilePoint Inc., discussed how you can create applications that run on all mobile devices as well as laptops and desktops using a visual drag-and-drop application – and eForms-buildi...
We certainly live in interesting technological times. And no more interesting than the current competing IoT standards for connectivity. Various standards bodies, approaches, and ecosystems are vying for mindshare and positioning for a competitive edge. It is clear that when the dust settles, we will have new protocols, evolved protocols, that will change the way we interact with devices and infrastructure. We will also have evolved web protocols, like HTTP/2, that will be changing the very core of our infrastructures. At the same time, we have old approaches made new again like micro-services...
Code Halos - aka "digital fingerprints" - are the key organizing principle to understand a) how dumb things become smart and b) how to monetize this dynamic. In his session at @ThingsExpo, Robert Brown, AVP, Center for the Future of Work at Cognizant Technology Solutions, outlined research, analysis and recommendations from his recently published book on this phenomena on the way leading edge organizations like GE and Disney are unlocking the Internet of Things opportunity and what steps your organization should be taking to position itself for the next platform of digital competition.
The 3rd International Internet of @ThingsExpo, co-located with the 16th International Cloud Expo - to be held June 9-11, 2015, at the Javits Center in New York City, NY - announces that its Call for Papers is now open. The Internet of Things (IoT) is the biggest idea since the creation of the Worldwide Web more than 20 years ago.
As the Internet of Things unfolds, mobile and wearable devices are blurring the line between physical and digital, integrating ever more closely with our interests, our routines, our daily lives. Contextual computing and smart, sensor-equipped spaces bring the potential to walk through a world that recognizes us and responds accordingly. We become continuous transmitters and receivers of data. In his session at @ThingsExpo, Andrew Bolwell, Director of Innovation for HP's Printing and Personal Systems Group, discussed how key attributes of mobile technology – touch input, sensors, social, and ...