Buena función de hash para cadenas

160

Estoy tratando de pensar en una buena función hash para cadenas. Y estaba pensando que podría ser una buena idea resumir los valores Unicode para los primeros cinco caracteres de la cadena (suponiendo que tenga cinco, de lo contrario, pare donde termina). ¿Sería una buena idea, o es mala?

Estoy haciendo esto en Java, pero no me imagino que eso haga una gran diferencia.

Leif Andersen
fuente
44
Las buenas funciones hash dependen en gran medida de la entrada al hash y de los requisitos del algoritmo. Tal hash no será muy bueno si todas sus cadenas comienzan con los mismos cinco caracteres, por ejemplo. También tenderá a dar como resultado una distribución normal.
WhirlWind
1
Posible duplicado de 98153
Michael Mrozek
14
¿Por qué no se puede utilizar Stringla propia hashCode()?
Bart Kiers el
@WhirlWind, es cierto, no estoy seguro de qué tendrán las cadenas, aparte de eso, probablemente sea texto en inglés.
Leif Andersen
@Barl, principalmente porque mi profesor nos dijo que implementemos nuestro propio hash functor ... y la razón por la que no quería usar Java era porque era genérico, e imagino que un funh hash más específico sería mejor.
Leif Andersen

Respuestas:

161

Por lo general, los hashes no haría sumas, de lo contrario stop, y potstendrá el mismo hash.

y no lo limitarías a los primeros n caracteres porque de lo contrario la casa y las casas tendrían el mismo hash.

En general, los valores hash toman valores y los multiplican por un número primo (lo que hace que sea más probable que genere valores hash únicos). Por lo tanto, puede hacer algo como:

int hash = 7;
for (int i = 0; i < strlen; i++) {
    hash = hash*31 + charAt(i);
}
jonathanasdf
fuente
@jonathanasdf ¿Cómo puedes decir que siempre te da una clave hash única? ¿Hay alguna prueba matemática? Creo que tenemos que tomar mod de hash con otro número primo más grande, de lo contrario se produce un problema de desbordamiento.
devsda
17
@devsda No siempre dijo que es único, dijo que es más probable que sea único. En cuanto a por qué, una búsqueda rápida en Google revela este artículo: computinglife.wordpress.com/2008/11/20/… explicando por qué 31 se usó para el hash de cadenas de Java. No se proporcionan pruebas matemáticas, pero explica el concepto general de por qué los primos funcionan mejor.
Pharap
2
Muchas gracias por aclarar la idea de hacer un mejor hash. Solo para verificar dos veces: Java utilizará el valor de retorno hashCode () para asignar a algún índice de tabla antes de almacenar el objeto. Entonces, si el hashCode () devuelve m, hace algo como (m mod k) para obtener un índice de la tabla de tamaño k. ¿Está bien?
whitehat
1
"hash = hash * 31 + charAt (i);" produce el mismo hash para spot, tops, stop, opts y potes.
Jack Straub
1
@maq Creo que tienes razón. No sé lo que estaba pensando.
Jack Straub
139

Si se trata de una cuestión de seguridad, podría usar Java crypto:

import java.security.MessageDigest;

MessageDigest messageDigest = MessageDigest.getInstance("SHA-256");
messageDigest.update(stringToEncrypt.getBytes());
String encryptedString = new String(messageDigest.digest());

