I am trying to write my own implementation of a hash table (hash map) in C++. It turns out that my code is unoptimized as I can't pass performance tests. Can you please give some advice for optimization of the program?
I am using open addressing for resolving collisions with quadratic probing. Hash function for string: value of polynom, coefs of polynom - every single char of string. Only strings are inserted into hash table
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
//HashTable class
/*
Using open adressing for resolving collisions with quadratic probing
*/
class HashTable {
public:
HashTable();
bool Set(std::string key);
bool Remove(std::string key);
bool Get(std::string key);
private:
int GetHash(std::string text, int table_size);
std::vector<std::pair<std::string, bool>> table;
void ExtendTable();
size_t fullness = 0;
};
HashTable::HashTable() {
//first element of pair - key, second - is the cell free
for(int i = 0; i < 8; i++) {
table.push_back(std::make_pair("",true));
}
}
int HashTable::GetHash(std::string text, int table_size) {
//Hash function for string. Calculates polynom value using Horner method
int b = text[0];
int point = (int)sqrt(table_size); //x value for polynom
for(int i = 1; i < text.size(); i++) {
b = (text[i] + b*point) % table_size;
}
return b % table_size;
}
void HashTable::ExtendTable() {
//Extends table if fullness == 3/4 * size of table
//creates new table
std::vector<std::pair<std::string, bool>> new_table;
for(int i = 0; i < 2*this->table.size(); i++) {
new_table.push_back(std::make_pair("", true));
}
//copying old table to a new one
for(int i = 0; i < this->table.size(); i++) {
int new_index = GetHash(this->table[i].first, 2*this->table.size());
int step = 1;
while(!new_table[new_index].second) {
new_index += pow(step, 2);
new_index %= 2*this->table.size();
step++;
}
new_table[new_index] = this->table[i];
}
this->table = new_table;
}
bool HashTable::Set(std::string key) {
//Adding new element to hash table. Dublicates are ignored
int index = GetHash(key, this->table.size());
int step = 1;
while(!this->table[index].second) {
if(this->table[index].first == key) return false;
index += pow(step, 2);
index %= this->table.size();
step++;
}
this->table[index] = std::make_pair(key, false);
this->fullness++;
if(this->fullness*4 >= this->table.size()*3)
ExtendTable();
return true;
}
bool HashTable::Get(std::string key) {
//Checks if element is in hash table
int index = GetHash(key, this->table.size());
int step = 1;
int counter = 0;
while(counter < this->fullness+1) {
if(this->table[index].first == key) return true;
index += pow(step, 2);
index %= this->table.size();
step++;
counter++;
}
return false;
}
bool HashTable::Remove(std::string key) {
//removes hash table
int index = GetHash(key, this->table.size());
int step = 0;
int counter = 0;
while(counter < this->fullness+1) {
if(this->table[index].first == key) {
this->fullness--;
this->table[index].first = "";
this->table[index].second = true;
return true;
}
index += pow(step, 2);
index %= this->table.size();
step++;
counter++;
}
return false;
}
int main() {
HashTable table;
std::ios_base::sync_with_stdio(0),std::cin.tie(0),std::cout.tie(0);
std::string input = "";
while(std::cin >> input) {
if(input == "+") {
std::cin >> input;
bool flag = table.Set(input);
if(flag) std::cout << "OK" << std::endl;
else std::cout << "FAIL" << std::endl;
}
else if(input == "?") {
std::cin >> input;
bool flag = table.Get(input);
if(flag) std::cout << "OK" << std::endl;
else std::cout << "FAIL" << std::endl;
}
else if(input == "-") {
std::cin >> input;
bool flag = table.Remove(input);
if(flag) std::cout << "OK" << std::endl;
else std::cout << "FAIL" << std::endl;
}
}
return 0;
}
