Comment générer un hashcode à partir d'un tableau d'octets en C# ?

Question

Disons que j'ai un objet qui stocke un tableau d'octets et que je veux être capable de générer efficacement un code de hachage pour celui-ci. J'ai utilisé les fonctions de hachage cryptographiques pour cela dans le passé parce qu'elles sont faciles à mettre en œuvre, mais elles font beaucoup plus de travail qu'elles ne le devraient pour être cryptographiquement unidirectionnelles, et je ne me soucie pas de cela (j'utilise juste le hashcode comme une clé dans une table de hachage).

Voici ce que j'ai aujourd'hui :

struct SomeData : IEquatable<SomeData>
{
    private readonly byte[] data;
    public SomeData(byte[] data)
    {
        if (null == data || data.Length <= 0)
        {
            throw new ArgumentException("data");
        }
        this.data = new byte[data.Length];
        Array.Copy(data, this.data, data.Length);
    }

    public override bool Equals(object obj)
    {
        return obj is SomeData && Equals((SomeData)obj);
    }

    public bool Equals(SomeData other)
    {
        if (other.data.Length != data.Length)
        {
            return false;
        }
        for (int i = 0; i < data.Length; ++i)
        {
            if (data[i] != other.data[i])
            {
                return false;
            }
        }
        return true;
    }
    public override int GetHashCode()
    {
        return BitConverter.ToInt32(new MD5CryptoServiceProvider().ComputeHash(data), 0);
    }
}

Des idées ?

---

dp : Vous avez raison de dire que j'ai manqué une vérification dans Equals, je l'ai mise à jour. L'utilisation du hashcode existant du tableau d'octets résultera en une égalité de référence (ou du moins ce même concept traduit en hashcodes). par exemple :

byte[] b1 = new byte[] { 1 };
byte[] b2 = new byte[] { 1 };
int h1 = b1.GetHashCode();
int h2 = b2.GetHashCode();

Avec ce code, bien que les deux tableaux d'octets contiennent les mêmes valeurs, ils font référence à différentes parties de la mémoire et donneront lieu à des codes de hachage (probablement) différents. J'ai besoin que les codes de hachage de deux tableaux d'octets ayant le même contenu soient égaux.

Answer 1

Le code de hachage d'un objet n'a pas besoin d'être unique.

La règle de vérification est la suivante :

• Les codes de hachage sont-ils égaux ? Alors appelez la fonction complète (lente) Equals méthode.
• Les codes de hachage ne sont pas égaux ? Alors les deux éléments ne sont définitivement pas égaux.

Tout ce que vous voulez, c'est un GetHashCode qui divise votre collection en groupes à peu près égaux - il ne devrait pas former la clé comme le HashTable o Dictionary<> devra utiliser le hachage pour optimiser la recherche.

Quelle est la durée prévue des données ? A quel point sont-elles aléatoires ? Si les longueurs varient beaucoup (par exemple pour les fichiers), renvoyez simplement la longueur. Si les longueurs sont probablement similaires, regardez un sous-ensemble d'octets qui varie.

GetHashCode devrait être beaucoup plus rapide que Equals mais n'a pas besoin d'être unique.

