¿Qué es una buena función hash de 64 bits en Java para cadenas textuales?

Question

Busco una función hash que:

1. hashes cadenas de texto así (por ejemplo, pocas colisiones)
2. está escrito en Java, y ampliamente utilizado
3. Bono: trabaja en varios campos (en lugar de concatenarlos y aplicar el hash en la cadena concatenada)
4. Bonificación: tiene una variante de 128 bits.
5. Bonificación: No requiere CPU.

Answer 1

¿Por qué no utiliza una variante long del predeterminado String.hashCode() (donde algunos chicos realmente inteligentes sin duda se esfuerzan para hacerlo eficiente, sin mencionar los miles de ojos de desarrollador que ya vieron este código)?

// adapted from String.hashCode() 
public static long hash(String string) { 
    long h = 1125899906842597L; // prime 
    int len = string.length(); 

    for (int i = 0; i < len; i++) { 
    h = 31*h + string.charAt(i); 
    } 
    return h; 
} 

Si usted está buscando aún más bits, que probablemente podría utilizar una edición BigInteger :

Como ya he mencionado en un comentario a la respuesta de @brianegge, no hay muchos casos de uso de hashes con más de 32 bits y lo más probable es que no uno solo de los hashes con más de 64 bits:

que podía imaginar una enorme tabla hash distribuida a través de docenas de servidores, quizás almacenar decenas de miles de asignaciones. Para tal escenario, @brianegge todavía tiene un punto válido aquí: 32 bit permiten 2^32 (ca. 4.3 billones) diferentes claves hash. Suponiendo un algoritmo fuerte, aún debería tener muy pocas colisiones. Con 64 bit (18,446,744,073 billones de teclas diferentes) sin duda guardará, independientemente de cualquier escenario loco que lo necesite.Sin embargo, es casi imposible pensar en los casos de uso para llaves de 128 bits (340,282,366,920,938,463,463,374,607,431 mil millones de teclas posibles).

combinar el hash para varios campos, simplemente hacer un XOR multiplican uno con un primer y añadirlos:

long hash = MyHash.hash(string1) * 31 + MyHash.hash(string2); 

El pequeño primo es allí para evitar código hash igual para los valores conmutadas , es decir, {'foo', 'bar'} y {'bar', 'foo'} no son iguales y deben tener un código hash diferente. XOR es malo, ya que devuelve 0 si ambos valores son iguales. Por lo tanto, {'foo', 'foo'} y {'bar', 'bar'} tendrían el mismo código hash.

Answer 2

DESCARGO DE RESPONSABILIDAD: Esta solución es aplicable si desea hojear palabras de lenguaje natural de manera eficiente. Es ineficaz para hash texto más largo, o texto que contiene caracteres no alfabéticos.

No estoy al tanto de una función, pero esto es una idea que podría ayudar:

• Dedicar 52 de los 64 bits que representan a la que las letras están presentes en la cadena. Por ejemplo, si 'a' estuviera presente, establecería el bit [0], para 'b' establecería el bit 1, para 'A' establecería el bit [26]. De esta forma, solo el texto que contiene exactamente el mismo conjunto de letras tendrá la misma "firma".

Puede utilizar los 12 bits restantes para codificar la longitud de la cadena (o un valor de módulo) para reducir aún más las colisiones, o generar un código hash de 12 bits utilizando una función hash tradicional.

Suponiendo que su entrada es solo de texto, me imagino que esto daría lugar a muy pocas colisiones y sería de bajo costo para calcular (O (n)). A diferencia de otras soluciones, hasta ahora este enfoque tiene en cuenta el dominio del problema para reducir las colisiones - Se basa en el Detector Anagram descrito en Perlas de programación (consulte here).

Answer 3

Create an SHA-1 hash y luego enmascare las 64bits más bajas.

Answer 4

¿Miras Apache commons lang?

Pero para 64 bit (y 128) necesita algunos trucos: las reglas establecidas en el libro Effective Java de Joshua Bloch lo ayudan a crear hash fácil de 64 bits (solo use long en lugar de int). Por 128 bits que necesita cortes adicionales ...

Answer 5

long hash = string.hashCode(); 

Sí, los mejores 32 bits será 0, pero es probable que se quede sin recursos de hardware antes de ejecutar a tener problemas con colisiones hash. El hashCode in String es bastante eficiente y bien probado.

actualización creo que los satisface por encima de la cosa más simple que posiblemente podrían trabajar, sin embargo, estoy de acuerdo con @sfussenegger idea de extender el hashCode cadena existente.

