Click here to close now.




















Welcome!

Java IoT Authors: VictorOps Blog, Bob Gourley, Elizabeth White, Dana Gardner, Jim Taylor

Related Topics: Java IoT

Java IoT: 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
SYS-CON Events announced today that HPM Networks will exhibit at the 17th International Cloud Expo®, which will take place on November 3–5, 2015, at the Santa Clara Convention Center in Santa Clara, CA. For 20 years, HPM Networks has been integrating technology solutions that solve complex business challenges. HPM Networks has designed solutions for both SMB and enterprise customers throughout the San Francisco Bay Area.
For IoT to grow as quickly as analyst firms’ project, a lot is going to fall on developers to quickly bring applications to market. But the lack of a standard development platform threatens to slow growth and make application development more time consuming and costly, much like we’ve seen in the mobile space. In his session at @ThingsExpo, Mike Weiner, Product Manager of the Omega DevCloud with KORE Telematics Inc., discussed the evolving requirements for developers as IoT matures and conducted a live demonstration of how quickly application development can happen when the need to comply wit...
The Internet of Everything (IoE) brings together people, process, data and things to make networked connections more relevant and valuable than ever before – transforming information into knowledge and knowledge into wisdom. IoE creates new capabilities, richer experiences, and unprecedented opportunities to improve business and government operations, decision making and mission support capabilities.
Explosive growth in connected devices. Enormous amounts of data for collection and analysis. Critical use of data for split-second decision making and actionable information. All three are factors in making the Internet of Things a reality. Yet, any one factor would have an IT organization pondering its infrastructure strategy. How should your organization enhance its IT framework to enable an Internet of Things implementation? In his session at @ThingsExpo, James Kirkland, Red Hat's Chief Architect for the Internet of Things and Intelligent Systems, described how to revolutionize your archit...
MuleSoft has announced the findings of its 2015 Connectivity Benchmark Report on the adoption and business impact of APIs. The findings suggest traditional businesses are quickly evolving into "composable enterprises" built out of hundreds of connected software services, applications and devices. Most are embracing the Internet of Things (IoT) and microservices technologies like Docker. A majority are integrating wearables, like smart watches, and more than half plan to generate revenue with APIs within the next year.
Growth hacking is common for startups to make unheard-of progress in building their business. Career Hacks can help Geek Girls and those who support them (yes, that's you too, Dad!) to excel in this typically male-dominated world. Get ready to learn the facts: Is there a bias against women in the tech / developer communities? Why are women 50% of the workforce, but hold only 24% of the STEM or IT positions? Some beginnings of what to do about it! In her Opening Keynote at 16th Cloud Expo, Sandy Carter, IBM General Manager Cloud Ecosystem and Developers, and a Social Business Evangelist, d...
In his keynote at 16th Cloud Expo, Rodney Rogers, CEO of Virtustream, discussed the evolution of the company from inception to its recent acquisition by EMC – including personal insights, lessons learned (and some WTF moments) along the way. Learn how Virtustream’s unique approach of combining the economics and elasticity of the consumer cloud model with proper performance, application automation and security into a platform became a breakout success with enterprise customers and a natural fit for the EMC Federation.
The Internet of Things is not only adding billions of sensors and billions of terabytes to the Internet. It is also forcing a fundamental change in the way we envision Information Technology. For the first time, more data is being created by devices at the edge of the Internet rather than from centralized systems. What does this mean for today's IT professional? In this Power Panel at @ThingsExpo, moderated by Conference Chair Roger Strukhoff, panelists addressed this very serious issue of profound change in the industry.
Discussions about cloud computing are evolving into discussions about enterprise IT in general. As enterprises increasingly migrate toward their own unique clouds, new issues such as the use of containers and microservices emerge to keep things interesting. In this Power Panel at 16th Cloud Expo, moderated by Conference Chair Roger Strukhoff, panelists addressed the state of cloud computing today, and what enterprise IT professionals need to know about how the latest topics and trends affect their organization.
It is one thing to build single industrial IoT applications, but what will it take to build the Smart Cities and truly society-changing applications of the future? The technology won’t be the problem, it will be the number of parties that need to work together and be aligned in their motivation to succeed. In his session at @ThingsExpo, Jason Mondanaro, Director, Product Management at Metanga, discussed how you can plan to cooperate, partner, and form lasting all-star teams to change the world and it starts with business models and monetization strategies.
Converging digital disruptions is creating a major sea change - Cisco calls this the Internet of Everything (IoE). IoE is the network connection of People, Process, Data and Things, fueled by Cloud, Mobile, Social, Analytics and Security, and it represents a $19Trillion value-at-stake over the next 10 years. In her keynote at @ThingsExpo, Manjula Talreja, VP of Cisco Consulting Services, discussed IoE and the enormous opportunities it provides to public and private firms alike. She will share what businesses must do to thrive in the IoE economy, citing examples from several industry sectors.
There will be 150 billion connected devices by 2020. New digital businesses have already disrupted value chains across every industry. APIs are at the center of the digital business. You need to understand what assets you have that can be exposed digitally, what their digital value chain is, and how to create an effective business model around that value chain to compete in this economy. No enterprise can be complacent and not engage in the digital economy. Learn how to be the disruptor and not the disruptee.
Akana has released Envision, an enhanced API analytics platform that helps enterprises mine critical insights across their digital eco-systems, understand their customers and partners and offer value-added personalized services. “In today’s digital economy, data-driven insights are proving to be a key differentiator for businesses. Understanding the data that is being tunneled through their APIs and how it can be used to optimize their business and operations is of paramount importance,” said Alistair Farquharson, CTO of Akana.
Business as usual for IT is evolving into a "Make or Buy" decision on a service-by-service conversation with input from the LOBs. How does your organization move forward with cloud? In his general session at 16th Cloud Expo, Paul Maravei, Regional Sales Manager, Hybrid Cloud and Managed Services at Cisco, discusses how Cisco and its partners offer a market-leading portfolio and ecosystem of cloud infrastructure and application services that allow you to uniquely and securely combine cloud business applications and services across multiple cloud delivery models.
The enterprise market will drive IoT device adoption over the next five years. In his session at @ThingsExpo, John Greenough, an analyst at BI Intelligence, division of Business Insider, analyzed how companies will adopt IoT products and the associated cost of adopting those products. John Greenough is the lead analyst covering the Internet of Things for BI Intelligence- Business Insider’s paid research service. Numerous IoT companies have cited his analysis of the IoT. Prior to joining BI Intelligence, he worked analyzing bank technology for Corporate Insight and The Clearing House Payment...
"Optimal Design is a technology integration and product development firm that specializes in connecting devices to the cloud," stated Joe Wascow, Co-Founder & CMO of Optimal Design, in this SYS-CON.tv interview at @ThingsExpo, held June 9-11, 2015, at the Javits Center in New York City.
SYS-CON Events announced today that CommVault has been named “Bronze Sponsor” of SYS-CON's 17th International Cloud Expo®, which will take place on November 3–5, 2015, at the Santa Clara Convention Center in Santa Clara, CA. A singular vision – a belief in a better way to address current and future data management needs – guides CommVault in the development of Singular Information Management® solutions for high-performance data protection, universal availability and simplified management of data on complex storage networks. CommVault's exclusive single-platform architecture gives companies unp...
Electric Cloud and Arynga have announced a product integration partnership that will bring Continuous Delivery solutions to the automotive Internet-of-Things (IoT) market. The joint solution will help automotive manufacturers, OEMs and system integrators adopt DevOps automation and Continuous Delivery practices that reduce software build and release cycle times within the complex and specific parameters of embedded and IoT software systems.
"ciqada is a combined platform of hardware modules and server products that lets people take their existing devices or new devices and lets them be accessible over the Internet for their users," noted Geoff Engelstein of ciqada, a division of Mars International, in this SYS-CON.tv interview at @ThingsExpo, held June 9-11, 2015, at the Javits Center in New York City.
Internet of Things is moving from being a hype to a reality. Experts estimate that internet connected cars will grow to 152 million, while over 100 million internet connected wireless light bulbs and lamps will be operational by 2020. These and many other intriguing statistics highlight the importance of Internet powered devices and how market penetration is going to multiply many times over in the next few years.