Data Structures Demystified (Demystified)

2017-07-07 02:10:07

Hashtable Using C++

Now that you understand how the components of the Hashtable class work, it is time to assemble them into a working C++ application. I organized the application into three files: the HashtableDemo.cpp file that contains the application; the HashTable.h file that contains the definitions of the metadata structure and the Hashtable class, and the Hashtable . cpp file that contains the implementation of member functions. You ll find all three files in the code at the end of this section. In this section, we ll focus on how to use the Hashtable class in an application. You already learned how member functions and data members of the Hashtable class work.

The application begins by declaring an instance of the Hashtable class and assigning reference to it to the hashtable pointer. You then declare two char arrays using the SIZE_KEY and SIZE_VALUE macro defined to set the size of the array. These arrays store strings that contain the key and the value of data that you ll be entering into the hashtable.

Next , the strcpy () function is called to copy the key and value to the key and value arrays. Before you can insert these into the hashtable, you must first determine if the key already exists in the hashtable by calling the contains() member function of the Hashtable class. The contains() member function returns a Boolean true if the key already exists; otherwise , a Boolean false is returned. Notice the not operator ( ! ) reverses the logic of the return value. You do this to execute statements contained within the if statement.

If the key doesn t exist in the hashtable, then the application displays a message on the screen telling that the key and value are being inserted. The actual insertion occurs by calling the put() member function of the Hashtable class. The put() function requires that the key and the value be passed as arguments.

This process is repeated in order to insert two additional key/value pairs into the hashtable. Each of these is also displayed on the screen as shown here. Figure 11-5 illustrates the hashtable.

Figure 11-5: The hashtable created after the put() function is called for the last time

Adding node - key: 389 value: Mary Adding node - key: 415 value: Henry Adding node - key: 999 value: Joe

Once all three new entries have been inserted into the hashtable, the application calls the displayAll() function. The displayAll() function is a stand-alone function and not a member of the Hashtable class. Its sole purpose is to display the content of the hashtable. The displayAll() function is defined beneath the main() function in this example.

Here s what is displayed on the screen when this function is called:

Current nodes in hashtable: key: 415 value: Henry key: 999 value: Joe key: 389 value: Mary

The application then calls the remove() member function of the Hashtable class to remove the entry that has 415 as its key. Once again, the displayAll() function is called to demonstrate that the entry was actually removed from the hashtable.

After removing 415: Current nodes in hashtable: key: 999 value: Joe key: 389 value: Mary

In its final step, the application destroys the hashtable by using the delete operator. The destructor is automatically called before the hashtable is destroyed . The destructor calls the removeAll() member function of the Hashtable class, which displays each entry before removing them from the hashtable. Here s what is displayed on the screen when all the entries are removed:

Destroying hashtable: Removing node - key:999 Joe Removing node - key:389 Mary

//HashtableDemo.cpp #include <iostream.h> #include <time.h> #include <stdlib.h> #include <string.h> #include <stdio.h> #include "Hashtable.h void displayAll(Hashtable* hashtable); void main() { Hashtable* hashtable = new Hashtable(); char key[SIZE_KEY]; char value[SIZE_VALUE]; strcpy(key, "389"); strcpy(value, "Mary"); if(!hashtable->contains(key)) { cout << "Adding node - key: " << key << " value: " << value << endl; hashtable->put(key, value) } strcpy(key, "415"); strcpy(value, "Henry"); if(!hashtable->contains(key)) { cout << "Adding node - key: " << key << " value: " << value << endl; hashtable->put(key, value); } strcpy(key, "999"); strcpy(value, "Joe"); if(!hashtable->contains(key)) { cout << "Adding node - key: " << key << " value: " << value << endl; hashtable->put(key, value); } displayAll(hashtable); hashtable->remove("415"); cout << "After removing 415:" << endl; displayAll(hashtable); cout << "\nDestroying hashtable:" << endl; delete hashtable; } void displayAll(Hashtable* hashtable) { char key[SIZE_KEY]; char value[SIZE_VALUE]; cout << "\nCurrent nodes in hashtable:" << endl; hashtable->initIterator(); while(hashtable->hasNext()) { hashtable->getNextKey(key); hashtable->get(key, value); cout << "key: " << key << "\tvalue: " << value << endl; } }

