3-14 The Java Collections Framework

We’ve dedicated a lot of time learning how to build abstract data types from scratch based on static arrays and dynamic linked lists.  Designing effective data structures is a lot of work, but it’s also very satisfying to produce efficient and elegant solutions.  Because certain ADTs are so commonly used in computer science, most modern languages support them as part of their core API and there is usually no need to reinvent the wheel.

As mentioned in 3-4 when we talked about the ArrayList, the Java API includes two hierarchies of interfaces and classes called the Java Collections Framework (JCF).  All of the JCF interfaces and classes are located in the java.util package.  Below is an illustration of some of the most commonly used interfaces and classes in the framework:

In UML, <<interface>> is used to indicate an interface class.  Set and List extend the Collection interface:

• Collection — Defines basic methods that all collections must support.
• Set — Defines a collection that does not allow duplicate elements.
• List — Defines a collection that stores elements in a sequence.  It supports index access and allows duplicate elements.
• Map — Similar to a collection, but a map stores key-value pairs (not just values) where each value has a unique key to identify it.  A Map is different enough from a Collection that it does not extend the Collection

The HashSet, ArrayList, LinkedList, and HashMap classes implement the interfaces above.  In UML, a class that implements an interface is indicated with a dotted arrow:

• HashSet — Stores only unique elements (no duplicate values allowed).
• ArrayList — Array-based, so it’s more efficient than a LinkedList for accessing elements randomly (i.e., using index), but less efficient when inserting or deleting elements in the middle of the list (see 3-4).
• LinkedList – Dynamic, like ours, but with many additional methods including those to support stack and queue operations.  Less efficient than an ArrayList for accessing elements randomly (i.e., using index), but more efficient if inserting or deleting elements in the middle of the list.
• HashMap – Stores key-value pairs (no duplicate keys allowed).

You might ask: If the Java API already provides these common ADTs why did we spend all this time learning how to build them from scratch?  Good question!  To become an exceptional developer you need deep understanding of the issues involved in designing efficient data structures, and you cannot learn this by simply using existing classes.  Your knowledge of how data structures work from the inside out will give you greater understanding and appreciation for the JCF classes.  Moreover, what if the Java API does not include a data structure that meets your needs?  Again, a deep understanding of how to create your own data structures is a very valuable skill.

You already have experience with the ArrayList class, and the other JCF classes are just as straightforward, so I am not going to provide extensive examples here.  The best way to learn about them is by working with them.

Congratulations!

If you’ve been following along and working through all of the exercises you should have a solid foundation in Java and common algorithms and data structures at this point – more than required for Java AP.  This lesson ends our coverage of the core features of Java.  In the next set of lessons we’ll look at how to build Java applications with graphical user interfaces (GUIs).  Stay tuned!

You Try!

1. In 3-2 Q2 we wrote a program that only accepted 10 unique integers.  Write a similar program but this time use a HashSet.  Once your code has accepted 10 integers, simply display them.  Hint: Try using an enhanced for loop to display your HashSet contents.
2. Modify your DynamicQueue to use the JCF LinkedList instead of the one we designed and implemented. Test it with your DynamicQueueTest class.
3. You’ve been given this Python code to maintain a dictionary of Geek Terms:
   
   Python

   # Geek Translator # Demonstrates using dictionaries   geek = {"404": "clueless.  From the web error message 404, meaning page not found.",         "Googling": "searching the Internet for background information on a person.",         "Keyboard Plaque" : "the collection of debris found in computer keyboards.",         "Link Rot" : "the process by which web page links become obsolete.",         "Percussive Maintenance" : "the act of striking an electronic device to make it work.",         "Uninstalled" : "being fired.  Especially popular during the dot-bomb era."}    choice = None while choice != "5":       print """     GEEK TRANSLATOR           1 - Look Up a Geek Term     2 - Add a Geek Term     3 - Redefine a Geek Term     4 - Delete a Geek Term     5 - Quit     """           choice = raw_input("Choice: ")     print       # exit     if choice == "5":         print "Good-bye."       # get a definition     elif choice == "1":         term = raw_input("What term do you want me to translate?: ")         if term in geek:             definition = geek[term]             print "\n", term, "means", definition         else:             print "\nSorry, I don't know", term       # add a term-definition pair     elif choice == "2":         term = raw_input("What term do you want me to add?: ")         if term not in geek:             definition = raw_input("\nWhat's the definition?: ")             geek[term] = definition             print "\n", term, "has been added."         else:             print "\nThat term already exists!  Try redefining it."       # redefine an existing term     elif choice == "3":         term = raw_input("What term do you want me to redefine?: ")         if term in geek:             definition = raw_input("What's the new definition?: ")             geek[term] = definition             print "\n", term, "has been redefined."         else:             print "\nThat term doesn't exist!  Try adding it."              # delete a term-definition pair     elif choice == "4":         term = raw_input("What term do you want me to delete?: ")         if term in geek:             del geek[term]             print "\nOkay, I deleted", term         else:             print "\nI can't do that!", term, "doesn't exist in the dictionary."                   # some unknown choice     else:         print "\nSorry, but", choice, "isn't a valid choice."

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71

   # Geek Translator # Demonstrates using dictionaries   geek = {"404": "clueless.  From the web error message 404, meaning page not found.",         "Googling": "searching the Internet for background information on a person.",         "Keyboard Plaque" : "the collection of debris found in computer keyboards.",         "Link Rot" : "the process by which web page links become obsolete.",         "Percussive Maintenance" : "the act of striking an electronic device to make it work.",         "Uninstalled" : "being fired.  Especially popular during the dot-bomb era."}    choice = None while choice != "5":       print """     GEEK TRANSLATOR           1 - Look Up a Geek Term     2 - Add a Geek Term     3 - Redefine a Geek Term     4 - Delete a Geek Term     5 - Quit     """           choice = raw_input("Choice: ")     print       # exit     if choice == "5":         print "Good-bye."       # get a definition     elif choice == "1":         term = raw_input("What term do you want me to translate?: ")         if term in geek:             definition = geek[term]             print "\n", term, "means", definition         else:             print "\nSorry, I don't know", term       # add a term-definition pair     elif choice == "2":         term = raw_input("What term do you want me to add?: ")         if term not in geek:             definition = raw_input("\nWhat's the definition?: ")             geek[term] = definition             print "\n", term, "has been added."         else:             print "\nThat term already exists!  Try redefining it."       # redefine an existing term     elif choice == "3":         term = raw_input("What term do you want me to redefine?: ")         if term in geek:             definition = raw_input("What's the new definition?: ")             geek[term] = definition             print "\n", term, "has been redefined."         else:             print "\nThat term doesn't exist!  Try adding it."              # delete a term-definition pair     elif choice == "4":         term = raw_input("What term do you want me to delete?: ")         if term in geek:             del geek[term]             print "\nOkay, I deleted", term         else:             print "\nI can't do that!", term, "doesn't exist in the dictionary."                   # some unknown choice     else:         print "\nSorry, but", choice, "isn't a valid choice."

   
   Rewrite the code in Java using a HashMap.