[C++] Write a program implementing chained hashing as described in Section 12-3. You can use the prototypes at the author's web site.

Here is the node class from the text is talking about that you can use:

https://drive.google.com/open?id=0B2ejYGF1LEE0SXRZai0wanBZMm8

Here is another node class from the author's website for this chapter. I don't know if it will help any:

https://drive.google.com/open?id=0B2ejYGF1LEE0ekJqeUFxUE13T00

123 CHAINED HASHING In open-address hashing, a collision is handled by probing the array for an unused position. Each array component can hold just one entry. When the array is full, no more items can be added to the table. We could handle this problem by resizing the array and rehashing all the entries, placing each entry in a new, larger array. But this would require a careful choice of the new size and proba- bly would require each entry to have a new hash value computed. Another approach is to use a different collision resolution method called chained bashing In chained hashing, also called chaining, each component of the hash table's aray can hold more than one entry. As with all bashing, we still hash the key of each entry to obtain an ary index. But if there is a collision, we don't worry too much. We simply placc the new catry in its proper array component along with other entries that happened to hash to the same array index. How does chaining place more than one entry in each component of the amay? The answer is that each array component must have some underlying structure. The most common structure that you will see for the array's components is to have each data[i] be a head pointer for a linked list. The nodes of the linked list each have an item that is the RecordType of thc table, as diagrammed bere: data Record whose key hashes Record whose Reoord whose key hashes key hashes that hashes that hashes that hashes 616 Chater 12/Seanchirg In this scheme, all the records that hash to location i are placed on the linked list, which has its head pointer stored in datai). To maintain the linked lists, we can usc the template version of our node class (from Section 6.4). With this approach, the table class definition is shown in Figure 12.7 In the figure we have included the file node2.h from Figure 64 on page 32 to provide the node class. We also have defined a static member constan called TABLE SIZE, which determines the size of the table's array. We used the name TABLE SIZE rather than CAPACITY since "CAPACITY Suggests a limit to the namber of entries-but in fact, the chaining hash table ean bold more than TABLE SIZE entries Definifon of the Table Template Class Using Cheining and the Linkod-List Tccolkt A Template Class Definition #include // Provides size.t include "node2.h" Provides the node type, from Figure 6.4 on page 321 nanespace nain savitch 128 template class table I MEMBER CONSTANT-See Appendix E if this faNs to compvle. static const std:size_t TABLE-SIZE = 811; // CONSTRUCTORS AND DESTRUCTOR tablec; table(const tablc& source) tabe I MODIFICATION MEMBER FUNCTIONS void insert (const RecordType& entry): void remove(int key); void operator -(const table& source); T CONSTANT MEMBER FUNCTIONS void find(int key, bool& found, RecordType& result) const bool is_present int key) const; std::size t ze const return total records; h nainsavitch.68::node data[TABLE_SIZE]: std::size t total_records; /I HELPER MEMBER FUNCTION std::sizet hash int key) const; Each component of the array is a heed pointer for a linked Wst. Time AnalysefHa hing 617 In our example, the table size is 811, so that the data array consists of 811 tead pointers for 811 linked lists. Each list is a linked list where the nodes contain RecordType values. Our class definition has one other private member variable, total records, which keeps track of the total number of records in all 811 linked lists. You can complete this implementation yourself. 123 CHAINED HASHING In open-address hashing, a collision is handled by probing the array for an unused position. Each array component can hold just one entry. When the array is full, no more items can be added to the table. We could handle this problem by resizing the array and rehashing all the entries, placing each entry in a new, larger array. But this would require a careful choice of the new size and proba- bly would require each entry to have a new hash value computed. Another approach is to use a different collision resolution method called chained bashing In chained hashing, also called chaining, each component of the hash table's aray can hold more than one entry. As with all bashing, we still hash the key of each entry to obtain an ary index. But if there is a collision, we don't worry too much. We simply placc the new catry in its proper array component along with other entries that happened to hash to the same array index. How does chaining place more than one entry in each component of the amay? The answer is that each array component must have some underlying structure. The most common structure that you will see for the array's components is to have each data[i] be a head pointer for a linked list. The nodes of the linked list each have an item that is the RecordType of thc table, as diagrammed bere: data Record whose key hashes Record whose Reoord whose key hashes key hashes that hashes that hashes that hashes 616 Chater 12/Seanchirg In this scheme, all the records that hash to location i are placed on the linked list, which has its head pointer stored in datai). To maintain the linked lists, we can usc the template version of our node class (from Section 6.4). With this approach, the table class definition is shown in Figure 12.7 In the figure we have included the file node2.h from Figure 64 on page 32 to provide the node class. We also have defined a static member constan called TABLE SIZE, which determines the size of the table's array. We used the name TABLE SIZE rather than CAPACITY since "CAPACITY Suggests a limit to the namber of entries-but in fact, the chaining hash table ean bold more than TABLE SIZE entries Definifon of the Table Template Class Using Cheining and the Linkod-List Tccolkt A Template Class Definition #include // Provides size.t include "node2.h" Provides the node type, from Figure 6.4 on page 321 nanespace nain savitch 128 template class table I MEMBER CONSTANT-See Appendix E if this faNs to compvle. static const std:size_t TABLE-SIZE = 811; // CONSTRUCTORS AND DESTRUCTOR tablec; table(const tablc& source) tabe I MODIFICATION MEMBER FUNCTIONS void insert (const RecordType& entry): void remove(int key); void operator -(const table& source); T CONSTANT MEMBER FUNCTIONS void find(int key, bool& found, RecordType& result) const bool is_present int key) const; std::size t ze const return total records; h nainsavitch.68::node data[TABLE_SIZE]: std::size t total_records; /I HELPER MEMBER FUNCTION std::sizet hash int key) const; Each component of the array is a heed pointer for a linked Wst. Time AnalysefHa hing 617 In our example, the table size is 811, so that the data array consists of 811 tead pointers for 811 linked lists. Each list is a linked list where the nodes contain RecordType values. Our class definition has one other private member variable, total records, which keeps track of the total number of records in all 811 linked lists. You can complete this implementation yourself