Hola buenas tardes, estaba leyendo sobre Tablas Hash y quería implementar una desde 0, lo primero que quise hacer son unas funciones hash, la que es para strings(si le ingresan como clave "ab" devuelve la suma de los códigos ASCII, "ab" = 97+98 = 195) y la de plegamiento(si le ingresan una clave entera devuelve la suma de unas partes, para la clave 42531 -> 42 + 53 + 1 = 96). El (suma%tamanioTabla) es para que el índice que devuelva esté en el rango de la tabla.
Mi duda es más teórica creo, porque según tengo entendido las funciones Hash son de orden O(1), osea que son rápidas al no iterar y obtener el resultado/ingreso/borrado directamente. Pero en las funciones Hash que hice hay bucles, por ejemplo en el de los strings hay tantos bucles como longitud de la palabra clave y si las claves son largas el programa va perdiendo eficiencia.
Entonces son válidas esas funciones Hash? o debería ingeniármelas de alguna forma para hacer las funciones Hash sin bucles para que no dependan de la clave?
Gracias.
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <sstream>
using namespace std;
int funcionHashStrings(string clave, int tamanioTabla);
int funcionHashPlegamiento(int llave, int tamanioTabla);
int main() {
int tamanio;
cout<<"Ingrese el tamaño de la tabla: ";
cin>>tamanio;
//PRUEBA FUNCIÓN HASH DE STRINGS
/*string palabra;
cout<<"\nIngrese una clave string: ";
cin>>palabra;
cout<<"Indice devuelvo por la funcion Hash: "<<funcionHashStrings(palabra,tamanio);*/
//PRUEBA PLEGAMIENTO
int llave;
cout<<"Ingrese la clave(numero entero): ";
cin>>llave;
cout<<endl;
cout<<"Devuelve como indice el numero: "<<funcionHashPlegamiento(llave,tamanio);
return 0;
}
int funcionHashStrings(string clave, int tamanioTabla){
int suma = 0;
for(unsigned i=0 ; i< clave.length(); i++) {
cout<<clave[i]<<": "<<(int)clave[i]<<endl;
suma += (int)clave[i];
}
cout<<"Suma: "<<suma<<endl;
return (suma%tamanioTabla); //Método del resto
}
int funcionHashPlegamiento(int llave, int tamanioTabla) {
string cadena,aux1="--", aux2= "-";
int suma=0;
cadena = static_cast<ostringstream*>(&(ostringstream() << llave))->str();
cout<<cadena<<" = ";
for(unsigned i=0; i<cadena.length(); i+=2) {
if((i+1) == cadena.length()) {
aux2[0] = cadena[i];
cout<<atoi(&aux2[0])<<" ";
suma+= (atoi(&aux2[0]));
}
else {
aux1[0] = cadena[i];
aux1[1]=cadena[i+1];
cout<<aux1<<" ";
suma+= (atoi(aux1.c_str()));
}
}
cout<<"= "<<suma<<endl;
return (suma%tamanioTabla);
}