Buenas,
Cual seria una buena funcion de hash para un string en un caso generico? De lo que se menciono en clase y lei en el libro del curso, hacer una buena funcion de hash para strings es algo que depende del contexto en que se trabaja. Por otro lado funciones como sumar los valores ASCII de un string si bien son generales no distribuyen muy bien, entonces si se me pidiera (por ejemplo en el parcial) hacer una tabla de hash con strings, como elijo la funcion de hash?
...un string lo podes tomar como un número escrito en base N+1 donde cada caracter es un dígito del número(digamos que este número se llama m). Luego te tomas un primo tan o más grade que la cantidad máxima de strings que queres guardar en tu hash. Luego encontras una raiz primitiva en U(p) siendo p el primo que elegimos. Ahora, nuesta funcion de hash es h(m)=g^m mod p. Como vimos en discreta 2, esto se puede hacer bastante rápido con exponenciación rápida. Además. distribuye muy bien!!!
Espero haber aportado en algo en tu duda. Hice una búsqueda sobre métodos actuales pero no entendí mucho como funcionaban. Te dejo este video por si te interesa. Explica qué es un hash, su utilidad, ejemplos de uso y menciona un par de funciones de hash para strings que se usan actualmente: https://www.youtube.com/watch?v=GctssJjiqG4
El nombre del hash que te hablo en el anterior mensaje se llama SHA256 por si lo queres buscar. Saludos!!!
Wow, conque eso es un SHA256. Muchas gracias, me iluminaste jajaj.
Gracias por la respuesta y por el material. No se me habia ocurrido que las raices primitivas podian usarse en una funcion de hash, parace una aplicacion interesante.
Por qué decís que es malo sumar caractéres y hacer mod M ? Es lo primero que se me ocurriría para hacerla fácil.
Si eso fuese malo, también sería malo hacer mod M cuando tenemos números cualesquiera. Por supuesto dependés de que tu M sea primo.
Te comento las 3 principales razones por las que entendi que esta funcion de hash no es muy buena :
1) Cumple algunas propiedades no deseadas, por ejemplo fijate que permutaciones del mismo string caerian en el mismo bucket, por lo tanto, si estas trabajando en un ambiente donde no es raro tener permutaciones esto provocaria un aumento en las colisiones
2) Sumar los valores ASCII es una funcion que "crece lento". A que me reffiero con esto :
Supongamos que quiero almacenar 1.000.000 de strings aproximadamente. Y supongamos que son nombres de personas, por lo que es razonable tener una cota aproximada de 30 caracteres (esto lo digo a ojo y seria incluyendo apellidos, pero no es relevante el valor exacto de la cota). Recordemos ademas que (si no me equivoco en el numero) los valores de la tabla ASCII van del 0 al 255. Esto implica que el maximo valor que puede darse en un string que recibo es 30*255 0 7650 (poner en los 30 lugares el valor mas grande). Entonces como quiero almacenar 1.000.000 de strings me armo una tabla del siguiente primo mas cercano (por simplicidad supongo que es 1.000.001) La funcion de hash entonces estaria usando menos de los 10.000 primeros lugares de la tabla, por lo que la cantidad de colisiones sera enorme. Esto se podria arreglar si se asigna tambien un "peso por posicion" o mejor dicho se escribe en base 256 y siguiendo la codificacion ASCII al string.
3) Los lenguajes no tienen una distribucion uniforme, por ejemplo la a aparece mucho mas en español que la z, entonces esto "indica" que la distribucion de la tabla de hash no será muy uniforme
Hola Rafael.
Todo lo que decís está muy bien. No es simple definir funciones de hash sobre strings para que tengan una buena distribución, independientemente de la semántica que se le de a los strings. En este curso, y en particular en una evaluación, si aparece la necesidad de trabajar con una función sobre strings se darán indicaciones/sugerencias, ya que no es parte del curso analizar distribuciones de probabilidad de funciones no triviales/simples.
Saludos, Carlos
Perfecto, gracias por la aclaracion.