Hashtable

-table:List*

-size:int

-----------------------------------------------------------------------------------------------------------------

-hash(key:string) : int {query}

+HashTable(s:int):

+~HashTable():

+clear():void

+insert(key:string) : int

+remove(key:string) : int

+find(key:string) : boolean

+isFull():bool{query}

+isEmpty():bool{query} +print():void{query}

table is a array of dynamic linked list objects 

Hash function converts string to hash value an integer.

Use the above UML diagram and descriptions below to write a class that implements a Hash table. Your implementation should use open chaining to resolve collisions. You may provide additional class attributes, as you see fit, to complete the class.

The above class has the following private attributes:

table: This is a pointer to the object's dynamically allocated hash table. Used to create an array of Linked List objects.

size - stores the number of elements in the hash table ( the capacity ).

hash - the hash function. It accepts the key string and returns the hash value.

The class has the following public attributes:

constructor - accepts an integer argument used to determine the number of elements in the hash table. Dynamically allocates the hash table.

destructor - deallocates all dynamically allocated memory.

insert - insert's it's argument into the hash table. calls the hash function to obtain an appropriate hash address. Returns 0 if successful, -1 otherwise.

remove - removes the first key matching it's argument from the hash table. Returns 0 if successful, -1 otherwise.

find - returns true if a key matching it's argument is found, false otherwise.

clear - resets the object to it's initial state.

isFull - returns true if the structure is full, false otherwise.

isEmpty - returns true if the structure has no keys, false otherwise.

print - displays all the keys currently stored in the structure.

Possible sample output from the print method:

Bucket 0: Head -> white->snow->And->went,->go.->NULL

Bucket 1:Head -> was->was->NULL

Bucket 2: Head -> a->fleece->as->lamb->sure->to->NULL

Bucket 3:Head -> lamb->It's->that->that->NULL

Bucket 4:Head -> Mary->little->everywhere->Mary->NULL

The above is what the 5-element hash table looks like after inserting "Mary had a little lamb. It's fleece was white as snow And everywhere that Mary went, that lamb was sure to go."

Hints:

Here's an example of code you might use to invoke the find method from one of the List objects in the table array: return table[hash(key)].find(key); If this makes no sense to you, review arrays of objects from Chapter 13 of the text from CS2370.

You need to come up with some scheme for converting letters to characters. In my solution, I found the sum of the ascii codes for each key and then ran modulus on that. Whatever scheme you come with is up to you.

driver.cpp is the file used to produce the sample output.

#include "HashTable.h" #include #include using namespace std; int main() { HashTable h(5); h.insert("Mary"); h.insert("had"); h.insert("a"); h.insert("little"); h.insert("lamb."); h.insert("It's"); h.insert("fleece"); h.insert("was"); h.insert("white"); h.insert("as"); h.insert("snow"); h.insert("And"); h.insert("everywhere"); h.insert("that"); h.insert("Mary"); h.insert("went,"); h.insert("that"); h.insert("lamb"); h.insert("was"); h.insert("sure"); h.insert("to"); h.insert("go."); h.print(); return 0; }