Welcome!

Java Authors: Carmen Gonzalez, Liz Dickinson, Pat Romanski, Bob Gourley, Yakov Fain

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)

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.


@ThingsExpo Stories
SYS-CON Events announced today that SOA Software, an API management leader, will exhibit at SYS-CON's 15th International Cloud Expo®, which will take place on November 4–6, 2014, at the Santa Clara Convention Center in Santa Clara, CA. SOA Software is a leading provider of API Management and SOA Governance products that equip business to deliver APIs and SOA together to drive their company to meet its business strategy quickly and effectively. SOA Software’s technology helps businesses to accelerate their digital channels with APIs, drive partner adoption, monetize their assets, and achieve a...
SYS-CON Events announced today that Aria Systems, the recurring revenue expert, has been named "Bronze Sponsor" of SYS-CON's 15th International Cloud Expo®, which will take place on November 4-6, 2014, at the Santa Clara Convention Center in Santa Clara, CA. Aria Systems helps leading businesses connect their customers with the products and services they love. Industry leaders like Pitney Bowes, Experian, AAA NCNU, VMware, HootSuite and many others choose Aria to power their recurring revenue business and deliver exceptional experiences to their customers.
SYS-CON Events announced today that AgilePoint, the leading provider of Microsoft-centric Business Process Management software, will exhibit at SYS-CON's 2nd International @ThingsExpo which will take place on November 4–6, 2014, at the Santa Clara Convention Center in Santa Clara, CA. AgilePoint is the leading provider of Microsoft-based Business Process Management (BPM) software products, has 1,300+ on-premise and cloud deployments in 25+ countries and provides the same advanced BPM feature set as J2EE vendors like IBM and Appian for the Microsoft .NET native environment. AgilePoint customer...
The Internet of Things (IoT) promises to evolve the way the world does business; however, understanding how to apply it to your company can be a mystery. Most people struggle with understanding the potential business uses or tend to get caught up in the technology, resulting in solutions that fail to meet even minimum business goals. In his session at Internet of @ThingsExpo, Jesse Shiah, CEO / President / Co-Founder of AgilePoint Inc., will show what is needed to leverage the IoT to transform your business. He will discuss opportunities and challenges ahead for the IoT from a market and tec...
SYS-CON Events announced today that Utimaco will exhibit at SYS-CON's 15th International Cloud Expo®, which will take place on November 4–6, 2014, at the Santa Clara Convention Center in Santa Clara, CA. Utimaco is a leading manufacturer of hardware based security solutions that provide the root of trust to keep cryptographic keys safe, secure critical digital infrastructures and protect high value data assets. Only Utimaco delivers a general-purpose hardware security module (HSM) as a customizable platform to easily integrate into existing software solutions, embed business logic and build s...
One of the biggest challenges when developing connected devices is identifying user value and delivering it through successful user experiences. In his session at Internet of @ThingsExpo, Mike Kuniavsky, Principal Scientist, Innovation Services at PARC, will describe an IoT-specific approach to user experience design that combines approaches from interaction design, industrial design and service design to create experiences that go beyond simple connected gadgets to create lasting, multi-device experiences grounded in people’s real needs and desires.
SYS-CON Events announced today that TeleStax, the main sponsor of Mobicents, will exhibit at Internet of @ThingsExpo, which will take place on November 4–6, 2014, at the Santa Clara Convention Center in Santa Clara, CA. TeleStax provides Open Source Communications software and services that facilitate the shift from legacy SS7 based IN networks to IP based LTE and IMS networks hosted on private (on-premise), hybrid or public clouds. TeleStax products include Restcomm, JSLEE, SMSC Gateway, USSD Gateway, SS7 Resource Adaptors, SIP Servlets, Rich Multimedia Services, Presence Services/RCS, Diame...
Samsung VP Jacopo Lenzi, who headed the company's recent SmartThings acquisition under the auspices of Samsung's Open Innovaction Center (OIC), answered a few questions we had about the deal. This interview was in conjunction with our interview with SmartThings CEO Alex Hawkinson. IoT Journal: SmartThings was developed in an open, standards-agnostic platform, and will now be part of Samsung's Open Innovation Center. Can you elaborate on your commitment to keep the platform open? Jacopo Lenzi: Samsung recognizes that true, accelerated innovation cannot be driven from one source, but requires a...
The Internet of Things will greatly expand the opportunities for data collection and new business models driven off of that data. In her session at Internet of @ThingsExpo, Esmeralda Swartz, CMO of MetraTech, will discuss how for this to be effective you not only need to have infrastructure and operational models capable of utilizing this new phenomenon, but increasingly service providers will need to convince a skeptical public to participate. Get ready to show them the money! Speaker Bio: Esmeralda Swartz, CMO of MetraTech, has spent 16 years as a marketing, product management, and busin...
Things are being built upon cloud foundations to transform organizations. This CEO Power Panel at 15th Cloud Expo, moderated by Roger Strukhoff, Cloud Expo and @ThingsExpo conference chair, will address the big issues involving these technologies and, more important, the results they will achieve. How important are public, private, and hybrid cloud to the enterprise? How does one define Big Data? And how is the IoT tying all this together?
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...
SYS-CON Events announces a new pavilion on the Cloud Expo floor where WebRTC converges with the Internet of Things. Pavilion will showcase WebRTC and the Internet of Things. The Internet of Things (IoT) is the most profound change in personal and enterprise IT since the creation of the Worldwide Web more than 20 years ago. All major researchers estimate there will be tens of billions devices--computers, smartphones, tablets, and sensors – connected to the Internet by 2020. This number will continue to grow at a rapid pace for the next several decades.
The only place to be June 9-11 is Cloud Expo & @ThingsExpo 2015 East at the Javits Center in New York City. Join us there as delegates from all over the world come to listen to and engage with speakers & sponsors from the leading Cloud Computing, IoT & Big Data companies. Cloud Expo & @ThingsExpo are the leading events covering the booming market of Cloud Computing, IoT & Big Data for the enterprise. Speakers from all over the world will be hand-picked for their ability to explore the economic strategies that utility/cloud computing provides. Whether public, private, or in a hybrid form, clo...
SYS-CON Events announced today that Gridstore™, the leader in software-defined storage (SDS) purpose-built for Windows Servers and Hyper-V, will exhibit at SYS-CON's 15th International Cloud Expo®, which will take place on November 4–6, 2014, at the Santa Clara Convention Center in Santa Clara, CA. Gridstore™ is the leader in software-defined storage purpose built for virtualization that is designed to accelerate applications in virtualized environments. Using its patented Server-Side Virtual Controller™ Technology (SVCT) to eliminate the I/O blender effect and accelerate applications Gridsto...
SYS-CON Events announced today that Red Hat, the world's leading provider of open source solutions, will exhibit at Internet of @ThingsExpo, which will take place on November 4–6, 2014, at the Santa Clara Convention Center in Santa Clara, CA. Red Hat is the world's leading provider of open source software solutions, using a community-powered approach to reliable and high-performing cloud, Linux, middleware, storage and virtualization technologies. Red Hat also offers award-winning support, training, and consulting services. As the connective hub in a global network of enterprises, partners, a...
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 Internet of @ThingsExpo, Andrew Bolwell, Director of Innovation for HP’s Printing and Personal Systems Group, will discuss how key attributes of mobile technology – touch input, senso...
The Internet of Things (IoT) is making everything it touches smarter – smart devices, smart cars and smart cities. And lucky us, we’re just beginning to reap the benefits as we work toward a networked society. However, this technology-driven innovation is impacting more than just individuals. The IoT has an environmental impact as well, which brings us to the theme of this month’s #IoTuesday Twitter chat. The ability to remove inefficiencies through connected objects is driving change throughout every sector, including waste management. BigBelly Solar, located just outside of Boston, is trans...
Connected devices and the Internet of Things are getting significant momentum in 2014. In his session at Internet of @ThingsExpo, Jim Hunter, Chief Scientist & Technology Evangelist at Greenwave Systems, will examine three key elements that together will drive mass adoption of the IoT before the end of 2015. The first element is the recent advent of robust open source protocols (like AllJoyn and WebRTC) that facilitate M2M communication. The second is broad availability of flexible, cost-effective storage designed to handle the massive surge in back-end data in a world where timely analytics...
Internet of @ThingsExpo Silicon Valley announced on Thursday its first 12 all-star speakers and sessions for its upcoming event, which will take place November 4-6, 2014, at the Santa Clara Convention Center in California. @ThingsExpo, the first and largest IoT event in the world, debuted at the Javits Center in New York City in June 10-12, 2014 with over 6,000 delegates attending the conference. Among the first 12 announced world class speakers, IBM will present two highly popular IoT sessions, which will take place November 4-6, 2014 at the Santa Clara Convention Center in Santa Clara, Calif...
From a software development perspective IoT is about programming "things," about connecting them with each other or integrating them with existing applications. In his session at @ThingsExpo, Yakov Fain, co-founder of Farata Systems and SuranceBay, will show you how small IoT-enabled devices from multiple manufacturers can be integrated into the workflow of an enterprise application. This is a practical demo of building a framework and components in HTML/Java/Mobile technologies to serve as a platform that can integrate new devices as they become available on the market.