Как сгенерировать хэш-код из массива байтов в C#?

Код hash объекта не обязательно должен быть уникальным.

Правило проверки:

• Равны ли коды hash? Затем вызовите полный (медленный) метод Equals .
• Разве коды hash не равны? Тогда эти два пункта определенно не равны.

Все, что вам нужно, - это алгоритм GetHashCode , который разбивает вашу коллекцию на примерно равные группы-он не должен формировать ключ, поскольку HashTable или Dictionary<> должны будут использовать hash для оптимизации поиска.

Как долго вы ожидаете получить эти данные? Насколько случайно? Если длины сильно различаются (скажем, для файлов), то просто верните длину. Если длины, вероятно, будут одинаковыми, посмотрите на подмножество байтов, которое изменяется.

GetHashCode должен быть намного быстрее , чем Equals, но не обязательно должен быть уникальным.

Две одинаковые вещи никогда не должны иметь разных кодов hash. Два разных объекта не должны иметь один и тот же код hash, но некоторые коллизии следует ожидать (в конце концов, существует больше перестановок, чем возможных 32-битных целых чисел).

Не используйте криптографические хэши для хэш-таблицы, это ridiculous/overkill.

А вот и ты... Модифицированный FNV Hash в 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;
        }
    }

Заимствуя из кода, сгенерированного программой JetBrains, я остановился на этой функции:

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

Проблема только с XOring байтами заключается в том, что 3/4 (3 байта) возвращаемого значения имеет только 2 возможных значения (all on или all off). Это распространяет биты вокруг немного больше.

Установка точки останова в равных условиях была хорошим предложением. Добавление около 200 000 записей моих данных в словарь, видит около 10 равных вызовов (или 1/20,000).

Вы сравнивали его с методом SHA1CryptoServiceProvider.ComputeHash ? Он принимает массив байтов и возвращает SHA1 hash, и я считаю, что он довольно хорошо оптимизирован. Я использовал его в обработчике Identicon, который довольно хорошо работал под нагрузкой.

Я нашел интересные результаты:

У меня есть класс:

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();          
    }
}

Затем я создал словарь с ключами типа MyHash, чтобы проверить, как быстро я могу вставить, а также узнать, сколько коллизий существует. Я сделал следующее

        // 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();

Каждый раз, когда я вставляю новый элемент в словарь, словарь вычисляет hash этого объекта. Таким образом, вы можете сказать, какой метод наиболее эффективен, поместив несколько ответов, найденных здесь, в методе public override int GetHashCode() метод, который был намного быстрее и имел наименьшее количество столкновений, был:

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

это заняло 2 секунды для выполнения. Метод

    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;
        }
    }

не было никаких столкновений также, но это заняло 7 секунд, чтобы выполнить!

Если вы ищете производительность, я протестировал несколько ключей hash, и Я рекомендую функцию Боба Дженкина hash . И то и другое безумно быстро вычислить и даст так же мало коллизий, как и криптографический hash вы использовали до сих пор.

Я вообще не знаю C#, и я не знаю, Может ли он быть связан с C, но вот его реализация в C году .

Не достаточно ли использовать существующий хэш-код из поля массива байтов? Также обратите внимание, что в методе Equals вы должны проверить, что массивы имеют одинаковый размер, Прежде чем делать сравнение.

Создание хорошего hash легче сказать, чем сделать. Помните, что вы в основном представляете n байт данных с m битами информации. Чем больше ваш набор данных и чем меньше m, тем больше вероятность того, что вы столкнетесь ... два фрагмента данных, разрешающих один и тот же hash.

Самый простой hash, который я когда-либо изучал, был просто XORing всех байтов вместе. Это просто, быстрее, чем большинство сложных алгоритмов hash и наполовину приличный универсальный алгоритм hash для небольших наборов данных. На самом деле это пузырьковый вид алгоритмов hash. Поскольку простая реализация оставила бы вам 8 бит, это всего лишь 256 хэшей ... не так уж и жарко. Вы могли бы использовать XOR блоков вместо отдельных байт, но тогда алгоритм становится намного сложнее.

Поэтому, конечно, криптографические алгоритмы, возможно, делают некоторые вещи, которые вам не нужны ... но они также являются огромным шагом вперед в качестве общего назначения hash. MD5 hash, который вы используете, имеет 128 бит, с миллиардами и миллиардами возможных хэшей. Единственный способ получить что-то лучшее-это взять несколько репрезентативных выборок данных, которые, как вы ожидаете, будут проходить через ваше приложение, и попробовать различные алгоритмы на нем, чтобы увидеть, сколько коллизий вы получите.

Так что пока я не вижу какой-то причины не использовать законсервированный алгоритм hash (производительность, возможно?), Я собираюсь рекомендовать вам придерживаться того, что у вас есть.

Независимо от того, хотите ли вы получить идеальную хэш-функцию (различное значение для каждого объекта, которое оценивается как равное) или просто довольно хорошую-это всегда компромисс производительности, обычно требуется время для вычисления хорошей хэш-функции, и если ваш набор данных невелик, вы лучше справитесь с быстрой функцией. Самое важное (как указывает ваш второй пост) - это правильность, и для достижения этого все, что вам нужно, - это вернуть длину массива. В зависимости от вашего набора данных это может быть даже хорошо. Если это не так (скажем, все ваши массивы одинаково длинны), вы можете пойти с чем-то дешевым, например, посмотреть на первое и последнее значение и XORing их значений, а затем добавить больше сложности, как вы считаете нужным для ваших данных.

Быстрый способ увидеть, как ваша хэш-функция работает с вашими данными, - это добавить все данные в хэш-таблицу и подсчитать количество раз, когда функция Equals вызывается, если это слишком часто, у вас есть больше работы над функцией. Если вы сделаете это, просто имейте в виду, что размер хэш-таблицы должен быть установлен больше, чем ваш набор данных, когда вы начинаете, иначе вы будете повторно хэшировать данные, которые вызовут повторные запросы и более равные оценки (хотя, возможно, более реалистичные?)

Для некоторых объектов (не этого) быстрый HashCode может быть сгенерирован ToString().GetHashCode(), конечно, не оптимальным, но полезным, поскольку люди склонны возвращать что-то близкое к идентичности объекта из ToString(), и это именно то, что ищет GetHashcode

Пустяки: худшая производительность, которую я когда-либо видел, была, когда кто-то по ошибке вернул константу из GetHashCode, хотя ее легко обнаружить с помощью отладчика, особенно если вы делаете много поисков в своей хэш-таблице

RuntimeHelpers.GetHashCode может помочь:

От Msdn:

Служит в качестве функции hash для a определенный тип, соответствующий для пользы внутри алгоритмы хеширования и структуры данных например, таблица hash.

private int? hashCode;

public override int GetHashCode()
{
    if (!hashCode.HasValue)
    {
        var hash = 0;
        for (var i = 0; i < bytes.Length; i++)
        {
            hash = (hash << 4) + bytes[i];
        }
        hashCode = hash;
    }
    return hashCode.Value;
}