COSC 2415 Data Structures
Bob Comer, Professor of Computer Studies
Program 7 - Hash Tables
Be sure to read through Chapter 12 section 12.7 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.
Note: the chained-hashing version of the Table class really should have a destructor, copy constructor and overloaded assignment operator. You do not need to write these functions. You should be able to do this assignment and test your code without these functions.
Neither of these implementations has a delete operation to delete an entry. For each implementation, do the following.
void erase(int key); Preconditions: key >= 0 Postconditions: If a record with the specified key exists in the table, then that record has been removed; otherwise the table is unchanged.
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
Hints:
void Table::print( ) { cout << "The hash table is: " << endl; cout << "Index Key Data" << endl; for( int i=0; i < CAPACITY; i++ ) { cout << setw(5) << i << setw(5) << table[i].key; if ( table[i].key != -1 ) cout << setw(8) << table[i].data; cout << endl; } cout << endl; }Be sure to remove this function before you turn in your assignment.