Tabela Hash com Busca Linear e tratamento de colisão utilizando realocação.

hashtable_interative.cpp

#include <iostream>
#include <cstdio>
#include <time.h>
#include "screen.h"

using namespace std;

#ifndef HASHTABLE_H
#define HASHTABLE_H

#include "screen.h"
using namespace std;

struct item{
    int key;
    std::string data;
    item(int key = -1, std::string data = ""){
        this->key = key;
        this->data = data;
    }
};

class hashtable
{
public:

    void show(int ind = -1, item it = item(0, "")){
        screen &s = *scr;
        s.clear();
        int step = 6;
        const int lkey = 5;//linha da chave

        int delta = 5;
        s.write(lkey - 1, 0, 0,  "  ind");
        s.write(lkey    , 0, 0, "  key");
        s.write(lkey + 1, 0, 0, "value");
        for(int i = 0; i < _max; i++){
            s.write(lkey - 2, i * step + delta, step, string(step, '='));
            s.write(lkey - 1, i * step + delta, step, "|__" + to_string(i) + "__");
            s.write(lkey    , i * step + delta, step, "|" + to_string(_vet[i].key));
            s.write(lkey + 1, i * step + delta, step, "|" + _vet[i].data);
            s.write(lkey + 2, i * step + delta, step, string(step, '='));
        }

        int lfkey = lkey - 4;//linha da chave em foco
        if(ind != -1){
            s.write(lfkey    , ind * step + delta, step, "|" + to_string(it.key));
            s.write(lfkey + 1, ind * step + delta, step, "|" + it.data);
        }
        s.show();
        s.wait();
    }

private:
    item * _vet;
    int _qtd;
    int _max;
    screen * scr;

    //realoca a tabela numa tabela com este novo tamanho
    void rebuild(int new_max_size){
        item * backup = _vet;
        int old_size = _max;

        _max = new_max_size;
        _vet = new item[new_max_size];
        _qtd = 0;

        for(int i = 0; i < old_size; i++){
            if(backup[i].key != -1)
                insert(backup[i].key, backup[i].data);
        }
        delete[] backup;
    }

    //retorna o indice da chave ou da primeira posição vazia após colisao
    int find_pos(int key, string value = ""){
        int ind = key % _max;
        while((_vet[ind].key != key) and (_vet[ind].key != -1)){
            show(ind, item(key, value));
            ind = (ind + 1) % _max;
        }
        show(ind, item(key, value));
        return ind;
    }

public:

    hashtable(int size, screen * scr)
    {
        this->scr = scr;
        _vet = new item[size];
        _max = size;
        _qtd = 0;
    }

    ~hashtable(){
        delete[] _vet;
    }

    int size(){
        return _qtd;
    }

    //se a chave ja existir, retorne false.
    //se não existe faça a inserção na tabela
    //se a ocupação passar de 80%, duplique o tamanho da tabela e
    //realoque todos os elementos
    bool insert(int key, string data){
        int ind = this->find_pos(key, data);
        cout << "pos " << ind << "bingo" << endl;

        item * elem = &_vet[ind];
        if(elem->key == key)
            return false; //elemento ja existe

        //inserindo item
        elem->key = key;
        elem->data = data;
        _qtd++;

        //se passar de 80%, realoque a tabela
        if(this->_qtd > 0.8 * (this->_max))
            rebuild(this->_max * 2);
        return true;
    }

    //se a chave existir retorne true
    bool exists(int key){
        return(_vet[find_pos(key)].key != -1);
    }

    //se a chave existir, retorne o dado. Se não existir, retorne ""
    string get(int key){
        int ind = find_pos(key);
        if(_vet[ind].key == -1)
            return "";
        return _vet[ind].data;
    }

    //se a chave existir, remova da tabela e retorne true
    //se a chave não existir, retorne false
    bool remove(int key){
        int ind = find_pos(key);
        if(_vet[ind].key == -1)
            return false;//chave nao existe

        //removo o primeiro
        _vet[ind].key = -1;
        _vet[ind].data = "";

        int next = (ind + 1) % _max;
        //vou removendo e reinserindo os proximos até encontrar uma posicao vazia
        while(_vet[next].key != -1){
            item aux = _vet[next];//salvo o item
            _qtd--;
            _vet[next].key = -1;//apago da posicao
            _vet[next].data = "";

            this->insert(aux.key, aux.data);//reinsiro o item
            show();
            next = (next + 1) % _max;//vou para proxima posicao
        }
        return true;
    }
};

#endif // HASHTABLE_H


int main()
{
    screen scr(20, 70);
    hashtable ht(10, &scr);
    string in;
    while(true){
        cout << "q quit, i insert, e exist, g get, r remove" << endl;
        cout << "ex: i key value; e key; g key; r key" << endl;
        cin >> in;
        if(in == "i"){
            int key;
            string value;
            cin >> key >> value;
            ht.insert(key, value);
            ht.show();
        }
        if(in == "e"){
            int key;
            cin >> key;
            cout << (ht.exists(key) ? "Existe" : "Nao existe") << endl;
        }
        if(in == "g"){
            int key;
            cin >> key;
            cout << "Valor " << ht.get(key) << endl;
        }
        if(in == "r"){
            int key;
            cin >> key;
            ht.remove(key);
            ht.show();
        }
        if(in == "q")
            break;
    }
    cout << endl;
    return 0;
}

screen.h

#ifndef SCREEN_H
#define SCREEN_H

#include <vector>
#include <iostream>
#include <sstream>

namespace std{

class screen
{
    vector<string> mat;

public:

    screen(int nl = 15, int nc = 70):
        mat(nl, string(nc, ' '))
    {
    }

    string& operator[](int l){
        return mat[l];
    }

    //max = maximo de caracteres a serem inseridos
    //max == 0 -> tantos quantos possível
    void write(int l, int c, int max, const string &str){
        int num = 0; //numero de caracteres escritos
        for(int i = 0; i < (int) str.size(); i++){
            if(c + i < (int) mat[0].size())
                if(l < (int) mat.size()){
                    mat[l][c + i] = str[i];
                    num++;
                    if(num == max)
                        return;
                }
        }
    }

    void show(){
        cout << string(mat[0].size() + 2, '#') << endl;
        for(auto linha : mat)
            cout << "#" << linha << "#" << endl;
        cout << string(mat[0].size() + 2, '#') << endl;
    }

    //espera qualquer entrada de dados
    void wait(){
        string s;
        //cin.ignore(1000, '\n');
        getline(cin, s);
    }

    void clear() {
        // CSI[2J clears screen, CSI[H moves the cursor to top-left corner
        std::cout << "\x1B[2J\x1B[H";
        //std::cout << "\x1B[H";
        for(auto &linha : mat)
            for(auto &c : linha)
                c = ' ';
    }

    int sizeL(){
        return mat.size();
    }

    int sizeC(){
        return mat[0].size();
    }
};
}//namespace std
#endif // SCREEN_H