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.
Hashing
. Creo que deberias ser consistente y: mover el código fuera de la claseHashing
que además soluciona el problema del lambda o utilizar polimorfismo y que cada clase solo tenga una función de hash.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... °-°