elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Los 10 CVE más críticos (peligrosos) de 2020


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Ayuda con teoría de Funciones Hash
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Ayuda con teoría de Funciones Hash  (Leído 1,014 veces)
Gauss

Desconectado Desconectado

Mensajes: 6


Ver Perfil
Ayuda con teoría de Funciones Hash
« en: 29 Noviembre 2018, 20:21 pm »

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.

Código:
#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);
}


En línea

CalgaryCorpus


Desconectado Desconectado

Mensajes: 323


Ver Perfil WWW
Re: Ayuda con teoría de Funciones Hash
« Respuesta #1 en: 29 Noviembre 2018, 20:32 pm »

Que dependa de la clave esta bien, y aun esta bien recorrer el string 1 vez para calcular el valor del hash.

La preocupacion de que no sea O(1) viene relacionada con el tamano de los datos que tienes, vale decir, si tienes n claves+datos, cuanto tomas en insertarlas en tu contenedor? y cuando te demoras en encontrarlas si estan, o en descubrir que no estan cuando asi es? Si esto es dependiente de n la tabla de hash no se esta comportando tan bien como quisieras. Tu quieres que ese tiempo sea constante tambien.


« Última modificación: 29 Noviembre 2018, 20:38 pm por CalgaryCorpus » En línea

Aqui mi perfil en LinkedIn, invitame un cafe aqui
Gauss

Desconectado Desconectado

Mensajes: 6


Ver Perfil
Re: Ayuda con teoría de Funciones Hash
« Respuesta #2 en: 1 Diciembre 2018, 21:07 pm »

Muchas gracias!
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Funciones de Hash « 1 2 »
Criptografía
Unravel 14 74,591 Último mensaje 18 Marzo 2012, 04:19 am
por cioran
Preguntas de teoría sobre funciones
Programación C/C++
DickGumshoe 3 1,781 Último mensaje 11 Enero 2012, 20:45 pm
por satu
Ayuda con un hash
Criptografía
0x6865726e616e 3 2,873 Último mensaje 15 Junio 2012, 16:28 pm
por APOKLIPTICO
Programa para probar funciones hash
Criptografía
Alvarito050506 4 1,775 Último mensaje 23 Octubre 2019, 16:34 pm
por Alvarito050506
Secured-Hash 2018 - Funciones para VFP6 « 1 2 »
Programación General
eb4bgr 13 2,847 Último mensaje 5 Noviembre 2019, 21:44 pm
por eb4bgr
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines