Hash table, using special values to mark empty and deleted indexes

Question

The following is a program for my school. It's supposed to use a hashtable to store values/keys. We use a marking system to mark for empty indexes and deleted indexes. -1 for empty and -2 for deleted. This hashtable is an outdated concept but the real goal is to learn how to manipulate hashtables. I want to ask if this is efficient or how it could be improved, please be specific. Lastly, just take a look at the header to see what each function/how the program/code works.

Main.cpp:

using namespace std;
#include "tests.h"
#include "hashtable.h"
int main()
{
 testHashTable();
 cout << endl;
 system("Pause");
 return 0;
}

Tests.h (used to test the code):

#include "hashtable.h"
void testHashTable() {
 cout << "^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^" << endl;
 cout << "Testing hashtables: " << endl;
 cout << "^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^" << endl;
 cout << "Constructing a hashtable and printing: " << endl;
 cout << "-------------------------------------------" << endl;
 HashTable test(7);
 cout << test << endl;
 cout << "Capacity: " << test.getCap() << endl;
 cout << "Number of items: " << test.getNumOfItems() << endl;
 cout << "-------------------------------------------" << endl;
 cout << "Hashtable insertion and print data: " << endl;
 cout << "-------------------------------------------" << endl;
 test.insertKey(21);
 cout << test << endl;
 test.insertKey(21);
 cout << test << endl;
 test.insertKey(7);
 test.insertKey(1991);
 test.insertKey(1992);
 test.insertKey(1996);
 test.insertKey(69);
 test.insertKey(420);
 cout << test << endl;
 cout << "Number of items: " << test.getNumOfItems() << endl;
 cout << "-------------------------------------------" << endl;
 cout << "Searching and print: " << endl;
 cout << "-------------------------------------------" << endl;
 cout << "Find 14, does it exist? " << boolalpha << test.searchKey(14) << endl;
 cout << "Find 400, does it exist? " << boolalpha << test.searchKey(400) << endl;
 cout << "Find 21, does it exist? " << boolalpha << test.searchKey(21) << endl;
 cout << "Find 1337, does it exist? " << boolalpha << test.searchKey(1337) << endl;
 cout << "Find 69, does it exist? " << boolalpha << test.searchKey(69) << endl;
 cout << "Find 420, does it exist? " << boolalpha << test.searchKey(420) << endl;
 cout << "Find 7, does it exist? " << boolalpha << test.searchKey(7) << endl;
 cout << "-------------------------------------------" << endl;
 cout << "Deleting values in hashtable: " << endl;
 cout << "-------------------------------------------" << endl;
 test.deleteKey(21);
 test.deleteKey(69);
 test.deleteKey(420);
 test.deleteKey(1991);
 test.deleteKey(1969);
 cout << test << endl;
 cout << "Number of items: " << test.getNumOfItems() << endl;
 cout << "-------------------------------------------" << endl;
 cout << "Hashtable insertion and print data again: " << endl;
 cout << "-------------------------------------------" << endl;
 test.insertKey(21);
 test.insertKey(69);
 cout << test << endl;
 cout << "Number of items: " << test.getNumOfItems() << endl;
 cout << "-------------------------------------------" << endl;
 cout << "Rehash hashtable and print data again: " << endl;
 cout << "-------------------------------------------" << endl;
 test.rehash();
 cout << test << endl;
 cout << "Capacity: " << test.getCap() << endl;
 cout << "Number of items: " << test.getNumOfItems() << endl;
 cout << "-------------------------------------------" << endl;
 cout << "Reset hashtable: " << endl;
 cout << "-------------------------------------------" << endl;
 test.resetTable();
 cout << test << endl;
 cout << "Number of items: " << test.getNumOfItems() << endl;
 cout << "Is this hashtable empty? True or false? " << boolalpha << test.isEmpty() << endl;
}

Hashtables.h:

