Java Reference
In-Depth Information
The hash function returns an
int
. Because intermediate calculations allow
overflow, the local variable should check that the result of the mod opera-
tion is nonnegative to avoid risking an out-of-bounds return value.
1.
The performance of a probing table degrades severely as the load factor
approaches 1.0. Do not let this happen. Rehash when the load factor
reaches 0.5.
2.
The performance of all hashing methods depends on using a good hash
function. A common error is providing a poor function.
3.
The quadratic probing hash table is available for your perusal.
HashSet.java
Contains the implementation of the
HashSet
class.
HashMap.java
Contains the implementation of the
HashMap
class.
IN SHORT
20.1
What are the array indices for a hash table of size 11?
What is the appropriate probing table size if the number of items in
the hash table is 10?
20.2
Explain how deletion is performed in both probing and separate
chaining hash tables.
20.3
What is the expected number of probes for both successful and
unsuccessful searches in a linear probing table with load factor 0.25?
20.4
Given the input {4371, 1323, 6173, 4199, 4344, 9679, 1989}, a fixed
table size of 10, and a hash function
H
(
X
) =
X
mod 10, show the
resulting
a.
20.5
Linear probing hash table
b.
Quadratic probing hash table
c.
Separate chaining hash table
Show the result of rehashing the probing tables in Exercise 20.5.
Rehash to a prime table size.
20.6
Search WWH ::
Custom Search