Chapter 23 - Sets and Maps Flashcards

1
Q

What is a set?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is a map?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Describe the Set interface.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is a HashSet?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is the hashCode method?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

How do you create a HashSet?

A

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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is a LinkedHashSet?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

How do you decide whether to use LinkedHashSet or HashSet?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Describe TreeSet.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

How do you create a TreeSet?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

A

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

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

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

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

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

A

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

18
Q

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

A

clear() : Removes all entries from this map.

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

19
Q

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

A

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.

20
Q

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

A

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

21
Q

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

A

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.

22
Q

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

A

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.

23
Q

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

A

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.

24
Q

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

A

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.

25
Q

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

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

E. Map

26
Q

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
A

B. TreeSet

27
Q

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

A

A. true true

28
Q

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]

A

A. [1]

29
Q

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]

A

D. [1, 1, 1, 1]

30
Q

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]

A

D. [1, 1, 1, 1]

31
Q

Which of the following data types have iterators?

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

All of them.

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

32
Q

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]

A

D. [New York, Dallas]

33
Q

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())

A

B, D, and E are true

34
Q

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)

A

C. s1.addAll(s2)

35
Q

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)

A

D. s1.removeAll(s2)

36
Q

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.

A

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>().

37
Q

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.

A

A. The program displays Red

38
Q

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)

A

A and C are correct

39
Q

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

A

B. HashSet

40
Q

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
A

B. HashMap

41
Q

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.

A

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.