#ifndef HASHTABLE_H
#define HASHTABLE_H 
using namespace std;
#include <iostream>
const int DEFAULTCAPACITY = 23;
class HashTable
{
 friend ostream& operator<<(ostream& out, const HashTable& theTable); // Print operator overloading.
public:
 // Constructors:
 HashTable(); // Default constructor.
 HashTable(int newCapacity); // Overloaded constructor.
 HashTable(const HashTable& otherTable); // Copy constructor.
 HashTable(HashTable&& otherTable); // Move constructor.
 // Accessors:
 int getNumOfItems() const; // Spits out the number of items stored within the hashtable.
 int getCap() const; // Spits out the capacity of the hashtable.
 bool isEmpty() const; // Spits out if the hashtable is empty or not.
 // Function(s):
 void insertKey(int value); // Inserts a value into the hashtable using the hashvalue function to get the correct index.
 void deleteKey(int value); // Deletes a value within the hashtable, setting it to -2.
 void resetTable(); // Empties out the hashtable, setting everything to -1.
 void rehash(); // Rehashes all non-deleted/non-empty values of the hashtable into a bigger hashtable that is double that of the current hashtable (next prime #).
 bool searchKey(int value) const; // Returns true if it finds the value within the hashtable.
 // Operator overloading(s):
 HashTable& operator=(const HashTable& otherTable); // Assignment operator overloading.
 HashTable& operator=(HashTable&& otherTable); // Move assignment operator overloading.
 // Destructor:
 ~HashTable(); // Destroys the hashtable.
private:
 int hashValue(int key, int j) const; // Calculates an expression to get the hashvalue so you can store the value in index.
 int* searchKey(int value, int j) const; // Spits out an index if there's one, if not spits out nullptr.
 int *ht; // Points to hashtable.
 int numOfItems; // Number of items in the hashtable.
 int capacity; // Maximum length of the hashtable.
};
#endif

Hashtables.cpp:

