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

Если вам нужна производительность, я протестировал несколько хеш-ключей и Рекомендую Хеш-функция Боба Дженкина. Это безумно быстро вычислить и даст столько же коллизий, сколько криптографический хеш, который вы использовали до сих пор.

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

Хэш-код объекта не обязательно должен быть уникальным.

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

• Равны ли хэш-коды? Затем вызовите полный (медленный) метод Equals.
• Не равны ли хэш-коды? Тогда эти два предмета точно не равны.

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

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

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

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

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

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

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

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

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

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

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

From Msdn:

Serves as a hash function for a particular type, suitable for use in hashing algorithms and data structures such as a hash table.

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

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

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

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

Заимствуя код, сгенерированный программой 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 возможных значения (все включено или все выключено). Это немного расширяет кругозор.

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

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

Вот и все ... Модифицированный хеш FNV на 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;
        }
    }

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

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

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

Каждый раз, когда я вставляю новый элемент в словарь, словарь будет вычислять хэш этого объекта. Таким образом, вы можете определить, какой метод наиболее эффективен, разместив несколько ответов, найденных здесь, в методе 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 секунд!

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