Iurii Tatishchev
30ad8892de
Now that you have a working implementation of the HashNode and HashTable classes, you can convert them to templates, and update main.cpp to match with the new template classes. In order for everything to work you will also have to: - overload the == operator for the Student class - declare the hash function a friend function of the Student class - send the hash function as an argument to insert, remove, and search functions.
121 lines
3.2 KiB
C++
121 lines
3.2 KiB
C++
// Specification file for the Hash class
|
|
// Written By: Iurii Tatishchev
|
|
// Changed by: Iurii Tatishchev
|
|
|
|
|
|
#ifndef HASHTABLE_H_
|
|
#define HASHTABLE_H_
|
|
|
|
#include "HashNode.h"
|
|
|
|
template<class ItemType>
|
|
class HashTable {
|
|
private:
|
|
HashNode<ItemType> *hashAry;
|
|
int hashSize;
|
|
int count;
|
|
|
|
public:
|
|
HashTable() {
|
|
count = 0;
|
|
hashSize = 53;
|
|
hashAry = new HashNode<ItemType>[hashSize];
|
|
}
|
|
|
|
HashTable(int n) {
|
|
count = 0;
|
|
hashSize = n;
|
|
hashAry = new HashNode<ItemType>[hashSize];
|
|
}
|
|
|
|
~HashTable() { delete[] hashAry; }
|
|
|
|
int getCount() const { return count; }
|
|
|
|
int getSize() const { return hashSize; }
|
|
|
|
double getLoadFactor() const { return 100.0 * count / hashSize; }
|
|
|
|
bool isEmpty() const { return count == 0; }
|
|
|
|
bool isFull() const { return count == hashSize; }
|
|
|
|
bool insert(const ItemType &itemIn, int h(const ItemType &key, int size));
|
|
|
|
bool remove(ItemType &itemOut, const ItemType &key, int h(const ItemType &key, int size));
|
|
|
|
int search(ItemType &itemOut, const ItemType &key, int h(const ItemType &key, int size)) const;
|
|
};
|
|
|
|
/*~*~*~*
|
|
Insert an item into the hash table
|
|
It does not reject duplicates
|
|
*~**/
|
|
template<class ItemType>
|
|
bool HashTable<ItemType>::insert(const ItemType &itemIn, int h(const ItemType &key, int size)) {
|
|
if (count == hashSize)
|
|
return false;
|
|
|
|
int pos = h(itemIn, hashSize);
|
|
int collisions = 0;
|
|
while (hashAry[pos].getOccupied() == 1) {
|
|
++pos;
|
|
++collisions;
|
|
pos = pos % hashSize;
|
|
}
|
|
hashAry[pos].setItem(itemIn);
|
|
hashAry[pos].setOccupied(1);
|
|
hashAry[pos].setNoCollisions(collisions);
|
|
count++;
|
|
|
|
return true;
|
|
}
|
|
|
|
/*~*~*~*
|
|
Removes the item with the matching key from the hash table
|
|
if found:
|
|
- copies data in the hash node to itemOut
|
|
- replaces data in the hash node with an empty record (occupied = -1: deleted!)
|
|
- returns true
|
|
if not found:
|
|
- returns false
|
|
*~**/
|
|
template<class ItemType>
|
|
bool HashTable<ItemType>::remove(ItemType &itemOut, const ItemType &key, int h(const ItemType &key, int size)) {
|
|
int pos = h(key, hashSize);
|
|
for (int collisions = 0; collisions < count; collisions++) {
|
|
if (hashAry[pos].getOccupied() == 1 && hashAry[pos].getItem() == key) {
|
|
itemOut = hashAry[pos].getItem();
|
|
// -1 means freed
|
|
hashAry[pos].setOccupied(-1);
|
|
count--;
|
|
return true;
|
|
}
|
|
pos = (pos + 1) % hashSize;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
/*~*~*~*
|
|
hash search - linear probe
|
|
if found:
|
|
- copy data to itemOut
|
|
- returns the number of collisions for this key
|
|
if not found, returns -1
|
|
*~**/
|
|
template<class ItemType>
|
|
int HashTable<ItemType>::search(ItemType &itemOut, const ItemType &key, int h(const ItemType &key, int size)) const {
|
|
int pos = h(key, hashSize);
|
|
for (int collisions = 0; collisions < count; collisions++) {
|
|
if (hashAry[pos].getOccupied() == 0) return -1;
|
|
if (hashAry[pos].getOccupied() == 1 && hashAry[pos].getItem() == key) {
|
|
itemOut = hashAry[pos].getItem();
|
|
return hashAry[pos].getNoCollisions();
|
|
}
|
|
pos = (pos + 1) % hashSize;
|
|
}
|
|
return -1;
|
|
}
|
|
|
|
#endif // HASHTABLE_H_
|