Chapter 27 Check Point Questions
Section 27.2
▼27.2.1
What is a hash function? What is a perfect hash function?
What is a collision?
Section 27.3
▼27.3.1
What is a hash code? What is the hash code for Byte, Short, Integer, and Character?
▼27.3.2
How is the hash code for a Float object computed?
▼27.3.3
How is the hash code for a Long object computed?
▼27.3.4
How is the hash code for a Double object computed?
▼27.3.5
How is the hash code for a String object computed?
▼27.3.6
How is a hash code compressed to an integer representing the index in a hash table?
▼27.3.7
If N is a value of the power of 2, is N / 2 same as N >> 1?
▼27.3.8
If N is a value of the power of 2, is m % N same as m & (N - 1) for any integer m?
▼27.3.9
What is new Integer("-98").hashCode() and
what is "ABCDEFGHIJK".hashCode()?
Section 27.4
▼27.4.1
What is open addressing? What is linear probing? What is quadratic probing? What is double hashing?
▼27.4.2
Describe the clustering problem for linear probing.
▼27.4.3
What is secondary clustering?
▼27.4.4
Show the hash table of size 11 after inserting entries with keys
34, 29, 53, 44, 120, 39, 45, and 40, using linear probing.
▼27.4.5
Show the hash table of size 11 after inserting entries with keys 34, 29, 53,
44, 120, 39, 45, and 40, using quadratic probing.
▼27.4.6
Show the hash table of size 11 after inserting entries with keys 34, 29, 53, 44, 120, 39, 45, and 40, using double hashing with the following functions:
h(k) = k % 11; h'(k) = 7 - k % 7;
Section 27.5
▼27.5.1
Show the hash table of size 11 after inserting entries with the
keys 34, 29, 53, 44, 120, 39, 45, and 40, using separate chaining.
Section 27.6
▼27.6.1
What is load factor? Assume the hash table has the initial size 4
and its load factor is 0.5; show the hash table after inserting entries
with the keys 34, 29, 53, 44, 120, 39, 45, and 40, using linear probing.
▼27.6.2
Assume the hash table has the initial size 4 and its load factor is 0.5; show the hash table after inserting entries with the keys 34, 29, 53, 44, 120, 39, 45, and 40, using quadratic probing.
▼27.6.3
Assume the hash table has the initial size 4 and its load factor is 0.5; show the hash table after inserting entries with the keys 34, 29, 53, 44, 120, 39, 45, and 40, using separate chaining.
Section 27.7
▼27.7.1
What is 1 << 30 in line 8 in Listing 27.2? What are the integers resulted from 1 << 1, 1 << 2, and 1 << 3?
▼27.7.2
What are the integers resulted from 32 >> 1, 32 >> 2, 32 >> 3, and 32 >> 4?
▼27.7.3
In Listing 27.2, will the program work if LinkedList is replaced by ArrayList? In Listing 27.2, how do you replace the code in lines 56-59 using one line of code?
▼27.7.4
Describe how the put(key, value) method is implemented in the MyHashMap class.
▼27.7.5
In Listing 27.2, the supplementalHash method is declared static, can the hash method be declared static?
▼27.7.6
Show the output of the following code.
MyMap<String, String> map = new MyHashMap<>(); map.put("Texas", "Dallas"); map.put("Oklahoma", "Norman"); map.put("Texas", "Austin"); map.put("Oklahoma", "Tulsa"); System.out.println(map.get("Texas")); System.out.println(map.size());
▼27.7.7
If x is a negative int value, will x & (capacity - 1) be negative?
Section 27.8
▼27.8.1
Why can you use a foreach loop to traverse the elements in a set?
▼27.8.2
Describe how the add(e) method is implemented in the MyHashSet class.
▼27.8.3
Can lines 100-103 in Listing 27.4 be removed?
▼27.8.4
Implement the remove() method in lines 150-152?