Chapter 23 - Sets and Maps

Question 1

What is a set?

Answer 1

A set is an efficient data structure for storing and processing nonduplicate elements.

Question 2

What is a map?

Answer 2

The map data structure is like a dictionary that provides a quick lookup to retrieve a value using a key.

Question 3

Describe the Set interface.

Answer 3

The Set interface extends the Collection interface. 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.
Three concrete classes of Set are: HashSet, LinkedHashSet, and TreeSet.

Question 4

What is a HashSet?

Answer 4

The concrete HashSet class implements the Set interface, backed by a hash table (actually a HashMap instance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This class permits the null element.

Question 5

What is the hashCode method?

Answer 5

For efficiency, objects added to a hash set need to implement the hashCode method in a manner that properly disperses the hash code. The 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.

Question 6

How do you create a HashSet?

Answer 6

HashSet has 4 different constructors:
HashSet() Create an empty hash set.
HashSet(c: Collection[? extends E>) Create a hash set from an existing collection.
HashSet(initialCapacity: int) Create a hash set with a specific initial capacity (default = 16).
HashSet(initialCapacity: int, loadFactor: float) The load factor measures how full the set is allowed to be before its capacity is increased (default = 0.75).

Question 7

What is a LinkedHashSet?

Answer 7

LinkedHashSet extends HashSet with a linked-list implementation that supports an ordering of the elements in the set. The elements in a HashSet are not ordered, bu the elements in a LinkedHashSet can be retrieved in the order in which they were inserted into the set.
Other than that, LinkedHashSet and HashSet are identical. They have identical constructors.

Question 8

How do you decide whether to use LinkedHashSet or HashSet?

Answer 8

If you don’t need to maintain the order in which the elements are inserted, use HashSet, which is more efficient than LinkedHashSet.

Question 9

Describe TreeSet.

Answer 9

SortedSet is a subinterface of Set, which guarantees that the elements in the set are sorted.
NavigableSet extends SortedSet to provide navigation methods.
TreeSet implements the NavigableSet interface, therefore inherits from SortedSet as well.
The elements in a TreeSet are always sorted. You can only add objects to a TreeSet as long as they can be compared with each other.

Question 10

How do you create a TreeSet?

Answer 10

TreeSet() : Constructs a new, empty tree set, sorted according to the natural ordering of its elements.
TreeSet(Collection[? extends E> c) : Constructs a new tree set containing the elements in the specified collection, sorted according to the natural ordering of its elements.
TreeSet(Comparator[? super E> comparator) : Constructs a new, empty tree set, sorted according to the specified comparator.
TreeSet(SortedSet[E> s) : Constructs a new tree set containing the same elements and using the same ordering as the specified sorted set.

Question 11

A tree set has the methods first() and last() available to it. What do they do?

Answer 11

first() returns the first element in the tree set.

last() returns the last element in the tree set.

Question 12

A tree set has the methods headSet(element) and tailSet(element) available to it. What do they do?

Answer 12

headSet(element) returns the elements in the tree set before the specified element.
tailSet(element) returns the elements in the tree set after the specified element, including the element.

Question 13

A tree set has the methods lower(e) and higher(e) available to it. What do they do?

Answer 13

lower(e) returns the largest element less than e in the tree set.
higher(e) returns the smallest element greater than e in the tree set.

Question 14

A tree set has the methods floor(e) and ceiling(e) available to it. What do they do?

Answer 14

floor(e) returns the largest element less than or equal to e in the tree set.
ceiling(e) returns the smallest element greater than or equal to e in the tree list.

Question 15

How do you decide whether to use a hash set or a tree set?

Answer 15

If you don’t need to maintain a sorted set when updating a set, you should use a hash set, because it takes less time to insert and remove elements in a hash set. When you need a sorted set, you can create a tree set from the hash set.

Question 16

When should you use sets and when should you use lists?

Answer 16

Lists are useful for accessing elements through the index. Sets are much(!) more efficient than lists for testing whether an element is in a set or a list.
If you don’t want duplicate items but still need to keep the order of the elements, definitely use LinkedHashSet.

Question 17

The Map interface has three concrete subclasses. What are they?

Answer 17

The three concrete map classes are HashMap, LinkedHashMap, and TreeMap.

Question 18

What does these methods in the Map interface do?
clear()
containsKey(key: Object)

Answer 18

clear() : Removes all entries from this map.

containsKey(key: Object) : Returns true if this map contains an entry for the specified key.

Question 19

What does these methods in the Map interface do?
containsValue(value: Object)
entrySet()

Answer 19

containsValue(value: Object) : Returns true if this map maps one ore more keys to the specified value.
entrySet() : Returns a set consisting of the entries in this map.

Question 20

What does these methods in the Map interface do?
get(key: Object)
isEmpty()

Answer 20

get(key: Object) : Returns the value for the specified key in this map.
isEmpty() : Returns true if this map contains no entries.

Question 21

What does these methods in the Map interface do?
keySet()
put(key: K, value: V)
putAll(m: Map[? extends K, ? extends V>)

Answer 21

keySet() : Returns a set consisting of the keys in this map.
put(key: K, value: V) : Puts an entry into this map.
putAll(m: Map[? extends K, ? extends V>) : Adds all the entries from m to this map.

Question 22

What does these methods in the Map interface do?
remove(key: Object)
size()
values()

Answer 22

remove(key: Object) : Removes the entries for the specified key.
size() : Returns the number of entries in this map.
values() : Returns a collection consisting of the values in this map.

Question 23

What is the difference between HashMap, LinkedHashMap, and TreeMap?

Answer 23

Similar to the differences between the Set classes.
HashMaps efficient for locating a value, inserting an entry, and deleting an entry.
LinkedHashMap supports an ordering of the entries in the map. Entries in a LinkedHashMap can be retrieved either in the order in which they were inserted into the map (insertion order) or in the order in which they were last accessed (access order). To construct a LinkedHashMap with the access order (because the default is insertion order), use LinkedHashMap(initialCapacity, loadFactor, true).
TreeMap is efficient for traversing the keys in a sorted order.

Question 24

How do you decide whether to use a HashMap, LinkedHashMap, or TreeMap?

Answer 24

If you don’t need to maintain an order in a map when updating it, use a HashMap. When you need to maintain the insertion order or access order in the map, use a LinkedHashMap. When you need the map to be sorted on keys, use a TreeMap.

Question 25

Which of the following data types does not implement the Collection interface?

A. HashSet
B. TreeSet
C. ArrayList
D. LinkedList
E. Map

Answer 25

E. Map

Question 26

Which of the data types below could be used to store elements in their natural order based on the compareTo method?

A. HashSet
B. TreeSet
C. LinkedHashSet
D. Collection
E. Set

Answer 26

B. TreeSet

Question 27

If two objects o1 and o2 are equal, what are the values for o1.equals(o2) and o1.hashCode() == o2.hashCode()?

A. true true
B. true false
C. false true
D. false false

Answer 27

A. true true

Question 28

What is the output for the following code?

import java.util.*;
public class Test {
    public static void main(String[] args) {
        Set[A> set = new HashSet[A>();
        set.add(new A());
        set.add(new A());
        set.add(new A());
        set.add(new A());
        System.out.println(set);
    }
}

class A  {
    int r = 1;

public String toString() {
    return r + "";
}

public boolean equals(Object o) {
    return this.r == ((A)o).r;
}

public int hashCode() {
    return r;
} }

A. [1]
B. [1, 1]
C. [1, 1, 1]
D. [1, 1, 1, 1]

Answer 28

A. [1]

Question 29

What is the output for the following code?

import java.util.*;
public class Test {
    public static void main(String[] args) {
        Set[A> set = new HashSet[A>();
        set.add(new A());
        set.add(new A());
        set.add(new A());
        set.add(new A());
        System.out.println(set);
    }
}

class A  {
    int r = 1;

public String toString() {
    return r + "";
}

public int hashCode() {
    return r;
} }

A. [1]
B. [1, 1]
C. [1, 1, 1]
D. [1, 1, 1, 1]

Answer 29

D. [1, 1, 1, 1]

Question 30

What is the output for the following code?

import java.util.*;
public class Test {
    public static void main(String[] args) {
        Set[A> set = new HashSet[A>();
        set.add(new A());
        set.add(new A());
        set.add(new A());
        set.add(new A());
        System.out.println(set);
    }
}

class A  {
    int r = 1;

public String toString() {
    return r + "";
}

public boolean equals(Object o) {
    return this.r == ((A)o).r;
} }

A. [1]
B. [1, 1]
C. [1, 1, 1]
D. [1, 1, 1, 1]

Answer 30

D. [1, 1, 1, 1]

Question 31

Which of the following data types have iterators?

A. HashSet
B. TreeSet
C. ArrayList
D. LinkedList
E. LinkedHashSet

Answer 31

All of them.

Explanation: The Collection interface has the iterator() method to return an iterator from a collection.

Question 32

The output of the following code is ___

LinkedHashSet[String> set1 = new LinkedHashSet[String>();
set1.add(“New York”);
LinkedHashSet[String> set2 = (LinkedHashSet[String>)(set1.clone());
set1.add(“Atlanta”);
set2.add(“Dallas”);
System.out.println(set2);

A. [New York]
B. [New York, Atlanta]
C. [New York, Atlanta, Dallas]
D. [New York, Dallas]

Answer 32

D. [New York, Dallas]

Question 33

Analyze the following code:

import java.util.*;

public class Test {
  public static void main(String[] args) {
    HashSet[String> set1 = new HashSet[String>();
    set1.add("red");
    Set set2 = set1.clone();
  }
}

A. Line 5 is wrong because a HashSet object cannot be cloned.
B. Line 5 has a compile error because set1.clone() returns an Object. You have to cast it to Set in order to compile it.
C. The program will be fine if set1.clone() is replaced by (Set)set1.clone()
D. The program will be fine if set1.clone() is replaced by (Set)(set1.clone())
E. The program will be fine if set1.clone() is replaced by (HashSet)(set1.clone())

Answer 33

B, D, and E are true

Question 34

Which of the following is correct to perform the set union of two sets s1 and s2?

A. s1.union(s2)
B. s1 + s2
C. s1.addAll(s2)
D. s1.add(s2)

Answer 34

C. s1.addAll(s2)

Question 35

Which of the following is correct to perform the set difference of two sets s1 and s2?

A. s1.difference(s2)
B. s1 - s2
C. s1.subtract(s2)
D. s1.removeAll(s2)

Answer 35

D. s1.removeAll(s2)

Question 36

Analyze the following code.

import java.util.*;

public class Test {
  public static void main(String[] args) throws Exception {
    Set[String> set = new TreeSet[String>();

set. add("Red");
set. add("Green");
set. add("Blue");

System.out.println(set.first());   } }

A. The program displays Red
B. The program displays Blue
C. The program displays Green
D. The program may display Red, Blue, or Green.
E. The program cannot compile, because the first() method is not defined in Set.

Answer 36

E. The program cannot compile, because the first() method is not defined in Set.
Explanation: first() is defined in TreeSet. To compile this program, replace Set[String> set = new TreeSet[String>() with TreeSet[String> set = new TreeSet[String>().

Question 37

Analyze the following code.

import java.util.*;

public class Test {
  public static void main(String[] args) throws Exception {
    TreeSet[String> set = new TreeSet[String>();

set. add("Red");
set. add("Green");
set. add("Blue");

System.out.println(set.last());   } }

A. The program displays Red
B. The program displays Blue
C. The program displays Green
D. The program may display Red, Blue, or Green.
E. The program cannot compile, because the first() method is not defined in Set.

Answer 37

A. The program displays Red

Question 38

Which of the following are correct methods in Map?

A. put(Object key, Object value)
B. put(Object value, Object key)
C. get(Object key)
D. get(int index)

Answer 38

A and C are correct

Question 39

Suppose your program frequently tests whether a student is in a soccer team, what is the best data structure to store the students in a soccer team?

A. ArrayList
B. HashSet
C. LinkedList
E. Vector

Answer 39

B. HashSet

Question 40

Suppose your program frequently tests whether a student is in a soccer team and also need to know the student?s information such as phone number, address, and age, what is the best data structure to store the students in a soccer team?

A. ArrayList
B. HashMap
C. TreeMap
D. LinkedList
E. HashSet

Answer 40

B. HashMap

Question 41

Analyze the following code:

public class Test {
  public static void main(String[] args) {
    Map[String, String> map = new HashMap[String, String>();
    map.put("123", "John Smith");
    map.put("111", "George Smith");
    map.put("123", "Steve Yao");
    map.put("222", "Steve Yao");
  }
}

A. After all the four entries are added to the map, “123” is a key that corresponds to the value “John Smith”.
B. After all the four entries are added to the map, “123” is a key that corresponds to the value “Steve Yao”.
C. After all the four entries are added to the map, “Steve Yao” is a key that corresponds to the value “222”.
D. After all the four entries are added to the map, “John Smith” is a key that corresponds to the value “123”.
E. A runtime error occurs because two entries with the same key “123” are added to the map.

Answer 41

The correct answer is B
Explanation: The signature of the put method is put(key, value). So the first parameter in the put method is the key. When a new entry with the same key is added to the map, the existing entry with the same key is replaced by the new entry.