Skip to main content
Engineering LibreTexts

16.6: Using the Set and Map Interfaces

  • Page ID
    15166
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    The Set and Map interfaces are similar to the List interface in that there are multiple classes in the collections framework that implement them.

    16.6.1 Using the Set Interface.

    The Set interface is modeled after the set theory principles taught in mathematics. In mathematics, sets are groups of elements with a clearly defined algorithm for deciding if any given element is in any given set. Elements can be added to sets and can be removed from sets. Sets cannot have duplicate elements; if an element is added to a set that already contains an element equal to it, the new set still has a single such element. The elements of a set have no natural order; two sets that have the same elements listed in different orders are considered to be the same set.

    Screen Shot 2021-09-29 at 2.38.19 PM.png

    Figure 16.32: A partial list of methods of the Set<E> interface

    In computer science and in Java, data structures that model sets are designed for large collections of data. Such data structures have a method that determines if an object is in a given set with an efficient algorithm. For large data sets, using such a method is much faster than iterating through a list. Sometimes, you may or may not be able to list the elements of a set data structure in some natural order, depending on how the data structure is implemented. An incomplete listing of the methods of the Set<E> interface is given in the UML diagram in Figure 16.32.

    TreeSet<E> and HashSet<E> are two classes in the collections framework that implement the Set<E> interface. They both provide fast operations to check whether an element is in a set. They also provide quick insertion of an element into the set or removal of an element from a set. For large sets—those having at least several thousand elements—where there are large numbers of insertions, deletions, and tests for whether elements are in a set, linked lists would be much slower. 

    Overriding methods

    When using the Set<E> interface for a user-defined class E, you will likely want to override the definition of the equals() method from the Object class in E because that method is used when computing the value of aSet.contains(anElement). When using the TreeSet<E> class for a user defined class E, you should implement the compareTo() method of the Comparable interface because it is used to order the elements of E. In the next section, we will discuss the specific manner in which elements are ordered. Finally, when using the HashSet<E> class for a user defined class E, you should override the hashCode() method of the Object class because it is used HashSet<E>. Hash codes are indexes that are computed from the particular object that is being stored in the HashSet. Given an object’s hash code, the object can be retrieved directly, as we do with object’s stored in an array. However, we will not discuss hash codes in any detail in this text.

    Problem Statement

    Let’s think about a simple example for using a set data structure. Suppose that a programmer is developing an application for a large company for maintaining a no–call list. The programmer has decided to use the TreeSet<E> data structure to store objects of the PhoneRecord class that was defined earlier in this chapter and will use methods of the Set<E> interface to manipulate the data.

    A TreeSet seems to be an appropriate structure for this problem, since

    • A large amount of data will be involved.
    • The company wants the PhoneRecord data stored in alphabetical order.
    • The main use of the data will be to test whether names are in the set.

    The programmer might write a short method like that in Figure 16.33 to demonstrate how the Set<E> and TreeSet<E> structures will be used.

    Screen Shot 2021-09-29 at 2.59.10 PM.png

    Figure 16.33: A method that demonstrates use of the interface Set<E> and the class TreeSet<E>. 

    In order for the testSet() method to work as we would like, we need to have the PhoneRecord class implement the Comparable interface and to override the equals() method. For this example, it is reasonable to assume that the name field of PhoneRecord objects should be unique so that it can be used to decide if two PhoneRecord objects are equal. The name field of PhoneRecord can also be used to define the other two methods discussed above. Thus, add the following code to the PhoneRecord class.

    public boolean equals (Object ob){

    return name.equals(((PhoneRecord)ob).getName());

    } //equals()

    public int compareTo (Object ob){

    return name.compareTo(((PhoneRecord)ob).getName());

    } //compareTo()

    public int hashCode(){

    return name.hashCode();

    } //hashCode()

    The output of the TestSet() method is listed below:

    Testing TreeSet and Set

    Roger M is contained in theSet is true

    Mary Q is contained in theSet is false

    Gary G 201−119−8765

    Jane M 090−997−1987

    Roger M 090−997−2918

    Stacy K 090−997−9188

    Notice that Jane M PhoneRecord appears only once in the listing of elements in the set.

    16.6.2 Using the Map<k, V> Interface.

    Screen Shot 2021-09-29 at 3.38.10 PM.png

    Figure 16.34: A partial list of methods of Map<K, V>.

    The Map<K, V> interface is modeled after looking up definitions for words in a dictionary. In computer science, maps are considered to be a collection of pairs of elements. A pair consists of a key that corresponds to a word being looked up and a value corresponding to the definition of the word. Pairs can be added to maps and can be removed from maps. Maps cannot have distinct pairs with the same keys; if you attempt to add a pair to a map that already contains a pair with the same key, the second pair will replace the first. An incomplete listing of the methods of the Map<K, V> interface is given in the UML diagram in Figure 16.34. TreeMap<K, V> and HashMap<K, V> are two classes in the collections framework that implement the Map<K, V> interface.

     Let’s now consider a simple example of using a map data structure. Suppose that our programmer has been hired by a large company to develop an application that maintains an electronic phone list for company employees. The programmer has decided to use the TreeMap<E> data structure to store pairs of names and telephone numbers and will use methods of the Map<K, V> interface to manipulate the data.

    A TreeMap seems like an appropriate data structure for this problem, since

    • A large amount of data will be involved.
    • The company wants the PhoneRecord data stored in alphabetical order.
    • The main use of the data will be to use names to access telephone numbers.

    The programmer might write a short method like that in Figure 16.35 to demonstrate how the Map<K, V> and TreeMap<K, V> structures will be used.

    The output for this test program is:

    Stacy K has phone 090−997−9188

    Jane M has phone 090−233−0000

    Notice the the second phone number for Jane M is the one that is stored in the data structure.

    Screen Shot 2021-09-29 at 4.08.46 PM.pngFigure 16.35: A method that demonstrates use of the interface Map <K, V> and the class TreeMap<K, V>.

    This page titled 16.6: Using the Set and Map Interfaces is shared under a CC BY 4.0 license and was authored, remixed, and/or curated by Ralph Morelli & Ralph Wade via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.