#include "hashtable.h"
ostream& operator<<(ostream& out, const HashTable& theTable) {
 for (int i = 0; i < theTable.capacity; ++i) {
 out << theTable.ht[i] << " ";
 }
 return (out);
}
HashTable::HashTable() {
 capacity = DEFAULTCAPACITY;
 ht = new int[capacity];
 for (int i = 0; i < capacity; ++i) {
 ht[i] = -1;
 }
 numOfItems = 0;
}
HashTable::HashTable(int newCapacity) {
 capacity = newCapacity;
 ht = new int[capacity];
 for (int i = 0; i < capacity; ++i) {
 ht[i] = -1;
 }
 numOfItems = 0;
}
HashTable::HashTable(const HashTable& otherTable) {
 // Set all member variables of the calling object:
 capacity = otherTable.capacity;
 numOfItems = otherTable.numOfItems;
 // Create a new array:
 ht = new int[capacity];
 // Copy all elements of the array parameter onto the calling object:
 for (int i = 0; i < numOfItems; ++i) {
 ht[i] = otherTable.ht[i];
 }
}
HashTable::HashTable(HashTable&& otherTable) {
 ht = move(otherTable.ht);
 capacity = move(otherTable.capacity);
 numOfItems = move(otherTable.numOfItems);
 otherTable.ht = nullptr;
 otherTable.capacity = move(0);
 otherTable.numOfItems = move(0);
}
int HashTable::getNumOfItems() const {
 return (numOfItems);
}
int HashTable::getCap() const {
 return (capacity);
}
bool HashTable::isEmpty() const {
 return (numOfItems == 0);
}
int HashTable::hashValue(int key, int j) const {
 const int stepSize = 3;
 return ( ((key)+(j*stepSize)) % capacity ); // Space for readability.
}
void HashTable::insertKey(int value) {
 if (numOfItems < capacity) {
 bool foundSlot = false;
 int j = 0;
 int* indexValue;
 while (!foundSlot) { 
 indexValue = &ht[hashValue(value, j)];
 if (*indexValue == -1 || *indexValue == -2 || *indexValue == value) {
 if (*indexValue != value) {
 *indexValue = value;
 ++numOfItems;
 }
 foundSlot = true;
 }
 ++j; // Just increase the j...
 }
 }
 else {
 cerr << "Capacity in HashTable has been reached, cannot exceed the capacity." << endl;
 }
}
void HashTable::deleteKey(int value) {
 if (numOfItems != 0) {
 int* indexPosition = searchKey(value, 0);
 if (indexPosition != nullptr) {
 *indexPosition = -2;
 --numOfItems;
 }
 }
}
void HashTable::resetTable() {
 for (int i = 0; i < capacity; ++i) {
 ht[i] = -1;
 }
 numOfItems = 0;
}
void HashTable::rehash() {
 int *oldHt = ht;
 int oldCapacity = capacity;
 capacity = (capacity * 2) + 1;
 ht = new int[capacity];
 numOfItems = 0;
 for (int i = 0; i < capacity; ++i) {
 ht[i] = -1;
 }
 for (int i = 0; i < oldCapacity; ++i) {
 if (oldHt[i] != -1 && oldHt[i] != -2) {
 insertKey(oldHt[i]);
 }
 }
 delete[] oldHt;
 oldHt = nullptr;
}
bool HashTable::searchKey(int value) const {
 int j = 0;
 int *indexValue = &ht[hashValue(value, j)];
 int *firstIndexValue = indexValue;
 bool stillSearching = true;
 while (stillSearching) {
 if (*indexValue == value || *indexValue == -1 || (indexValue == firstIndexValue && j != 0)) { // The third or condition is to make sure it has
 stillSearching = false; // wrapped around at least one time and 
 } // if it did and landed on first index value again, just stop the search.
 else {
 ++j;
 indexValue = &ht[hashValue(value, j)];
 }
 }
 return (*indexValue == value);
}
int* HashTable::searchKey(int value, int j) const {
 int *indexValue = &ht[hashValue(value, j)];
 int *firstIndexValue = indexValue;
 bool stillSearching = true;
 while (stillSearching) {
 if (*indexValue == value || *indexValue == -1 || (indexValue == firstIndexValue && j != 0)) { // The third or condition is to make sure it has
 stillSearching = false; // wrapped around at least one time and 
 } // if it did and landed on first index value again, just stop the search.
 else {
 ++j;
 indexValue = &ht[hashValue(value, j)];
 }
 }
 if (*indexValue != value) {
 return nullptr;
 }
 return indexValue;
}
HashTable& HashTable::operator=(const HashTable& otherTable) {
 // Avoid self-assignment by checking that the 
 // parameter passed is not the calling object:
 if (&otherTable != this)
 {
 // If the array we are passing has a different
 // capacity from the calling object,
 // then we need to create a new array:
 if (capacity != otherTable.capacity)
 {
 // Deallocate the memory used by 
 // the calling object and
 // re-create the object so that 
 // it has the same capacity:
 delete[] ht;
 ht = new int[otherTable.capacity];
 // Update capacity:
 capacity = otherTable.capacity;
 }
 // Update number of elements:
 numOfItems = otherTable.numOfItems;
 // Start copying:
 for (int i = 0; i < numOfItems; ++i)
 ht[i] = otherTable.ht[i];
 }
 else
 {
 cerr << "Attempted assignment to itself.";
 }
 return (*this);
}
HashTable& HashTable::operator=(HashTable&& otherTable) {
 if (this != &otherTable) {
 delete[] ht;
 ht = move(otherTable.ht);
 capacity = move(otherTable.capacity);
 numOfItems = move(otherTable.numOfItems);
 otherTable.ht = nullptr;
 otherTable.capacity = move(0);
 otherTable.numOfItems = move(0);
 }
 return (*this);
}
HashTable::~HashTable() {
 delete[] ht;
 ht = nullptr; 
}

• Quinn Mortimer: Who told you that the hashtable was an outdated concept? It's one of the two most common approaches to implementing a mapping type and many think it has significant performance benefits over a tree-based approach.

Answer 1

Don't use using in your headers

Everyone who uses the header will have the entire contents of the std namespace copied into the global namespace whether they want them or not. It's not what I expect when I write #include "hashtable.h", and it's poor practice to inflict that on your (削除) victims (削除ここまで) users.

---

Otherwise, the code looks pretty clean. Good use of const where appropriate. Some issues that may be worth looking at:

• Prefer to use a smart pointer rather than a raw pointer for ht, which is owned by this class.

• We can use std::fill instead of a for loop to initialise the contents of ht.

• It's probably more convenient to implement move construction/assignment in terms of swap(), so implement that.

• Prefer to use the standard names for functions such as capacity() and empty(), to make this class more interchangeable with the standard collections. Similarly, consider providing iterators and making the content type a template parameter.

• Test program - do you really need to flush every line of output? Or can most of those std::endl be simply \n instead?