1
Homework #5
a) (5 points) Modify the chained hash table from the book (chtbl.h and chtbl.c) so that it
auto-grows when its load factor exceeds a given value. (Auto-growing means increasing the
number of buckets in the hash table then rehashing the existing elements.)
Begin by modifying the chtbl_init function from the book to have the following prototype:
int chtbl_init(CHTbl *htbl,
int buckets,
int (h)(const void key),
int (match)(const void key1, const void *key2),
void (destroy)(void data),
double maxLoadFactor,
double resizeMultiplier);
The htbl, buckets, h, match, and destroy parameters have the same meaning as defined in
the book. The maxLoadFactor parameter is the maximum load factor the hash table should be
allowed to reach before being auto-resized. The resizeMultiplier parameter is the amount
by which the number of buckets should be multiplied when a resize occurs (this value must be
greater than 1). The maxLoadFactor and resizeMultiplier values should be stored in new
fields in the CHTbl struct.
Next, modify the code in the chtbl_insert function as follows:
- Resize the hash table when the load factor exceeds the maximum load factor. The
new size of the hash table should be the old size times the resizeMultiplier. All
elements currently in the hash table must be rehashed and placed into new buckets. - Change the method by which hash codes are mapped to buckets to use the
multiplication method instead of the division method.
Modify any other parts of CHTbl as needed. Note that removing items from the hash table
should not cause the number of buckets in the table to shrink.
b) (3 points) Implement a program that demonstrates inserts and lookups with an auto-resizing
hash table. This program should initialize the hash table to a small number of buckets then
begin inserting integers until a resize occurs. After each insert the program should output the
following information:
• Number of buckets in the table
• Number of elements in the table
• The table’s load factor
• The table’s max load factor
• The table’s resize multiplier
For example, if the hash table was initialized to start with 5 buckets, a max load factor of 0.5, and
a resize multiplier of 2.0, the following output should be displayed as elements are inserted:
CSE-40049
2
buckets 5, elements 1, lf 0.20, max lf 0.5, resize multiplier 2.0
buckets 5, elements 2, lf 0.40, max lf 0.5, resize multiplier 2.0
buckets 10, elements 3, lf 0.33, max lf 0.5, resize multiplier 2.0
Note that in the 3rd line of output the number of buckets has doubled. This happened because
the load factor that would result from inserting the 3rd element would have caused the load
factor to exceed the max load factor (0.5) so the hash table was auto-resized.
After the resize occurs, your program must demonstrate successfully looking up a value that
was inserted before the resize and must also demonstrate unsuccessfully looking up a value that
does not exist in the table.
c) (1 point) Answer the following questions: - What is the Big-O execution performance of an insert now that auto-resizing can take
place? - Why do you think you were required to change chtbl_insert to use the
multiplication method instead of the division method to map hash codes to buckets?
d) (1 point) Make sure your source code is well-commented, consistently formatted, uses no
magic numbers/values, follows programming best-practices, and is ANSI-compliant.
Turn in all source code, program output, diagrams, and answers to questions in a single
Word or PDF document.