SETS AND MAPS - Introduction to Java Programming: Comprehensive Version - page 798

21.1 Introduction
A set is an efficient data structure for storing and processing nonduplicate elements.
A map is like a dictionary that provides a quick lookup to retrieve a value using a key.

Key
Point

The “ No - Fly ” list is a list, created and maintained by the U.S. government's Terrorist Screen-
ing Center, of people who are not permitted to board a commercial aircraft for travel in or out
of the United States. Suppose we need to write a program that checks whether a person is on
the No-Fly list. You can use a list to store names in the No-Fly list. However, a more efficient
data structure for this application is a set .
Suppose your program also needs to store detailed information about terrorists in the
No-Fly list. The detailed information such as gender, height, weight, and nationality can be
retrieved using the name as the key. A map is an efficient data structure for such a task.
This chapter introduces sets and maps in the Java Collections Framework.

why set?

why map?

21.2 Sets
You can create a set using one of its three concrete classes: HashSet ,
LinkedHashSet , or TreeSet .

Key
Point

The Set interface extends the Collection interface, as shown in Figure 20.1. It does not
introduce new methods or constants, but it stipulates that an instance of Set contains no
duplicate elements. The concrete classes that implement Set must ensure that no duplicate
elements can be added to the set. That is, no two elements e1 and e2 can be in the set such
that e1.equals(e2) is true .
The AbstractSet class extends AbstractCollection and partially implements Set .
The AbstractSet class provides concrete implementations for the equals method and
the hashCode method. The hash code of a set is the sum of the hash codes of all the ele-
ments in the set. Since the size method and iterator method are not implemented in the
AbstractSet class, AbstractSet is an abstract class.
Three concrete classes of Set are HashSet , LinkedHashSet , and TreeSet , as shown
in Figure 21.1.

set
no duplicates

AbstractSet

21.2.1 HashSet
The HashSet class is a concrete class that implements Set . You can create an empty hash
set using its no-arg constructor or create a hash set from an existing collection. By default,
the initial capacity is 16 and the load factor is 0.75 . If you know the size of your set, you can
specify the initial capacity and load factor in the constructor. Otherwise, use the default set-
ting. The load factor is a value between 0.0 and 1.0 .
The load factor measures how full the set is allowed to be before its capacity is increased.
When the number of elements exceeds the product of the capacity and load factor, the capacity is
automatically doubled. For example, if the capacity is 16 and load factor is 0.75 , the capacity will
be doubled to 32 when the size reaches 12 (16 * 0.75

hash set

load factor

12). A higher load factor decreases the
space costs but increases the search time. Generally, the default load factor 0.75 is a good trade-
off between time and space costs. We will discuss more on the load factor in Chapter 27, Hashing.
A HashSet can be used to store duplicate-free elements. For efficiency, objects added
to a hash set need to implement the hashCode method in a manner that properly disperses
the hash code. Recall that hashCode is defined in the Object class. The hash codes of two
objects must be the same if the two objects are equal. Two unequal objects may have the
same hash code, but you should implement the hashCode method to avoid too many such
cases. Most of the classes in the Java API implement the hashCode method. For example,
the hashCode in the Integer class returns its int value. The hashCode in the Character
class returns the Unicode of the character. The hashCode in the String class returns
s 0 *31 (n - 1)

=

hashCode()

s 1 *31 (n - 2) + + c + s n - 1 , where s i is s.charAt(i) .