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

Question

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

Вот что у меня сегодня:

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

Есть мысли?

---

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

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

С этим кодом, несмотря на то, что два байтовых массива имеют одинаковые значения внутри них, они ссылаются на разные части памяти и приведут (вероятно) к разным хеш-кодам. Мне нужно, чтобы хэш-коды для двух байтовых массивов с одинаковым содержимым были равны.

Answer 1

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

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

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

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

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

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

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

Answer 2

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

Вот, пожалуйста ... Модифицированный хэш 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;
        }
    }

Answer 3

Заимствуя код, сгенерированный программным обеспечением 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 вызовов «Равно» (или 1/20 000).

Answer 4

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

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

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 секунд!

Answer 5

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

Answer 6

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

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

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

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

Answer 7

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

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

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

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

Answer 8

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

Answer 9

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

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

Answer 10

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