Java Reference
In-Depth Information
IN THEORY
20.7
An alternative collision resolution strategy is to define a sequence,
, where
Fi
()
=
R i
R 0
=
0
and
R 1 R 2
,
,
,
R M 1
is a random permu-
-
tation of the first
M 1
-
integers (recall that the table size is M ).
a.
Prove that under this strategy, if the table is not full, the collision
can always be resolved.
b.
Would this strategy be expected to eliminate primary clustering?
c.
Would this strategy be expected to eliminate secondary clustering?
d.
If the load factor of the table is
λ
, what is the expected time to
perform an insertion?
e.
Generating a random permutation using the algorithm in Section 9.4
involves a large number of (expensive) calls to a random number
generator. Give an efficient algorithm to generate a random-looking
permutation that avoids calling a random number generator.
If rehashing is implemented as soon as the load factor reaches 0.5,
when the last element is inserted the load factor is at least 0.25 and at
most 0.5. What is the expected load factor? In other words, is it true
or false that the load factor is 0.375 on average?
20.8
When the rehashing step is implemented, you must use O ( N ) probes
to reinsert the N elements. Give an estimate for the number of probes
(i.e., N or 2 N or something else). ( Hint: Compute the average cost of
inserting in the new table. These insertions vary from load factor 0 to
load factor 0.25.)
20.9
Under certain assumptions, the expected cost of an insertion in a hash
table with secondary clustering is given by 1/(1 -
20.10
).
Unfortunately, this formula is not accurate for quadratic probing.
However, assuming that it is,
a.
λ
) -
λ
- ln(1 -
λ
What is the expected cost of an unsuccessful search?
b.
What is the expected cost of a successful search?
A quadratic probing hash table is used to store 10,000 String objects.
Assume that the load factor is 0.4 and that the average string length
is 8. Determine
a.
20.11
The hash table size
b.
The amount of memory used to store the 10,000 String objects
c.
The amount of additional memory used by the hash table
d.
The total memory used by the hash table
e.
The space overhead
Search WWH ::




Custom Search