Click here to close now.

Welcome!

JAVA IoT Authors: Liz McMillan, Sematext Blog, Pat Romanski, John Wetherill, Carmen Gonzalez

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
With major technology companies and startups seriously embracing IoT strategies, now is the perfect time to attend @ThingsExpo in Silicon Valley. Learn what is going on, contribute to the discussions, and ensure that your enterprise is as "IoT-Ready" as it can be! Internet of @ThingsExpo, taking place Nov 3-5, 2015, at the Santa Clara Convention Center in Santa Clara, CA, is co-located with 17th Cloud Expo and will feature technical sessions from a rock star conference faculty and the leading industry players in the world. The Internet of Things (IoT) is the most profound change in personal an...
The worldwide cellular network will be the backbone of the future IoT, and the telecom industry is clamoring to get on board as more than just a data pipe. In his session at @ThingsExpo, Evan McGee, CTO of Ring Plus, Inc., discussed what service operators can offer that would benefit IoT entrepreneurs, inventors, and consumers. Evan McGee is the CTO of RingPlus, a leading innovative U.S. MVNO and wireless enabler. His focus is on combining web technologies with traditional telecom to create a new breed of unified communication that is easily accessible to the general consumer. With over a de...
SYS-CON Events announced today that MetraTech, now part of Ericsson, 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. Ericsson is the driving force behind the Networked Society- a world leader in communications infrastructure, software and services. Some 40% of the world’s mobile traffic runs through networks Ericsson has supplied, serving more than 2.5 billion subscribers.
Disruptive macro trends in technology are impacting and dramatically changing the "art of the possible" relative to supply chain management practices through the innovative use of IoT, cloud, machine learning and Big Data to enable connected ecosystems of engagement. Enterprise informatics can now move beyond point solutions that merely monitor the past and implement integrated enterprise fabrics that enable end-to-end supply chain visibility to improve customer service delivery and optimize supplier management. Learn about enterprise architecture strategies for designing connected systems tha...
From telemedicine to smart cars, digital homes and industrial monitoring, the explosive growth of IoT has created exciting new business opportunities for real time calls and messaging. In his session at @ThingsExpo, Ivelin Ivanov, CEO and Co-Founder of Telestax, shared some of the new revenue sources that IoT created for Restcomm – the open source telephony platform from Telestax. Ivelin Ivanov is a technology entrepreneur who founded Mobicents, an Open Source VoIP Platform, to help create, deploy, and manage applications integrating voice, video and data. He is the co-founder of TeleStax, a...
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 @ThingsExpo, Jesse Shiah, CEO / President / Co-Founder of AgilePoint Inc., showed what is needed to leverage the IoT to transform your business. He discussed opportunities and challenges ahead for the IoT from a market and technical point of vie...
Grow your business with enterprise wearable apps using SAP Platforms and Google Glass. SAP and Google just launched the SAP and Google Glass Challenge, an opportunity for you to innovate and develop the best Enterprise Wearable App using SAP Platforms and Google Glass and gain valuable market exposure. In his session at @ThingsExpo, Brian McPhail, Senior Director of Business Development, ISVs & Digital Commerce at SAP, outlined the timeline of the SAP Google Glass Challenge and the opportunity for developers, start-ups, and companies of all sizes to engage with SAP today.
Cultural, regulatory, environmental, political and economic (CREPE) conditions over the past decade are creating cross-industry solution spaces that require processes and technologies from both the Internet of Things (IoT), and Data Management and Analytics (DMA). These solution spaces are evolving into Sensor Analytics Ecosystems (SAE) that represent significant new opportunities for organizations of all types. Public Utilities throughout the world, providing electricity, natural gas and water, are pursuing SmartGrid initiatives that represent one of the more mature examples of SAE. We have s...
The Internet of Things will put IT to its ultimate test by creating infinite new opportunities to digitize products and services, generate and analyze new data to improve customer satisfaction, and discover new ways to gain a competitive advantage across nearly every industry. In order to help corporate business units to capitalize on the rapidly evolving IoT opportunities, IT must stand up to a new set of challenges. In his session at @ThingsExpo, Jeff Kaplan, Managing Director of THINKstrategies, will examine why IT must finally fulfill its role in support of its SBUs or face a new round of...
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, described 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.
The true value of the Internet of Things (IoT) lies not just in the data, but through the services that protect the data, perform the analysis and present findings in a usable way. With many IoT elements rooted in traditional IT components, Big Data and IoT isn’t just a play for enterprise. In fact, the IoT presents SMBs with the prospect of launching entirely new activities and exploring innovative areas. CompTIA research identifies several areas where IoT is expected to have the greatest impact.
Can call centers hang up the phones for good? Intuitive Solutions did. WebRTC enabled this contact center provider to eliminate antiquated telephony and desktop phone infrastructure with a pure web-based solution, allowing them to expand beyond brick-and-mortar confines to a home-based agent model. It also ensured scalability and better service for customers, including MUY! Companies, one of the country's largest franchise restaurant companies with 232 Pizza Hut locations. This is one example of WebRTC adoption today, but the potential is limitless when powered by IoT.
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 @ThingsExpo, Esmeralda Swartz, CMO of MetraTech, discussed 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!
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 will addresses this very serious issue of profound change in the industry.
SYS-CON Events announced today that BMC 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. BMC delivers software solutions that help IT transform digital enterprises for the ultimate competitive business advantage. BMC has worked with thousands of leading companies to create and deliver powerful IT management services. From mainframe to cloud to mobile, BMC pairs high-speed digital innovation with robust IT industrialization – allowing customers to provide amazing user experiences with optimized IT per...
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...
SYS-CON Events announced today that O'Reilly Media has been named “Media 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 City, NY. O'Reilly Media spreads the knowledge of innovators through its books, online services, magazines, and conferences. Since 1978, O'Reilly Media has been a chronicler and catalyst of cutting-edge development, homing in on the technology trends that really matter and spurring their adoption by amplifying "faint signals" from the alpha geeks who are creating the future. An active participa...
The world is at a tipping point where the technology, the device and global adoption are converging to such a point that we will see an explosion of a world where smartphone devices not only allow us to talk to each other, but allow for communication between everything – serving as a central hub from which we control our world – MediaTek is at the heart of both driving this and allowing the markets to drive this reality forward themselves. The next wave of consumer gadgets is here – smart, connected, and small. If your ambitions are big, so are ours. In his session at @ThingsExpo, Jack Hu, D...
The 4th International Internet of @ThingsExpo, co-located with the 17th International Cloud Expo - to be held November 3-5, 2015, at the Santa Clara Convention Center in Santa Clara, CA - announces that its Call for Papers is open. The Internet of Things (IoT) is the biggest idea since the creation of the Worldwide Web more than 20 years ago.
SYS-CON Events announced today that DragonGlass, an enterprise search platform, 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. After eleven years of designing and building custom applications, OpenCrowd has launched DragonGlass, a cloud-based platform that enables the development of search-based applications. These are a new breed of applications that utilize a search index as their backbone for data retrieval. They can easily adapt to new data sets and provide access to both structured and unstruc...