//HashTable.h #include <string.h> #define SIZE_KEY 32 #define SIZE_VALUE 256 #define DEFAULT_TABLESIZE 101 typedef struct Metadata { struct Metadata(char* key, char* value) { strcpy(this->key, key); strcpy(this->value, value); next = NULL; } char key[SIZE_KEY]; char value[SIZE_VALUE]; struct Metadata* next; } METADATA; class Hashtable { private: int tablesize; METADATA** table; int size; long hashString(char* key); METADATA* find(char* key); METADATA* current_entry; int current_index; public: Hashtable(int tablesize = DEFAULT_TABLESIZE); virtual ~Hashtable(); bool put(char* key, char* value); bool get(char* key, char* value); bool contains(char* key); bool remove(char* key); void removeAll(); int getSize(); void initIterator(); bool hasNext(); void getNextKey(char* key); }; //Hashtable.cpp #include <iostream.h> #include <stdlib.h> #include "HashTable.h" Hashtable::Hashtable(int tablesize) { size = 0; this->tablesize = tablesize; table = new METADATA*[tablesize]; for(int i=0; i<tablesize; i++) { table[i] = NULL; } } Hashtable::~Hashtable() { removeAll(); delete[] table; } bool Hashtable::put(char* key, char* value) { if(find(key) != NULL) { return false; } METADATA* entry = new METADATA(key, value); int bucket = hashString(key); entry->next = table[bucket]; table[bucket] = entry; size++; return true; } bool Hashtable::get(char* key, char* value) { METADATA* temp = find(key); if(temp == NULL) { value[0] = '\0'; return false; } else { strcpy(value, temp->value); return true; } } bool Hashtable::contains(char* key) { if(find(key) == NULL) { return false; } else { return true; } } bool Hashtable::remove(char* key) { int bucket = hashString(key); METADATA* temp = table[bucket]; if(temp == NULL) { return false; } else if(strcmp(key, temp->key) == 0) { table[bucket] = temp->next; delete temp; size--; return true; } else { METADATA* temp_next = temp->next; while(temp_next != NULL) { if(strcmp(key, temp_next->key) == 0) { temp->next = temp_next->next; delete temp_next; size--; return true; } temp = temp->next; temp_next = temp_next->next; } } return false; } void Hashtable::removeAll() { for(int i=0; i<tablesize; i++) { METADATA* temp = table[i]; while(temp != NULL) { METADATA* next = temp->next; cout << "Removing node - key:" << temp->key << "\t" << temp->value << endl; delete temp; temp = next; } } size = 0; } int Hashtable::getSize() { return size; } METADATA* Hashtable::find(char* key) { int bucket = hashString(key); METADATA* temp = table[bucket]; while(temp != NULL) { if(strcmp(key, temp->key) == 0) { return temp; } temp = temp->next; } return NULL; } long Hashtable::hashString(char* key) { int n = strlen(key); long h = 0; for(int i=0; i<n; i++) { h = (h << 2) + key[i]; } return abs(h % tablesize); } void Hashtable::initIterator() { current_entry = NULL; current_index = tablesize; for(int i=0; i<tablesize; i++) { if(table[i] == NULL) { continue; } else { current_entry = table[i]; current_index = i; break; } } } bool Hashtable::hasNext() { if(current_entry == NULL) { return false; } else { return true; } } void Hashtable::getNextKey(char* key) { if(current_entry == NULL) { key[0] = '\0'; return; } strcpy(key, current_entry->key); if(current_entry->next != NULL) { current_entry = current_entry->next; } else { for(int i=current_index+1; i<tablesize; i++) { if(table[i] == NULL) { continue; } current_entry = table[i]; current_index = i; return; } current_entry = NULL; current_index = tablesize; } } '; return false; } else { strcpy(value, temp->value); return true; } } bool Hashtable::contains(char* key) { if(find(key) == NULL) { return false; } else { return true; } } bool Hashtable::remove(char* key) { int bucket = hashString(key); METADATA* temp = table[bucket]; if(temp == NULL) { return false; } else if(strcmp(key, temp->key) == 0) { table[bucket] = temp->next; delete temp; size--; return true; } else { METADATA* temp_next = temp->next; while(temp_next != NULL) { if(strcmp(key, temp_next->key) == 0) { temp->next = temp_next->next; delete temp_next; size--; return true; } temp = temp->next; temp_next = temp_next->next; } } return false; } void Hashtable::removeAll() { for(int i=0; i<tablesize; i++) { METADATA* temp = table[i]; while(temp != NULL) { METADATA* next = temp->next; cout << "Removing node - key:" << temp->key << "\t" << temp->value << endl; delete temp; temp = next; } } size = 0; } int Hashtable::getSize() { return size; } METADATA* Hashtable::find(char* key) { int bucket = hashString(key); METADATA* temp = table[bucket]; while(temp != NULL) { if(strcmp(key, temp->key) == 0) { return temp; } temp = temp->next; } return NULL; } long Hashtable::hashString(char* key) { int n = strlen(key); long h = 0; for(int i=0; i<n; i++) { h = (h << 2) + key[i]; } return abs(h % tablesize); } void Hashtable::initIterator() { current_entry = NULL; current_index = tablesize; for(int i=0; i<tablesize; i++) { if(table[i] == NULL) { continue; } else { current_entry = table[i]; current_index = i; break; } } } bool Hashtable::hasNext() { if(current_entry == NULL) { return false; } else { return true; } } void Hashtable::getNextKey(char* key) { if(current_entry == NULL) { key[0] = '

