Comment puis-je calculer un bon code de hachage pour une liste de chaînes?

Je ne vois aucune raison de ne pas concaténer les chaînes et calculer le hashcode pour la concaténation.

par analogie, disons que je voulais calculer un checksum MD5 pour un bloc mémoire, Je ne voudrais pas diviser le bloc en plus petits morceaux et calculer des checksums MD5 individuels pour eux et puis les combiner avec une méthode ad hoc.

votre première option a le seul inconvénient de (String1, String2) produire le même hashcode de (String2, String1) . Si ce n'est pas un problème (par exemple. parce que vous avez un ordre de réparation) c'est bon.

Cat toute la chaîne ensemble puis obtenir le hashcode " semble le plus naturel et sûr pour moi.

Update : comme un commentaire le souligne, Cela présente l'inconvénient que la liste ("x"," yz") et ("xy"," z") donnerait le même hash. Pour éviter cela, vous pouvez joindre les chaînes avec un délimiteur de chaîne qui ne peut pas apparaître à l'intérieur des chaînes.

si les cordes sont grandes, Vous pouvez préférer hachez chacune, cat les hashcodes et ressasser le résultat. Plus de CPU, moins de mémoire.

une Autre façon qui apparaît dans ma tête, chaîne xors avec rotation de hachages basé sur l'index:

int shift = 0;
int result = 1;
for(String s : strings)
{
    result ^= (s.hashCode() << shift) | (s.hashCode() >> (32-shift)) & (1 << shift - 1);
    shift = (shift+1)%32;
}

edit: en lisant l'explication donnée dans Java efficace, je pense que le code de geoff serait beaucoup plus efficace.

une solution basée sur SQL pourrait être basée sur les fonctions checksum et checksum_agg. Si je le suis correctement, vous avez quelque chose comme:

MyTable
  MyTableId
  HashCode

MyChildTable
  MyTableId  (foreign key into MyTable)
  String

avec les différentes chaînes pour un article donné (MyTableId) stocké dans MyChildTable. Pour calculer et stocker un checksum reflétant ces chaînes (jamais-à-changer), quelque chose comme ceci devrait fonctionner:

UPDATE MyTable
 set HashCode = checksum_agg(checksum(string))
 from MyTable mt
  inner join MyChildTable ct
   on ct.MyTableId = mt.MyTableId
 where mt.MyTableId = @OnlyForThisOne

je crois que c'est indépendant de l'ordre, donc strings "the quick brown" produire la même somme que brun "Le rapide".

j'espère que ce n'est pas nécessaire, mais puisque vous ne mentionnez rien qui ressemble à ce que vous utilisez seulement les hashcodes pour un premier contrôle et ensuite vérifier que les chaînes sont réellement égales, je sens le besoin de vous prévenir:

hashCode égalité != égalité de valeur

il y aura beaucoup d'ensembles de chaînes qui donneront le hashcode identique, mais ne seront pas toujours égaux.

donc je comprends, vous avez effectivement un ensemble de chaînes que vous devez identifier par le code de hachage, et cet ensemble de chaînes que vous devez identifier parmi ne changera jamais?

si c'est le cas, cela n'a pas vraiment d'importance, à condition que le schéma que vous utilisez vous donne des nombres uniques pour les différentes chaînes/combinaisons de chaînes. Je commencerais par concaténer les cordes et calculer la corde.hashCode () et voir si vous finissez avec unique nombre. Si vous ne le faites pas, alors vous pouvez essayer:

• au lieu de concaténer les chaînes, concaténer les codes de hachage des chaînes de composants, et essayer différents multiplicateurs (par exemple si vous voulez identifier les combiantions de séquences à deux chaînes, essayez HC1 + 17 * HC2, si cela ne donne pas des nombres uniques, essayez HC1 + 31 * HC2, puis essayez 19, puis essayez 37 etc -- essentiellement n'importe quel petit nombre impair fera l'affaire).
• si vous n'obtenez pas des numéros uniques de cette façon-- ou si vous avez besoin de faire face à l'ensemble des possibilités d'expansion -- alors envisager un code de hachage plus fort. Un code de hash 64 bits est un bon compromis entre la facilité de comparaison et la probabilité de hash étant unique.

un schéma possible pour un code de hachage 64 bits est le suivant:

• générez un tableau de 256 nombres aléatoires 64 bits en utilisant un schéma assez fort (vous pourriez utiliser SecureRandom, bien que le XORShift système fonctionnent bien)
• ramasser "m", un autre "aléatoire" 64 bits, nombre impair, avec plus ou moins de la moitié de ses bits set
• pour générer un code de hachage, passez par chaque valeur de byte, b, formant la chaîne, et prenez le nombre bth de votre tableau de nombres aléatoires; puis XOR ou ajouter que avec la valeur de hachage actuelle, multiplié par" m "

