2

Tengo una clase llamada HashTabla que representa una tabla hash. Pero, para el algoritmo de hashing quiero usar distintas funciones de hash. Para eso he creado una clase llamada Hashing que contiene algunas funciones hash hechas para probar.

Mi código va así:

template <class K, class V>
class HashEntidad {
private:
    K key;
    V value;
public:
    HashEntidad(K key, V value) {
        this->key = key;
        this->value = value;
    }
    K getKey() { return key; }
    V getValue() { return value; }
};

template<class K, class V>
class HashTabla {
private:
    GeneradorPrimos genradorPrimos = GeneradorPrimos(3);
    HashEntidad<K, V>** tabla;
    int numElementos = 0;
    int TABLE_SIZE;
    size_t (*hashear)(const K, int);

public:
    HashTabla(size_t(*hasher)(const K, int) = nullptr) {
        TABLE_SIZE = genradorPrimos.current();
        tabla = new HashEntidad<K, V>* [TABLE_SIZE];
        
        if(hasher != nullptr) {
          hashear = hasher;  
        } else {
             hashear = [](const K key, int size_) { 
                return Hashing().dinamicHashing<K>(key, size_); 
            };
        }

        for (int i = 0; i < TABLE_SIZE; ++i)
            tabla[i] = nullptr;

    }

    ~HashTabla() = default;

    //Direccionamiento según Prueba Lineal
    void insertar(const K& key, V value) {
        size_t base, hash;
        int step;
        //validar si la tabla está llena
        if (numElementos == TABLE_SIZE) resize();

        base = hashear(key, TABLE_SIZE);
        hash = base;
        step = 0;

        while (tabla[hash] != nullptr)
        {
            step++;
            hash = (base + step) %TABLE_SIZE;
        }

        //almacenarlo en la tabla
        tabla[hash] = new HashEntidad<K, V>(key, value);
        numElementos++;
    }

    int buscar(const K& key) {
        int step = 0;
        size_t i, base;
        i = base = hashear(key, TABLE_SIZE);
        while (true)
        {
            if (tabla[i] == nullptr) return -1;
            else if (tabla[i]->getKey() == key) {
                return i;
            }
            else step++;

            i = (base + step) % TABLE_SIZE;             
        }
    }

    //imprimri el hashtahle 
    void imprimir() {
        for (int i = 0; i < TABLE_SIZE; i++) {
            if (tabla[i] != nullptr) {
                cout << "Clave: " << tabla[i]->getKey() << ", Valor: " << tabla[i]->getValue() << ", hash: " << hashear(tabla[i]->getKey(), TABLE_SIZE) << endl;
            }
            else {
                cout << i << "\n";
            }
        }
    }

private:
    void resize() {
        int nuevo_size = genradorPrimos.next();
        HashEntidad<K, V>** nueva_tabla = new HashEntidad<K, V>* [nuevo_size];

        for (int i = 0; i < nuevo_size; ++i)
            nueva_tabla[i] = nullptr;

        for (int i = 0; i < TABLE_SIZE; ++i) {
            if (tabla[i] != nullptr) {
                K key = tabla[i]->getKey();
                V value = tabla[i]->getValue();
                size_t  hash = hashear(key, nuevo_size);
                size_t base = hash;
                int step = 0;
                // Manejar colisiones utilizando prueba lineal
                while (nueva_tabla[hash] != nullptr) {
                    hash = (base + (++step)) % nuevo_size;
                }

                nueva_tabla[hash] = new HashEntidad<K, V>(key, value);
                tabla[i] = nullptr;
            }
        }

        TABLE_SIZE = nuevo_size;
        tabla = nueva_tabla;
    }
};

La clase que contiene mis funciones hash es la siguiente:

class Hashing {
private:
    GeneradorPrimos genPrimos = GeneradorPrimos(0);
public:
    Hashing() = default;

    template <typename T>
    size_t dinamicHashing(const T& key, int size){
        size_t hash = 0;
        size_t tamBytesKey = sizeof(T);
        const unsigned char* data = reinterpret_cast<const unsigned char*>(&key);

        for (int i = 0; i < tamBytesKey; i++)
            hash ^= data[i];

        return hash % size;
    }

