Hashtabelle/HashTabelle.h

150 lines
3.1 KiB
C++

#pragma once
#include <iostream>
#include <string>
#include <vector>
#include <mutex>
#include <taskflow/taskflow.hpp>
template<typename T>
class HashTable {
public:
struct elem {
public:
T* data;
int key;
};
struct hashList {
public:
std::vector<elem> list;
};
int size;
int elements;
std::vector<hashList> table;
HashTable(int size);
~HashTable();
void insert(int id, T* n);
T* search(int id);
bool remove(int id);
void restructure();
int getSize();
int getElements();
double getUtilization();
void print();
int hash(int id);
private:
};
template < typename T >
HashTable<T>::HashTable(int size) {
this->size = size;
this->table = std::vector<hashList>(size);
};
template < typename T >
HashTable<T>::~HashTable() {
//table.clear();
//table.shrink_to_fit();
std::vector<hashList>().swap(table);
}
template < typename T >
int HashTable<T>::getSize() {
return size;
}
template < typename T >
int HashTable<T>::getElements() {
return elements;
}
template < typename T >
double HashTable<T>::getUtilization() {
return (double)elements/size;
}
template < typename T >
int HashTable<T>::hash(int id) {
return id % size;
}
template < typename T >
T* HashTable<T>::search(int id) {
int index = hash(id);
std::vector<elem> list = table.at(index).list;
for (auto it = list.begin(); it != list.end(); ++it) {
if (it->key == id) {
return it->data;
}
}
return nullptr;
}
template < typename T >
void HashTable<T>::insert(int id, T* data) {
int index = hash(id);
if (search(id)){
std::vector<elem> list = table[index].list;
for (auto it = table[index].list.begin(); it != table[index].list.end(); ++it) {
if (it->key == id) {
it->data = data;
}
}
}
else{
table[index].list.push_back(elem{ data, id });
elements++;
}
}
template < typename T >
bool HashTable<T>::remove(int id) {
int index = hash(id);
std::vector<elem> list = table[index].list;
int elemindex = 0;
for (auto it = table[index].list.begin(); it != table[index].list.end(); ++it) {
if (it->key == id){
table[index].list.erase(table[index].list.begin() + elemindex);
elements--;
return true;
}
elemindex++;
}
return false;
}
template < typename T >
void HashTable<T>::print() {
for (auto it = table.begin(); it != table.end(); ++it) {
std::cout << "Next list" << std::endl;
for (auto it2 = it->list.begin(); it2 != it->list.end(); ++it2) {
std::cout << it2->key << std::endl;
}
}
}
template < typename T >
void HashTable<T>::restructure() {
std::vector<hashList>oldTable = table;
size = size * 2;
table = std::vector<hashList>(size);
for (auto it = oldTable.begin(); it != oldTable.end(); ++it) {
for (auto it2 = it->list.begin(); it2 != it->list.end(); ++it2) {
insert(it2->key, it2->data);
}
}
}