INF1010 3WB – T4: Implementação de uma tabela Hash.

Enunciado:

Implemente uma classe Hash, em C++, respeitando o seguinte:

1. Utilize uma estrutura de tabela Hash para armazenar os elementos que devem ser inseridos e consultados com complexidade O(1).
2. A classe é template, e portanto permite o armazenamento de elementos de qualquer tipo. Elementos esses identificados por uma chave do tipo std::string.
3. Utilize a interface mostrada no arquivo t4_hash.h para sua classe.
4. É permitido criar funções ou variáveis membro privadas, para facilitar a implementação.
5. ATENÇÃO: Para este trabalho, em que estamos criando uma classe template, implemente todas as funções no .h

t4_hash.h

#ifndef T4_HASH_H
#define T4_HASH_H

#include <string>

template< typename T >
class Hash
{
public:
    //Construtor. Aloca a tabela com tamanho tableSize
    Hash( int tableSize );

    //Destrutor. Desaloca a tabela.
    ~Hash();

    //Insere um elemento na tabela
    void insere(const std::string& chave, T valor);

    //Obtém o valor de um elemento, dada a sua chave
    T obtemValor(const std::string& chave);

    //Funcao hash. Dada uma chave, retorna em qual
    //posicao da tabela ela deve ser armazenada
    int hash(const std::string& chave);

private:
    struct HashElem
    {
        std::string _chave;
        T _valor;
    };

    //Tabela armazenada como um C-array de elementos HashElem.
    HashElem* _tabela;

    /* Funcoes e membros privados que julgar necessarios */
};

#endif // T4_HASH_H