Qu'est-ce qu'une bonne fonction de hachage 64 bits en Java pour les chaînes de texte?

Question

Je cherche une fonction de hachage qui:

1. Hache bien les chaînes de texte (p. Ex. Quelques collisions)
2. Est écrit en Java et largement utilisé
3. Bonus: fonctionne sur plusieurs champs (au lieu de les concaténer et d'appliquer le hachage sur la chaîne concaténée)
4. Bonus: a une variante 128 bits.
5. Bonus: peu gourmand en ressources CPU.

Answer 1

Pourquoi n'utilisez-vous pas un long variante de la valeur par défaut String.hashCode() (où quelques très intelligent de gars certainement de faire des efforts dans ce qui la rend efficace - de ne pas mentionner les milliers de développeurs yeux que déjà regardé ce code)?

// 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 vous êtes à la recherche pour encore plus de bits, vous pourriez probablement utiliser un BigInteger Edit:

Comme je l'ai mentionné dans un commentaire à la réponse de @brianegge, il n'y a pas beaucoup usecases pour le hachage avec plus de 32 bits et probablement pas un seul pour le hachage avec plus de 64 bits:

Je ne pouvais imaginer une énorme table de hachage distribuée à travers des dizaines de serveurs, peut-être stocker des dizaines de milliards de mappages. Pour un tel scénario, @brianegge a encore un point valide ici: 32 bits permettent de 2^32 (ca. 4,3 milliards de dollars) de différentes clés de hachage. En supposant un algorithme fort, vous devriez avoir très peu de collisions. Avec 64 bits (18,446,744,073 milliards de clés différentes) votre certainement gagner, quel que soit le scénario dingue vous en avez besoin pour. La pensée de usecases pour les clés 128 bits (340,282,366,920,938,463,463,374,607,431 milliard de clés possibles) est à peu près impossible et pourtant.

Combiner le hachage de plusieurs champs, il suffit de faire un XOR multiplier l'un par un premier et d'ajouter:

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

Le petit premier est là pour éviter l'égalité de code de hachage pour la commutation de valeurs, c'est à dire {'foo','bar'} et {'bar','foo'} ne sont pas égaux et doivent avoir un autre code de hachage. XOR est mauvaise car elle renvoie 0 si les deux valeurs sont égales. Par conséquent, {'toto','toto'} et {'bar','bar'} aurait le même code de hachage.

Answer 2

Créez un hachage SHA-1 , puis masquez les 64 bits les plus bas.

Answer 3

long hash = string.hashCode();

Oui, le top 32 bits sera de 0, mais vous aurez probablement à court de ressources matérielles avant de vous lancer dans des problèmes avec des collisions de hachage. Le hashCode de la Chaîne est très efficace et bien testé.

Mise à jour Je pense que le ci-dessus répond à la chose la plus simple qui pourrait éventuellement fonctionner, cependant, je suis d'accord avec @sfussenegger idée de l'extension de la Chaîne existante hashCode.

En plus d'avoir une bonne hashCode pour votre Chaîne, vous pouvez envisager de ressasser le code de hachage de la mise en œuvre. Si votre espace de stockage est utilisé par d'autres développeurs, ou utilisées avec d'autres types, ce qui peut aider distribué vos clés. Par exemple, Java HashMap est basée sur la puissance de deux longueur des tables de hachage, il ajoute cette fonction pour assurer les bits de poids faible sont suffisamment diffusés.

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

Answer 4

Pourquoi ne pas utiliser un polynôme CRC64. Celles-ci sont raisonnablement efficaces et optimisées pour garantir que tous les bits sont comptés et répartis sur l'espace de résultat.

Il existe de nombreuses implémentations disponibles sur le net si vous google "CRC64 Java"

Answer 5

Faire quelque chose comme ceci:

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 vous permet d'écrire des primitives et des Cordes et avoir leur sortie comme des octets. L'enveloppant d'un ByteArrayOutputStream en il vous permettra d'écrire sur un tableau d'octets, qui s'intègre bien avec MessageDigest. Vous pouvez choisir n'importe quel algorithme énumérés ici.

Enfin BigInteger vous permettra de tourner les octets de sortie dans un format plus facile à utiliser ce numéro. Le MD5 et SHA1 algorithmes produisent de la 128 bits de tables de hachage, donc si vous avez besoin de 64 ans, vous pouvez simplement tronquée.

SHA1 devrait hachage presque tout bien, et avec de rares collisions (c'est de 128 bits). Cela fonctionne à partir de Java, mais je ne suis pas sûr de savoir comment il est mis en œuvre. Il peut effectivement être assez rapide. Il fonctionne sur plusieurs champs dans la mise en œuvre: il suffit d'appuyer sur tous sur l' DataOutputStream et vous êtes bon pour aller. Vous pouvez même le faire avec de la réflexion et des annotations (peut-être @HashComponent(order=1) pour afficher les champs d'aller dans une table de hachage, et dans quel ordre). Il a une 128-bit et je pense que vous trouverez qu'il n'utilise pas autant de CPU que vous pensez qu'il sera.

J'ai utilisé ce code pour obtenir des hachages pour de grands ensembles de données (par probablement des milliards d'objets) pour être en mesure d'éclat à travers de nombreux backend magasins. Il doit travailler pour ce que vous en avez besoin pour. Notez que je pense que vous pouvez seulement appeler MessageDigest.getInstance() une fois et ensuite, clone() à partir de là: SI le clonage est beaucoup plus rapide.