ITSE 2445 - Data Structures and
ITSE 2445 Data Structures
Bob Comer, Professor of Computer Studies

Be sure to read through Chapter 12 of the textbook before starting this assignment.

Below you will find C++ code for two different implementations of a hash table.

The first implementation is a simple hash table that uses linear probing to resolve collisions. In this version the data is stored directly in an array, so the number of entries is limited by the size of the array.

The second implementation uses chained hashing to resolve collisions. Each element in the array is a pointer to a linked list that stores all data that hashes to that index. So the number of entries in the table is limited only by the amount of memory that you can dynamically allocate.

Neither of these implementations has a delete operation to delete an entry. For each implementation, do the following.

• Study the implementation and your textbook to be sure that you understand how it works.
• Add a function that deletes an entry as follows. Be sure to include documentation for your function in the class header file.

       void erase(int key)
       Postcondition: If a record with the specified key exists in the table, then
       that record has been removed; otherwise the table is unchanged.
  

• Modify the driver program so that you can test your delete function.

Submit all your code for each of the two implementations.

Sample code. Note that depending on your browser settings, the code may not display correctly in your browser. But you should be able to copy the code to your local machine and view it in your C++ editor.

Hash Table with Linear Probing

Driver program drv_hwlp.cpp

Header hash_lp.h

Implementation hash_lp.cpp

Hash Table with Chained Hashing

Driver program drv_hwch.cpp

Header hash_chn.h

Implementation hash_chn.cpp

Hint: the easiest node to delete in a linked-list is the head node. Instead of deleting a node in the middle of the list, you can copy the data from the head node into the node to be deleted, then delete the head node.