Además de tener un buen hashCode para su String, le recomendamos que vuelva a aplicar el código hash en su implementación. Si su almacenamiento es utilizado por otros desarrolladores, o usado con otros tipos, esto puede ayudar a distribuir sus claves. Por ejemplo, el HashMap de Java se basa en tablas hash de potencia de dos, por lo que agrega esta función para garantizar que los bits más bajos estén suficientemente distribuidos.

h ^= (h >>> 20)^(h >>> 12); 
    return h^(h >>> 7)^(h >>> 4); 

Answer 6

¿Por qué no utilizar un polinomio CRC64? Estos son razonablemente eficientes y optimizados para garantizar que todos los bits se cuenten y distribuyan en el espacio de resultados.

Hay un montón de implementaciones disponibles en la red si google "CRC64 Java"

Answer 7

hacer algo como esto:

import java.io.ByteArrayOutputStream; 
import java.io.DataOutputStream; 
import java.io.IOException; 
import java.math.BigInteger; 
import java.security.MessageDigest; 
import java.security.NoSuchAlgorithmException; 

public class Test { 

    public static void main(String[] args) throws NoSuchAlgorithmException, 
      IOException { 
     ByteArrayOutputStream baos = new ByteArrayOutputStream(); 
     DataOutputStream dos = new DataOutputStream(baos); 

     try { 
      MessageDigest md = MessageDigest.getInstance("MD5"); 
      SomeObject testObject = new SomeObject(); 

      dos.writeInt(testObject.count); 
      dos.writeLong(testObject.product); 
      dos.writeDouble(testObject.stdDev); 
      dos.writeUTF(testObject.name); 
      dos.writeChar(testObject.delimiter); 
      dos.flush(); 

      byte[] hashBytes = md.digest(baos.toByteArray()); 
      BigInteger testObjectHash = new BigInteger(hashBytes); 

      System.out.println("Hash " + testObjectHash); 
     } finally { 
      dos.close(); 
     } 
    } 

    private static class SomeObject { 
     private int count = 200; 
     private long product = 1235134123l; 
     private double stdDev = 12343521.456d; 
     private String name = "Test Name"; 
     private char delimiter = '\n'; 
    } 
} 

DataOutputStream le permite escribir primitivas y Cuerdas y ellos tienen salida como bytes. Envolviendo una ByteArrayOutputStream en ella dejará que se escribe a una matriz de bytes, que se integra muy bien con MessageDigest. Puede elegir de cualquier algoritmo enumerado here.

Finalmente BigInteger le permiten apagar los bytes de salida en un número más fácil de usar. Los algoritmos MD5 y SHA1 producen hashes de 128 bits, por lo que si necesita 64 puede truncar.

SHA1 debería tener casi cualquier cosa, y con colisiones infrecuentes (es de 128 bits). Esto funciona desde Java, pero no estoy seguro de cómo se implementa. En realidad, puede ser bastante rápido. Funciona en varios campos en mi implementación: simplemente empújelos todos al DataOutputStream y listo. Incluso podría hacerlo con reflejos y anotaciones (quizás @HashComponent(order=1) para mostrar qué campos entran en un hash y en qué orden).Tiene una variante de 128 bits y creo que encontrarás que no usa tanta CPU como crees que será.

He utilizado un código como este para obtener hashes para enormes conjuntos de datos (a estas alturas probablemente miles de millones de objetos) para poder fragmentarlos en muchas tiendas back-end. Debería funcionar para lo que sea que lo necesite. Tenga en cuenta que creo que tal vez quiera llamar solo al MessageDigest.getInstance() una vez y luego al clone() a partir de ese momento: IIRC la clonación es mucho más rápida.

Answer 8

reversa de la cadena para obtener otro código hash de 32 bits y luego combinar los dos:

String s = "astring"; 
long upper = ((long) s.hashCode()) << 32; 
long lower = ((long) s.reverse().hashCode()) - ((long) Integer.MIN_VALUE); 
long hash64 = upper + lower; 

Ésta es pseudocódigo; el método String.reverse() no existe y deberá implementarse de otra manera.

Answer 9

Una respuesta para hoy (2018). SipHash.

Será mucho más rápido que la mayoría de las respuestas aquí, y de una calidad significativamente más alta que todas ellas.

biblioteca

La guayaba tiene uno: https://google.github.io/guava/releases/23.0/api/docs/com/google/common/hash/Hashing.html#sipHash24--