    size_t basicHashing(const char* key, int size) {
        unsigned long long hash = 0;

        for (int i = 0; i < strlen(key); i++) {
            hash = (hash * genPrimos.current()) + key[i];
        }
        return hash % size;
    }
};
La clase GeneradorPrimos solo se encarga de generar un numero primo, si se llama con 0 genera un numero primo muy alto, de lo contrario empieza en el valor asignado

Al probarlo con el constructor por defecto, es decir, sin pasar ninguna función hash a mi tabla funciona correctamente.

int main() {
    HashTabla<const char*, char> tabla = HashTabla<const char*, char>();
    tabla.insertar("1", 'a');
    tabla.insertar("2", 'b');
    tabla.insertar("c", 'c');
    tabla.insertar("e", 'e');
    tabla.imprimir();
    cout << tabla.get("1");
}

Pero si trato de pasarle alguna función me da error:

HashTabla<const char*, char> tabla = HashTabla<const char*, char>(Hashing().basicHashing);

El error:

error: reference to non-static member function must be called
    HashTabla<const char*, char> tabla = HashTabla<const char*, char>(Hashing().basicHashing);
                                                                      ~~~~~~~~~~^~~~~~~~~~~~
1 error generated.

Al principio lo que hice fue encerrar las funciones hash en una lambda. Tal que así:

}
HashTabla<const char*, char> tabla = HashTabla<const char*, char>(
  [](const char* key, int size) {
      return Hashing().basicHashing(key, size);
  }
);

Pero no lo veo muy bonito y por lo que me han dicho es una horrorosidad >_<. Lo que trato hacer es que la clase HashTabla acepte una función (Con 2 argumentos, uno es la key y el otro el size de la tabla) que se usará como función de hash para sacar el hash a la key. Pero, la clase puede recibir tanto una función de la clase Hashing como una lambda creada por el propio usuario o algún puntero a función, de igual forma, creado por el usuario.

3
  • ¿Realmente tienes un problema? Por lo que veo encontraste una solución, solo que no te gusta. Por cierto, nota que por cada llamada al lambda estás creando una instancia nueva de la clase Hashing. Creo que deberias ser consistente y: mover el código fuera de la clase Hashing que además soluciona el problema del lambda o utilizar polimorfismo y que cada clase solo tenga una función de hash.
    – Mateo
    Commented el 15 jun. 2023 a las 21:04
  • Si bien la solución que encontré funciona quiero algo apegado a mi idea original. La cual era hacer algo como HashTabla<const char*, char>(Hashing().basicHashing) pero al no poder hacer eso recurrí a la forma que muestro que no es lo busco. Y sobre colocar las funciones fuera, sí sería una solución pero me veo obligado hacerlo así. Y asu vez mi profe quiere como mínimo 3 funciones hash... °-°
    – Christian
    Commented el 15 jun. 2023 a las 21:25
  • Ok, qué tal si pruebas con polimorfismo?
    – Mateo
    Commented el 15 jun. 2023 a las 21:27

2 respuestas 2

2

Estás confundiendo los tipos de los punteros a función. En tu constructor de HashTabla estás pasando size_t(*hasher)(const K, int) como parámetro de construcción.

Ese parámetro es "puntero a una función que devuelve size_t y recibe const K e int como parámetros", pero al construir estás pasando Hashing().basicHashing como parámetro de construcción y esa expresión ni siquiera tiene sentido en C++.

Si quieres pasar un puntero a una función del objeto Hashing entonces te falta:

  1. El operador "dirección-de" (&).
  2. El objeto propietario de dicha función (Hashing).

Es decir, la firma del constructor de HashTabla debería ser:

// Puntero a función perteneciente a 'Hashing' que devuelve 'size_t'
// y recibe 'const K' e 'int' como parámetros.
HashTabla(size_t(Hashing::*hasher)(const K, int) = nullptr);

Y la llamada debería ser:

HashTabla<const char*, char>(&Hashing::basicHashing);

El problema de usar una función miembro de otro objeto, es que dichas funciones necesitan un objeto sobre el que llamarse, así que sólo con el puntero no conseguirías nada.

Si quieres una función de hash independiente, no hagas parte de un objeto. Si quieres un objeto hash porque necesitas conservar un estado interno entonces tendrás que modificar tu HashTabla para que guarde una instancia del objeto hash, si todos los objetos hash siguen la misma interfaz ni siquiera necesitas guardar la función que usan para el cálculo.

