Chapter 9
Section 9.1
1.
Set s = new HashSet(); //creates new HashSet
s.add("hello"); //adds "hello" to s
s.add("bye"); //adds "bye" to s
s.addAll(s); //returns false, as all elements of s already exist in s.
Set t = new TreeSet(); //creates new TreeSet
t.add("123"); //adds "123" to t
s.addAll(t); //adds all elements of t to s, namely "123" is added to s
System.out.println(s.containsAll(t)); //Prints "true", as all elements of t are in s
System.out.println(t.containsAll(s)); //Prints "false", as none of the s elements are in t
System.out.println(s.contains("ace")); //false, the element has been added no where
System.out.println(s.contains("123")); //true, the element was added from t to s
s.retainAll(t); //removes all elements not in common to the sets, leaving "123"
System.out.println(s.contains("123")); //true, as stated above
t.retainAll(s); //Set intersection of what are now identical sets, therefore unchanged.
System.out.println(t.contains("123")); //true, as stated above
2.
Set extends the Collection interface. Basically, a Set is a collection that contains no duplicate elements.
3.
A set cannot have duplicate elements, implementing the mathematical set abstraction. A list may contain duplicate elements. Thus restrictions are placed on the add and addAll methods in the Set. The List interface adds the following additional methods: add(int, Object), get(int), indexOf(Object), listIndexOf(Object), listIterator(), listIterator(int), remove(int), set(int, Object), subList(int, int)
4.
setAcopy is needed to fill it with a copy of the elements in setA. “setAcopy = setA” is not an option because it would not perform a deep copy of the set.
Section 9.2
1.
a. ISBN Number. There may be multiple textbooks with the same year, publisher, year, or author, but the ISBN would be unique to the particular book.
b. player’s name, which should be unique, whereas the others could be non-unique. The name is not necessarily unique.
c. Model number, because it is unique, but there could be many computer models with the same manufacturer, processor, memory, or disk size.
d. Course ID, because many courses can have the same department, title, section number, days, time, or room.
Section 9.3
1.
If the table has no free spaces, the loop will never terminate.
2.
Using open addressing and linear probing:
Using chaining:
3.The following sequence will create the table shown:
insert(6)
insert(14)
insert(24)
insert(20)
4.
Searching for Sam and Pete would fail; search algorithm would incorrectly conclude that the item is not in the table (when finding the null value in position [0], after a linear probing search). The search for Harry would not be affected, since it is stored in the position hashCode()%5.
To solve this problem, deleted should be stored instead of null, so that the linear probing algorithm knows that it should keep looking.
5.
The item being inserted might already be in the table, but preceded in the search by an item that was deleted.
6.
Open addressing:
Expected number of comparisons:
Storage requirements: n = 500
Chaining:
To obtain the same performance, we want c to be 1.5:
Storage requirements:
This shows how the benefits of using chaining. In the example, when using chaining the same performance is obtained for approximate the same storage requirements (500 vs. 502), even when the load factor is twice than that for the open addressing case (50% full vs. 100%full). In other words, for the same performance and storage requirements, using chaining allows 100% tilization, whereas open addressing would yield the same results for only 50% utilization.
Section 9.4
1.
Assuming the new table size is 11:
[0]
[1]
[2]24
[3]14
[4]
[5]
[6]6
[7]
[8]
[9]20
[10]
Section 9.5
1.The Map.Entry interface is needed to provide access to the key and value from the internal Entry objects that are in the Set view returned by the entrySet method. The entrySet actually returns objects of the private inner class. By having this class implement the Map.Entry interface client classes can access the key and value, but the rest of the internal structure remains hidden, and the implementer of the Map class is free to choose and modify this internal class. Thus information hiding is preserved.
Section 9.6
1.Since the map stores references to the value, we need a unique copy of each value to be stored in the map for each member of the alphabet. If we did not create a clone, the append of the next bit would be applied to the same physical object, thus all members of the alphabet would have the same code.