fuente
93
Agradable. Tengo una aplicación de aprendizaje automático, haciendo PNL estadística en un corpus grande. Después de algunos pasos iniciales de normalización morfológica en las palabras originales del texto, descarto los valores de cadena y en su lugar utilizo códigos hash. En todo mi corpus, hay alrededor de 600,000 palabras únicas, y al usar la función predeterminada de código hash de Java, recibí aproximadamente 3.5% de colisiones. Pero si SHA-256 el valor de la cadena y luego genera un código hash a partir de la cadena digerida, la relación de colisión es inferior al 0,0001%. ¡Gracias!
benjismith
3
Gracias por proporcionar información sobre las colisiones y el número de palabras. Muy útil.
philipp
19
@benjismith Uno en un millón es demasiado grande ... ¿es "menos del 0,0001%" una forma oblicua de decir "exactamente 0"? Realmente dudo que haya visto una colisión SHA-256 porque eso nunca se ha observado, en ningún lugar, nunca; ni siquiera para SHA-1 de 160 bits. Si tiene dos cadenas que producen el mismo SHA-256, a la comunidad de seguridad le encantaría verlas; serás mundialmente famoso ... de una manera muy oscura. Ver comparación de funciones SHA
Tim Sylvester
77
@TimSylvester, entendiste mal. No encontré colisiones SHA-256. Calculé el SHA-256 y luego introduje las secuencias de bytes resultantes en una función típica de "código hash" de Java, porque necesitaba un hash de 32 bits. Ahí es donde encontré las colisiones. Nada notable :)
benjismith
1
¿No hay una diferencia entre 'hashing' y 'cifrado'? Entiendo que MessageDigest es una función de hashing unidireccional, ¿verdad? Además, cuando utilicé la función, obtuve la cadena hash como muchos caracteres UTF basura cuando abrí el archivo en LibreOffice. ¿Es posible obtener la cadena hash como un grupo aleatorio de caracteres alfanuméricos en lugar de caracteres UTF basura?
Nav
38

Probablemente deberías usar String.hashCode () .

Si realmente quieres implementar hashCode tú mismo:

No caiga en la tentación de excluir partes significativas de un objeto del cálculo del código hash para mejorar el rendimiento - Joshua Bloch, Java efectivo

Usar solo los primeros cinco caracteres es una mala idea . Piense en nombres jerárquicos, como URL: todos tendrán el mismo código hash (porque todos comienzan con "http: //", lo que significa que están almacenados bajo el mismo depósito en un mapa hash, exhibiendo un rendimiento terrible.

Aquí hay una historia de guerra parafraseada en String hashCode de " Java efectivo ":

La función de hash de cadena implementada en todas las versiones anteriores a 1.2 examinó a lo sumo dieciséis caracteres, espaciados uniformemente a lo largo de la cadena, comenzando con el primer carácter. Para grandes colecciones de nombres jerárquicos, como URL, esta función hash mostró un comportamiento terrible.

Frederik
fuente
1
Si uno está usando una colección de doble hash, puede valer la pena que el primer hash sea realmente rápido y sucio. Si uno tiene mil cadenas largas, la mitad de las cuales están asignadas por una función deficiente a un valor particular, y la otra mitad está asignada a valores distintos, el rendimiento en una tabla con un solo hash sería malo, pero el rendimiento en un doble La tabla hash, donde el segundo hash examinó toda la cadena, podría ser casi el doble que una tabla con un solo hash (ya que la mitad de las cadenas no tendrían que estar completamente hash). Sin embargo, ninguna de las colecciones estándar de Java tiene doble hashing.
supercat
El enlace efectivo de Java está roto @Frederik
KGs
17

Si estás haciendo esto en Java, ¿por qué lo estás haciendo? Solo llama .hashCode()a la cuerda

Pirolista
fuente
2
Lo hago como parte de la clase, y parte de la tarea es escribir varias funciones hash diferentes. El profesor nos dijo que busquemos ayuda externa para los "mejores".
Leif Andersen
20
Si necesita que tenga que ser coherente en todas las versiones e implementaciones de JVM, no debe confiar .hashCode(). Más bien, use algún algoritmo conocido.
Stephen Ostermiller
77
El algoritmo para String::hashCodese especifica en el JDK, por lo que es tan portátil como la existencia misma de la clase java.lang.String.
yshavit
12

Guava'sHashFunction ( javadoc ) proporciona un hash decente sin cripto-fuerte.

Mike Samuel
fuente
1
Todavía está en beta a partir de este comentario
ThomasRS
1
Y ahora 404d.
Shawn
8

Esta función provista por Nick es buena, pero si usa una nueva Cadena (byte [] bytes) para realizar la transformación a Cadena, falló. Puede usar esta función para hacer eso.

private static final char[] hex = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };

public static String byteArray2Hex(byte[] bytes) {
    StringBuffer sb = new StringBuffer(bytes.length * 2);
    for(final byte b : bytes) {
        sb.append(hex[(b & 0xF0) >> 4]);
        sb.append(hex[b & 0x0F]);
    }
    return sb.toString();
}

public static String getStringFromSHA256(String stringToEncrypt) throws NoSuchAlgorithmException {
    MessageDigest messageDigest = MessageDigest.getInstance("SHA-256");
    messageDigest.update(stringToEncrypt.getBytes());
    return byteArray2Hex(messageDigest.digest());
}

Puede ser que esto pueda ayudar a alguien

Festus Tamakloe
fuente
Puede pasar la matriz de bytes a messageDigest.update ().
szgal
byteArray2Hex () - ¡eso es perfectamente lo que estaba buscando! Muchas gracias :)
Krzysiek
5
// djb2 hash function
unsigned long hash(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}

Fuente Lógica detrás de la función hash djb2 - SO

Pratik Deoghare
fuente
1
Creo que es solo un número primo para comenzar, por lo que tenemos menos colisiones.
CornSmith
5

Se rumorea que FNV-1 es una buena función hash para cadenas.

Para cadenas largas (más largas que, digamos, unos 200 caracteres), puede obtener un buen rendimiento de la función hash MD4 . Como función criptográfica, se rompió hace unos 15 años, pero para fines no criptográficos, sigue siendo muy bueno y sorprendentemente rápido. En el contexto de Java, tendría que convertir los charvalores de 16 bits en palabras de 32 bits, por ejemplo, agrupando dichos valores en pares. Una implementación rápida de MD4 en Java se puede encontrar en sphlib . Probablemente exagere en el contexto de una tarea en el aula, pero vale la pena intentarlo.

Thomas Pornin
fuente
Esta función hash es mucho mejor que la que viene con Java.
clankill3r
3

Si desea ver las implementaciones estándar de la industria, miraría java.security.MessageDigest .

"Los resúmenes de mensajes son funciones hash unidireccionales seguras que toman datos de tamaño arbitrario y generan un valor hash de longitud fija".

Dean J
fuente
1

Aquí hay un enlace que explica muchas funciones hash diferentes, por ahora prefiero la función hash ELF para su problema particular. Toma como entrada una cadena de longitud arbitraria.

Yefei
fuente
1

sdbm: este algoritmo se creó para la biblioteca de base de datos sdbm (una reimplementación de dominio público de ndbm)

static unsigned long sdbm(unsigned char *str)
{   
    unsigned long hash = 0;
    int c;
    while (c = *str++)
            hash = c + (hash << 6) + (hash << 16) - hash;

    return hash;
}
Anchal
fuente
0
         public String hashString(String s) throws NoSuchAlgorithmException {
    byte[] hash = null;
    try {
        MessageDigest md = MessageDigest.getInstance("SHA-256");
        hash = md.digest(s.getBytes());

    } catch (NoSuchAlgorithmException e) { e.printStackTrace(); }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < hash.length; ++i) {
        String hex = Integer.toHexString(hash[i]);
        if (hex.length() == 1) {
            sb.append(0);
            sb.append(hex.charAt(hex.length() - 1));
        } else {
            sb.append(hex.substring(hex.length() - 2));
        }
    }
    return sb.toString();
}
Charaf JRA
fuente
-1

Es una buena idea trabajar con números impares cuando se trata de desarrollar una buena función hast para string. Esta función toma una cadena y devuelve un valor de índice, hasta ahora funciona bastante bien. y tiene menos colisión. el índice varía de 0 a 300, tal vez incluso más que eso, pero hasta ahora no he subido incluso con palabras largas como "ingeniería electromecánica"

