#include <iostream>
#include <cstring>
#include <array>
#include <list>
#include <string>
#include <algorithm>

using namespace std;

unsigned int mi_hash(string cadena) {
    unsigned int resultado = 1;
    for(int i = 0; i < cadena.length(); ++i) {
        resultado = 31 * resultado + cadena[i];
    }
    return resultado;
}

class EstructuraHash {
    public:
    explicit EstructuraHash()
        : elementos(tamanoActual)
        {}

    int tamanoActual = 100;
    float porcentajeAgraandado = 0.80;

    vector<list<string>> elementos;

    void agregar(string cadena) {
        unsigned int hash_resultado = mi_hash(cadena);
        unsigned int posicion = hash_resultado % 10;
        elementos.at(posicion).push_back(cadena);

        auto usados = [](const vector<list<string>>& elementos) {
            int resultado = 0;
            for(auto bucket : elementos) {
                resultado += std::count_if(bucket.begin(), bucket.end(),
                                   [](std::string e) -> bool { return !e.empty(); });
            }
            return resultado;
        };

        if(usados(elementos) >  tamanoActual * porcentajeAgraandado) {
            realocar();
        }
    }

    bool existe(std::string cadena) {
        unsigned int hash_resultado = mi_hash(cadena);
        unsigned int posicion = hash_resultado % 10;
        auto bucketList = elementos.at(posicion);
        auto elemento = std::find(bucketList.begin(), bucketList.end(), cadena);

        return elemento != bucketList.end();
    }

    void realocar() {
        vector<list<string>> viejoVector(tamanoActual*2);
        swap(viejoVector, elementos);
        for(auto bucket : viejoVector) {
            for(auto registro : bucket) {
                agregar(registro);
            }
        }
    }
};


int main()
{
    EstructuraHash h;
    h.agregar("HelloWorld");
    h.agregar("Moby Dick");
    h.agregar("Bohemian rhapsody");

    cout << h.existe("hi") << h.existe("Hello World");
    return 0;
}