Java Reference
In-Depth Information
A
NSWERS
TO
S
ELF
-T
EST
Q
UESTIONS
1.
2301506.
"Java".hashCode()
has the same value.
2.
19
3.
"x"
4.
Since the implementation defines both the hash table and the dictionary entry, you have a choice as to where to
add a field to indicate the state of a location in a hash table. You could add a field having three states to each table
location, but you really need only a boolean field, since a
null
location is empty. If the field is true, the location is
occupied; if it is false, it is available.
Adding a similar data field to the dictionary entry instead of to the hash table leads to a cleaner implementation.
As before, if the table location is
null
, it is empty. If the entry's field is true, the location is occupied; if it is false, it
is available. Note that the implementation that appears in the next chapter uses this scheme.
5.
13. Since 13 is both prime and the modulo base in
h
1
, the probe sequence can reach all locations in the table
before it repeats.
6.
3, 8, 0, 5, 10, 2, 7, 12, 4, 9, 1, 6, 11, 3, ...
7.
hashTable[0]
→ 20
hashTable[1]
→
6
→
31
hashTable[2]
is
null
hashTable[3]
is
null
hashTable[4]
→
4
→
14
→
29
8.
The
add
algorithm is the same as the one given in Segment 21.25, but it uses a different search of a chain.
Regardless of whether the chain is sorted, you stop the search as soon as you find the desired search key.
However, if the key is not in the chain, you have to search an entire unsorted chain to learn this. If the chain is
sorted, you can stop the search when you reach the point where the key should have occurred if it were present.
9.
No. Suppose that
a
,
b
,
c
, and
d
are search keys in sorted order in the hash table. With separate chaining,
b
and
d
might appear in one chain while the other keys appear in another. Traversing the chains in order will not visit the
keys in sorted order. The same is true of open addressing when traversing the occupied array locations.