donc une implémentation basée sur les valeurs suggérées dans les recettes numériques serait:

  private static final long[] byteTable;
  private static final long HSTART = 0xBB40E64DA205B064L;
  private static final long HMULT = 7664345821815920749L;

  static {
    byteTable = new long[256];
    long h = 0x544B2FBACAAF1684L;
    for (int i = 0; i < 256; i++) {
      for (int j = 0; j < 31; j++) {
        h = (h >>> 7) ^ h;
        h = (h << 11) ^ h;
        h = (h >>> 10) ^ h;
      }
      byteTable[i] = h;
    }
  }

ce qui précède initialise notre tableau de nombres aléatoires. Nous utilisons un générateur XORShift, mais nous pourrions vraiment utiliser n'importe quel générateur de nombres aléatoires de assez bonne qualité (créer un SecureRandom() avec une graine particulière puis appeler nextLong() serait très bien). Ensuite, pour générer un code de hachage:

  public static long hashCode(String cs) {
    if (cs == null) return 1L;
    long h = HSTART;
    final long hmult = HMULT;
    final long[] ht = byteTable;
    for (int i = cs.length()-1; i >= 0; i--) {
      char ch = cs.charAt(i);
      h = (h * hmult) ^ ht[ch & 0xff];
      h = (h * hmult) ^ ht[(ch >>> 8) & 0xff];
    }
    return h;
  }

un guide à considérer est que, étant donné un code de hachage de N bits, en moyenne, vous vous attendez à devoir générer des hachages de l'ordre de 2^(n/2) chaînes avant vous obtenez une collision. Autrement dit, avec un hash 64 bits, on s'attendrait à une collision après environ 4 milliards de cordes (donc, si vous avez affaire à, disons, à quelques millions de cordes, les chances d'une collision sont assez négligeables).

une autre option serait MD5, qui est un hash très fort (pratiquement sécurisé), mais il s'agit d'un hash 128 bits, donc vous avez le léger inconvénient d'avoir à traiter avec des valeurs 128 bits. Je dirais que le MD5 est exagéré à ces fins ... disons, avec un hash 64 bits, vous pouvez traiter assez en toute sécurité avec de l'ordre de quelques millions de cordes.

(Désolé, je dois clarifier -- MD5 a été conçu comme un hachage sécurisé, c'est juste que c'est depuis qu'il a été trouvé non sécurisé. Un hachage" sûr " en est un où, étant donné un hachage particulier, il n'est pas possible de construire délibérément des entrées qui mèneraient à ce hachage. Dans certaines circonstances, mais pas dans la vôtre, vous auriez besoin de cette propriété. Vous pourriez en avoir besoin, d'un autre côté, si les chaînes que vous avez affaire à un utilisateur d'entrée de données, un utilisateur malveillant pourrait essayer de confondre votre système. Vous pourriez aussi être interessé par ce que j'ai écrit dans le passé:

• guide des codes de hachage
• secure hash codes en Java (inclut certaines mesures de la performance)

utilisant le GetHashCode() n'est pas idéal pour combiner plusieurs valeurs. Le problème est que pour les chaînes, le hashcode est juste un checksum. Cela laisse peu d'entropie pour des valeurs similaires. par exemple l'ajout de hashcodes ("abc", "bbc") sera le même que ("abd", "abc"), provoquant une collision.

dans les cas où vous avez besoin d'être absolument sûr, vous utilisez un vrai algorithme de hachage, comme SHA1, MD5, etc. Le seul problème est qu'il s'agit de fonctions de bloc, ce qui est difficile à comparer rapidement les hachages pour l'égalité. Plutôt, essayez un CRC ou FNV1 hash. FNV1 32 bits est super simple:

public static class Fnv1 {
    public const uint OffsetBasis32 = 2166136261;
    public const uint FnvPrime32 = 16777619;

    public static int ComputeHash32(byte[] buffer) {
        uint hash = OffsetBasis32;

        foreach (byte b in buffer) {
            hash *= FnvPrime32;
            hash ^= b;
        }

        return (int)hash;
    }
}

vous pouvez utiliser la méthode suivante pour agréger les codes de hachage: http://docs.oracle.com/javase/7/docs/api/java/util/Objects.html#hash (java.lang.Objet...)

résolvez votre problème de racine.

N'utilisez pas de hashcode. Il suffit d'ajouter une clé primaire entière pour chaque chaîne