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

guava java library

Question

Estoy buscando una función hash que:

1. Hashes cadenas de texto bien (por ejemplo, pocas colisiones)
2. Está escrito en Java, y es ampliamente utilizado
3. Bonificación: funciona en varios campos (en lugar de que yo los concatene y aplique el hash en la cadena concatenada)
4. Bonificación: tiene una variante de 128 bits.
5. Bonificación: no intensivo de la CPU.

Answer 1

¿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). Para 128 bit necesitas hacks adicionales ...

Answer 2

¿Por qué no usar 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 muchas implementaciones disponibles en la red si googleas "CRC64 Java"

Answer 3

Haz 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 permite escribir primitivas y cadenas y hacer que salgan como bytes. Envolver un ByteArrayOutputStream en él le permitirá escribir en una matriz de bytes, que se integra muy bien con MessageDigest . Puedes elegir de cualquier algoritmo enumerado here .

Finalmente, BigInteger le permitirá convertir 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 hash casi cualquier cosa bien, 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 de mi implementación: simplemente DataOutputStream a DataOutputStream y listo. Incluso podría hacerlo con reflejos y anotaciones (tal vez @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 usado código como este para obtener hashes para grandes 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 a MessageDigest.getInstance() una vez y clone() partir de ese momento: IIRC la clonación es mucho más rápida.

Answer 4

Invierta la cadena para obtener otro código hash de 32 bits y luego combine 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;

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

Answer 5

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.

La biblioteca de Guava tiene una: https://google.github.io/guava/releases/23.0/api/docs/com/google/common/hash/Hashing.html#sipHash24--

Answer 6

¿Por qué no usas una variante long del String.hashCode() predeterminado (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 está buscando aún más bits, probablemente podría utilizar una Edición BigInteger :

Como mencioné en un comentario a la respuesta de @brianegge, no hay muchas aplicaciones para hash con más de 32 bits y muy probablemente ni una sola para hash con más de 64 bits:

Podría imaginar una enorme tabla de hachís distribuida en docenas de servidores, tal vez almacenando decenas de miles de millones de mapeos. 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).

Para combinar el hash de varios campos, simplemente haga un XOR multiplique uno con un primo y agréguelos:

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

El primo pequeño está ahí para evitar el mismo código hash para los valores conmutados, 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 7

Cree un hash SHA-1 y luego enmascare los 64 bits más bajos.

Answer 8

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 conozco una función, pero esta es una idea que podría ayudar:

• Dedique 52 de los 64 bits para representar qué 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".

Luego puede usar los 12 bits restantes para codificar la longitud de la cuerda (o un valor de módulo) para reducir aún más las colisiones, o generar un código hash de 12 bits usando una función de hashing tradicional.

Suponiendo que su entrada sea solo de texto, me imagino que esto resultaría en muy pocas colisiones y sería de bajo costo computar (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 (ver 1 ).

Answer 9

long hash = string.hashCode();

Sí, los 32 bits superiores serán 0, pero probablemente se te acabarán los recursos de hardware antes de que te encuentres con problemas con las colisiones hash. El hashCode in String es bastante eficiente y bien probado.

Actualización Creo que lo anterior satisface lo más simple que podría funcionar , sin embargo, estoy de acuerdo con la idea de @sfussenegger de extender el Código hash String existente.

Además de tener un buen hashCode para su String, le recomendamos que revise 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);