Deux choses identiques ne doit jamais ont des codes de hachage différents. Deux objets différents ne devrait pas ont le même code de hachage, mais certaines collisions sont à prévoir (après tout, il y a plus de permutations que d'entiers 32 bits possibles).

Answer 2

N'utilisez pas de hachages cryptographiques pour une table de hachage, c'est ridicule/excessif.

Et voilà... Hash FNV modifié en C#

http://bretm.home.comcast.net/hash/6.html

    public static int ComputeHash(params byte[] data)
    {
        unchecked
        {
            const int p = 16777619;
            int hash = (int)2166136261;

            for (int i = 0; i < data.Length; i++)
                hash = (hash ^ data[i]) * p;

            hash += hash << 13;
            hash ^= hash >> 7;
            hash += hash << 3;
            hash ^= hash >> 17;
            hash += hash << 5;
            return hash;
        }
    }

Answer 3

En empruntant le code généré par le logiciel JetBrains, j'ai opté pour cette fonction :

    public override int GetHashCode()
    {
        unchecked
        {
            var result = 0;
            foreach (byte b in _key)
                result = (result*31) ^ b;
            return result;
        }
    }

Le problème avec le simple XOring des octets est que les 3/4 (3 octets) de la valeur retournée n'ont que 2 valeurs possibles (tout activé ou tout désactivé). Cela répartit les bits un peu plus.

La mise en place d'un point d'arrêt dans Equals était une bonne suggestion. L'ajout d'environ 200 000 entrées de mes données à un dictionnaire entraîne environ 10 appels à Equals (soit 1/20 000).

Answer 4

J'ai trouvé des résultats intéressants :

J'ai la classe :

public class MyHash : IEquatable<MyHash>
{        
    public byte[] Val { get; private set; }

    public MyHash(byte[] val)
    {
        Val = val;
    }

    /// <summary>
    /// Test if this Class is equal to another class
    /// </summary>
    /// <param name="other"></param>
    /// <returns></returns>
    public bool Equals(MyHash other)
    {
        if (other.Val.Length == this.Val.Length)
        {
            for (var i = 0; i < this.Val.Length; i++)
            {
                if (other.Val[i] != this.Val[i])
                {
                    return false;
                }
            }

            return true;
        }
        else
        {
            return false;
        }            
    }

    public override int GetHashCode()
    {            
        var str = Convert.ToBase64String(Val);
        return str.GetHashCode();          
    }
}

Ensuite, j'ai créé un dictionnaire avec des clés de type MyHash afin de tester la vitesse à laquelle je peux insérer et je peux aussi savoir combien de collisions il y a. J'ai fait ce qui suit

        // dictionary we use to check for collisions
        Dictionary<MyHash, bool> checkForDuplicatesDic = new Dictionary<MyHash, bool>();

        // used to generate random arrays
        Random rand = new Random();

        var now = DateTime.Now;

        for (var j = 0; j < 100; j++)
        {
            for (var i = 0; i < 5000; i++)
            {
                // create new array and populate it with random bytes
                byte[] randBytes = new byte[byte.MaxValue];
                rand.NextBytes(randBytes);

                MyHash h = new MyHash(randBytes);

                if (checkForDuplicatesDic.ContainsKey(h))
                {
                    Console.WriteLine("Duplicate");
                }
                else
                {
                    checkForDuplicatesDic[h] = true;
                }
            }
            Console.WriteLine(j);
            checkForDuplicatesDic.Clear(); // clear dictionary every 5000 iterations
        }

        var elapsed = DateTime.Now - now;

        Console.Read();

Chaque fois que j'insère un nouvel élément dans le dictionnaire, celui-ci calcule le hachage de cet objet. Vous pouvez donc savoir quelle méthode est la plus efficace en plaçant plusieurs réponses trouvées ici dans la méthode public override int GetHashCode() La méthode qui était de loin la plus rapide et qui présentait le moins de collisions était la suivante :

    public override int GetHashCode()
    {            
        var str = Convert.ToBase64String(Val);
        return str.GetHashCode();          
    }

qui a mis 2 secondes à s'exécuter. La méthode

    public override int GetHashCode()
    {
        // 7.1 seconds
        unchecked
        {
            const int p = 16777619;
            int hash = (int)2166136261;

            for (int i = 0; i < Val.Length; i++)
                hash = (hash ^ Val[i]) * p;

            hash += hash << 13;
            hash ^= hash >> 7;
            hash += hash << 3;
            hash ^= hash >> 17;
            hash += hash << 5;
            return hash;
        }
    }

n'a pas eu de collisions non plus mais a mis 7 secondes à s'exécuter !

Answer 5

Avez-vous comparé avec le SHA1CryptoServiceProvider.ComputeHash ? Elle prend un tableau d'octets et renvoie un hachage SHA1, et je crois qu'elle est assez bien optimisée. Je l'ai utilisée dans un Gestionnaire d'Identicon qui a bien fonctionné sous charge.