int keyHash(string key)
{
    unsigned int k = (int)key.length();
    unsigned int u = 0,n = 0;

    for (Uint i=0; i<k; i++)
    {
        n = (int)key[i];
        u += 7*n%31;
    }
    return u%139;
}

Otra cosa que puede hacer es multiplicar cada carácter por el índice a medida que aumenta, como la palabra "oso" (0 * b) + (1 * e) + (2 * a) + (3 * r) que le dará Un valor int para jugar. la primera función hash anterior colisiona en "aquí" y "escucha" pero sigue siendo excelente para dar buenos valores únicos. el siguiente no choca con "aquí" y "escuchar" porque multiplico cada carácter con el índice a medida que aumenta.

int keyHash(string key)
{
    unsigned int k = (int)key.length();
    unsigned int u = 0,n = 0;

    for (Uint i=0; i<k; i++)
    {
        n = (int)key[i];
        u += i*n%31;
    }
    return u%139;
}
kanthonye
fuente
-1

Aquí hay una función hash simple que uso para una tabla hash que construí. Básicamente es para tomar un archivo de texto y almacena cada palabra en un índice que representa el orden alfabético.

int generatehashkey(const char *name)
{
        int x = tolower(name[0])- 97;
        if (x < 0 || x > 25)
           x = 26;
        return x;
}

Lo que esto básicamente hace es que las palabras se dividen según su primera letra. Entonces, la palabra que comienza con 'a' obtendría una clave hash de 0, 'b' obtendría 1 y así sucesivamente y 'z' sería 25. Los números y símbolos tendrían una clave hash de 26. Hay una ventaja que proporciona ; Puede calcular fácil y rápidamente dónde se indexaría una palabra dada en la tabla hash, ya que todo está en un orden alfabético, algo así: el código se puede encontrar aquí: https://github.com/abhijitcpatil/general

Dando el siguiente texto como entrada: Atticus le dijo a Jem un día: "Prefiero que dispares a las latas en el patio trasero, pero sé que irás tras los pájaros". Dispara a todos los arrendajos azules que quieras, si puedes golpearlos, pero recuerda que es un pecado matar a un ruiseñor. Esa fue la única vez que escuché a Atticus decir que era pecado hacer algo, y le pregunté a la señorita Maudie al respecto. "Tu padre tiene razón", dijo. “Los sinsontes no hacen una cosa excepto hacer música para que la disfrutemos. No se comen los jardines de las personas, no anidan en cunas de maíz, no hacen nada más que cantar por nosotros. Por eso es pecado matar un ruiseñor.

Este sería el resultado:

0 --> a a about asked and a Atticus a a all after at Atticus
1 --> but but blue birds. but backyard
2 --> cribs corn can cans
3 --> do dont dont dont do dont do day
4 --> eat enjoy. except ever
5 --> for for fathers
6 --> gardens go
7 --> hearts heard hit
8 --> its in it. I it I its if I in
9 --> jays Jem
10 --> kill kill know
11 --> 
12 --> mockingbird. music make Maudie Miss mockingbird.”
13 --> nest
14 --> out one one only one
15 --> peoples
16 --> 17 --> right remember rather
18 --> sin sing said. she something sin say sin Shoot shot said
19 --> to Thats their thing they They to thing to time the That to the the tin to
20 --> us. up us
21 --> 
22 --> why was was want
23 --> 
24 --> you you youll you
25 --> 
26 --> Mockingbirds  Your em Id
usuario2311285
fuente
2
Una buena función hash distribuye los valores por igual entre los cubos.
Jonathan Peterson
-1

Esto evitará cualquier colisión y será rápido hasta que usemos el desplazamiento en los cálculos.

 int k = key.length();
    int sum = 0;
    for(int i = 0 ; i < k-1 ; i++){
        sum += key.charAt(i)<<(5*i);
    }
kamal el-deen shair
fuente