//HashTable.h #include <string.h> #define SIZE_KEY 32 #define SIZE_VALUE 256 #define DEFAULT_TABLESIZE 101 typedef struct Metadata { struct Metadata(char* key, char* value) { strcpy(this->key, key); strcpy(this->value, value); next = NULL; } char key[SIZE_KEY]; char value[SIZE_VALUE]; struct Metadata* next; } METADATA; class Hashtable { private: int tablesize; METADATA** table; int size; long hashString(char* key); METADATA* find(char* key); METADATA* current_entry; int current_index; public: Hashtable(int tablesize = DEFAULT_TABLESIZE); virtual ~Hashtable(); bool put(char* key, char* value); bool get(char* key, char* value); bool contains(char* key); bool remove(char* key); void removeAll(); int getSize(); void initIterator(); bool hasNext(); void getNextKey(char* key); }; //Hashtable.cpp #include <iostream.h> #include <stdlib.h> #include "HashTable.h" Hashtable::Hashtable(int tablesize) { size = 0; this->tablesize = tablesize; table = new METADATA*[tablesize]; for(int i=0; i<tablesize; i++) { table[i] = NULL; } } Hashtable::~Hashtable() { removeAll(); delete[] table; } bool Hashtable::put(char* key, char* value) { if(find(key) != NULL) { return false; } METADATA* entry = new METADATA(key, value); int bucket = hashString(key); entry->next = table[bucket]; table[bucket] = entry; size++; return true; } bool Hashtable::get(char* key, char* value) { METADATA* temp = find(key); if(temp == NULL) { value[0] = '\0'; return false; } else { strcpy(value, temp->value); return true; } } bool Hashtable::contains(char* key) { if(find(key) == NULL) { return false; } else { return true; } } bool Hashtable::remove(char* key) { int bucket = hashString(key); METADATA* temp = table[bucket]; if(temp == NULL) { return false; } else if(strcmp(key, temp->key) == 0) { table[bucket] = temp->next; delete temp; size--; return true; } else { METADATA* temp_next = temp->next; while(temp_next != NULL) { if(strcmp(key, temp_next->key) == 0) { temp->next = temp_next->next; delete temp_next; size--; return true; } temp = temp->next; temp_next = temp_next->next; } } return false; } void Hashtable::removeAll() { for(int i=0; i<tablesize; i++) { METADATA* temp = table[i]; while(temp != NULL) { METADATA* next = temp->next; cout << "Removing node - key:" << temp->key << "\t" << temp->value << endl; delete temp; temp = next; } } size = 0; } int Hashtable::getSize() { return size; } METADATA* Hashtable::find(char* key) { int bucket = hashString(key); METADATA* temp = table[bucket]; while(temp != NULL) { if(strcmp(key, temp->key) == 0) { return temp; } temp = temp->next; } return NULL; } long Hashtable::hashString(char* key) { int n = strlen(key); long h = 0; for(int i=0; i<n; i++) { h = (h << 2) + key[i]; } return abs(h % tablesize); } void Hashtable::initIterator() { current_entry = NULL; current_index = tablesize; for(int i=0; i<tablesize; i++) { if(table[i] == NULL) { continue; } else { current_entry = table[i]; current_index = i; break; } } } bool Hashtable::hasNext() { if(current_entry == NULL) { return false; } else { return true; } } void Hashtable::getNextKey(char* key) { if(current_entry == NULL) { key[0] = '\0'; return; } strcpy(key, current_entry->key); if(current_entry->next != NULL) { current_entry = current_entry->next; } else { for(int i=current_index+1; i<tablesize; i++) { if(table[i] == NULL) { continue; } current_entry = table[i]; current_index = i; return; } current_entry = NULL; current_index = tablesize; } } '; return; } strcpy(key, current_entry->key); if(current_entry->next != NULL) { current_entry = current_entry->next; } else { for(int i=current_index+1; i<tablesize; i++) { if(table[i] == NULL) { continue; } current_entry = table[i]; current_index = i; return; } current_entry = NULL; current_index = tablesize; } }

Hashtable Using C++

Категории