Hash table

hash_table.cpp

#include "hash_table.h"

HashTable::HashTable() : table(16) {}

HashTable::HashTable(int size) : table(size) {

}

HashTable::~HashTable() = default;

bool HashTable::try_get_value(const string &key, int &value) const {
    auto &bucket = table[hash_func(key)];
    if (!bucket.empty()) {
        auto it = find_if(bucket.begin(),
                          bucket.end(),
                          [&](auto &item) { return item.first == key; });

        if (it != bucket.end()) {
            value = (*it).second;
            return true;
        }
    }
    return false;
}

bool HashTable::contains_key(const string &key) const {
    return !table[hash_func(key)].empty();
}

void HashTable::insert(const string &key, int value) {
    auto &bucket = table[hash_func(key)];
    auto it = find_if(bucket.begin(),
                      bucket.end(),
                      [&](auto &item) { return item.first == key; });

    if (it != bucket.end())
        (*it) = pair<string, int>(key, value);

    else
        bucket.emplace_back(key, value);


    if (this->calc_load_factor() > 0.75) {
        table.resize(table.size() * 2);
        rehash();
    }
}


void HashTable::remove(const string &key) {
    auto &bucket = table[hash_func(key)];
    if (!bucket.empty())
        bucket.erase(remove_if(bucket.begin(),
                               bucket.end(),
                               [&](auto &item) { return item.first == key; }),
                     bucket.end());
}

void HashTable::clear() {
    for (auto &bucket: table)
        bucket.clear();
}


size_t HashTable::get_table_size() const {
    return table.size();
}


int HashTable::hash_func(const string &key) const {
    int sum = 0;
    for (char chr: key) {
        sum = (sum * PRIME_NUMBER) + chr;
    }
    return sum % get_table_size();
}

size_t HashTable::get_number_of_keys() const {
    int count = 0;
    for (const auto &bucket: table)
        count += (int) bucket.size();

    return count;
}

double HashTable::calc_load_factor() const {
    return (double) get_number_of_keys() / (double) get_table_size();
}

void HashTable::print() {
    for (int i = 0; i < table.size(); ++i) {
        cout << i << ". ";
        for (const auto &item: table[i]) {
            cout << "-->" << '(' << item.first << ": " << item.second << ')';
        }
        cout << endl;
    }
}

std::ostream &operator<<(std::ostream &os, const HashTable &hash_table) {
    for (int i = 0; i < hash_table.table.size(); ++i) {
        cout << i << ". ";
        for (const auto &item: hash_table.table[i]) {
            os << "-->" << '(' << item.first << ": " << item.second << ')';
        }
        cout << endl;
    }


    return os;
}

void HashTable::rehash() {
    vector<vector<pair<string, int>>> old_table = this->table;
    table = vector<vector<pair<string, int>>>(table.size());
    for (const auto &bucket: old_table)
        for (const auto &item: bucket)
            table[hash_func(item.first)].push_back(item);
}

hash_table.h

#ifndef HASH_TABLE_H
#define HASH_TABLE_H

#include <vector>
#include <ostream>
#include <iostream>
#include <utility>
#include <algorithm>
#include <stdexcept>

using namespace std;

class HashTable {
public:
    HashTable();

    HashTable(int size);

    virtual ~HashTable();

    bool contains_key(const string &key) const;

    void insert(const string &key, int value);

    void remove(const string &key);

    void clear();

    bool try_get_value(const string &Key, int &Value) const;

    size_t get_table_size() const;

    size_t get_number_of_keys() const;

    double calc_load_factor() const;

    void print();

    friend std::ostream &operator<<(std::ostream &os, const HashTable &table);



private:
    const static int PRIME_NUMBER = 137;
    vector<vector<pair<string, int>>> table;
    int hash_func(const string &key) const;
    void rehash();
};


#endif //HASH_TABLE_H

main.cpp

#include <iostream>
#include "hash_table.h"

using namespace  std;

int main() {
    cout << std::boolalpha;
    HashTable hash_table(6);

    {
        hash_table.insert("foo", 987);
        hash_table.insert("abc", 123);
        hash_table.insert("def", 456);
        hash_table.insert("ghi", 789);
        cout << hash_table;
    }

    cout << endl;
    
    {
        hash_table.remove("ghi");
        cout << hash_table;
    }

    cout << endl;

    {
        int value = 0;
        cout << hash_table.try_get_value("def", value) << " " << value << endl;
    }


    return 0;
}