Iurii Tatishchev
b43f08aacc
Reuse code from the previous lab and write new code as described below: - search hash: Modify this function to return -1 if the target key is not found or the number of collisions for that key if found. `int search(Student &target, string key);` - remove hash: Create a new function to delete an item from the hash table. - insert manager: inserts user provided data into the hash table and rejects duplicates.
82 lines
2.0 KiB
C++
82 lines
2.0 KiB
C++
// Implementation file for the Hash class
|
|
// Written By: Iurii Tatishchev
|
|
// Changed by: Iurii Tatishchev
|
|
|
|
#include <string>
|
|
#include <utility>
|
|
|
|
#include "HashTable.h"
|
|
|
|
using namespace std;
|
|
|
|
/*~*~*~*
|
|
A simple hash function
|
|
*~**/
|
|
int HashTable::_hash(string key) const {
|
|
int sum = 0;
|
|
for (char c : key)
|
|
sum += c;
|
|
return sum % hashSize;
|
|
};
|
|
|
|
/*~*~*~*
|
|
hash insert - linear probe
|
|
*~**/
|
|
bool HashTable::insert(const Student &itemIn) {
|
|
if (count == hashSize)
|
|
return false;
|
|
int pos = _hash(itemIn.getName());
|
|
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;
|
|
}
|
|
|
|
/*~*~*~*
|
|
hash delete - linear probe
|
|
*~**/
|
|
bool HashTable::remove(Student &itemOut, string key) {
|
|
int pos = _hash(key);
|
|
for (int collisions = 0; collisions < count; collisions++) {
|
|
if (hashAry[pos].getOccupied() == 1 && hashAry[pos].getItem().getName() == 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
|
|
search for key
|
|
if found:
|
|
- copy data to itemOut
|
|
- copy number of collisions for this key to noCol
|
|
- returns true
|
|
if not found, returns false
|
|
*~**/
|
|
int HashTable::search(Student &itemOut, string key) const {
|
|
int pos = _hash(key);
|
|
for (int collisions = 0; collisions < count; collisions++) {
|
|
if (hashAry[pos].getOccupied() == 0) return -1;
|
|
if (hashAry[pos].getOccupied() == 1 && hashAry[pos].getItem().getName() == key) {
|
|
itemOut = hashAry[pos].getItem();
|
|
return hashAry[pos].getNoCollisions();
|
|
}
|
|
pos = (pos + 1) % hashSize;
|
|
}
|
|
return -1;
|
|
}
|