template<class K, class V, class H = std::nullptr_t>
class HashTabla {
private:
    GeneradorPrimos genradorPrimos = GeneradorPrimos(3);
    HashEntidad<K, V>** tabla;
    int numElementos = 0;
    int TABLE_SIZE;
    H hasher{};
    …
public:
    HashTabla(H hasher = {}) :
        hasher{hasher}
    {
        …
        if constexpr (std::is_same_v<decltype(hasher), std::nullptr_t>)
        { /* no se proporcionó hasher */ }
        else
        { /* tenemos hasher */ }
    }
};

He hecho una versión simplificada de mi propuesta:

#include <iostream>
#include <type_traits>

struct Hash
{
    int do_hash() { std::cout << "Do hash! "; return 0; };
};

template <typename T = std::nullptr_t>
struct S
{
    S(T t = {}) : t{t}
    {
        if constexpr (std::is_same_v<decltype(t), std::nullptr_t>)
            std::cout << "No hay hasher\n";
        else
            std::cout << "El hash devuelve = " << t.do_hash() << '\n';
    }

    T t;
};

int main()
{
    S s;       // Sin hasher
    S<Hash> h; // Con hasher

    return 0;
}

Puedes verla funcionando en Try it online!.

2
  • Entiendo el enfoque que planteas. En mi cabeza estaba bien la idea de crear una clase Hashing que contenga algunas funciones de hash, pero veo que era mejor tener cada una en una clase. Por cierto, si modifico el constructor a HashTabla(size_t(Hashing::*hasher)(const K, int) = nullptr); solo aceptará funciones miembro de Hashing, no?
    – Christian
    Commented el 16 jun. 2023 a las 18:46
  • Correcto size_t(Hashing::*hasher)(const K, int) es "puntero a función miembro de Hashing que devuelve size_t y recibe const K e int como parámetros". Si quieres que sea una clase arbitraria deberías usar una plantilla (por ejemplo size_t(H::*hasher)(const K, int) siendo H un parámetro plantilla). Commented el 19 jun. 2023 a las 9:51
1

Una posible solución pasa por aumentar el número de constructores de tu código:

template<class K, class V>
class HashTabla {
private:
    std::function< size_t( const K &, int ) > hashear;

    static size_t haser_por_defecto( const K &k, int size ) {
        static Hashing h;

        return h.dinamicHashing< K >( key, size );
    }

public:
    HashTabla( ) {
        TABLE_SIZE = genradorPrimos.current();
        tabla = new HashEntidad<K, V>* [TABLE_SIZE];        
        hashear = haser_por_defecto;

        for (int i = 0; i < TABLE_SIZE; ++i)
            tabla[i] = nullptr;
    }

    HashTabla( std::function< size_t( const K &, int ) > &&haser ) {
        TABLE_SIZE = genradorPrimos.current();
        tabla = new HashEntidad<K, V>* [TABLE_SIZE];
        hashear = std::move( haser ); 

        for (int i = 0; i < TABLE_SIZE; ++i)
            tabla[i] = nullptr;
    }

    template< typename CLASS >
    HashTabla( CLASS *instance, size_t (CLASS::*method)( const K &, int ) ) {
        TABLE_SIZE = genradorPrimos.current();
        tabla = new HashEntidad<K, V>* [TABLE_SIZE];
        auto lambda = [instance, method]( const K &k, int size ) -> size_t {
            return (instance->*method)( k, size );
        };
        hashear = lambda;

        for (int i = 0; i < TABLE_SIZE; ++i)
            tabla[i] = nullptr;
    }
};

Cambiamos tu variable-miembro hashear, y creamos un constructor distinto dependiendo de como lo quieras usar:

  • Constructor por defecto, para usar la función de hash por defecto.
  • Usando una lambda, lo que te permite usar funciones estáticas y, en general, funciones-no-miembro.
  • Contructor template, que genera una lambda al-vuelo, y necesita un puntero a la instancia que quieras usar, junto a un puntero a su función miembro.

Este último caso se usaria así:

struct MiHash {
    size_t calcular( const int &, int );
};

MiHash mihash;
HashTabla< int, std::string > Hash( &mihash, &MiHash::calcular );

Y listo, ya se puede usar a placer.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.