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

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

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

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

Есть предположения?


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

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

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

19.08.2008 14:55:33
11 ОТВЕТОВ

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

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

1
27.06.2015 10:03:04

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

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

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

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

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

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

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

61
1.03.2017 10:51:00
+1 Это было одно из самых ясных объяснений, которые я когда-либо слышал, почему полезно переопределить Equals и GetHashcode.
Andrew Hare 4.05.2009 15:57:33

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

1
19.08.2008 15:19:32

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

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

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

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

1
19.08.2008 15:31:02

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

3
19.08.2008 15:53:28
SHA1 медленнее, чем MD5. Если вы не беспокоитесь о безопасности, используйте MD5.
Jonathan C Dickinson 22.01.2009 05:12:10
Спасибо Джон .. SHA1CryptoServiceProvider.ComputeHash метод работал для меня .. !!
Deepak 18.12.2012 11:15:55

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

От MSDN:

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

0
20.08.2008 02:32:20

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

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

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

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

1
1.08.2013 16:56:06

Заимствуя код, сгенерированный программным обеспечением 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).

12
8.01.2009 17:37:53
для IList<byte>определенно использовать цикл для на основе индексации, чем foreach. Может быть, это не большая разница, byte[]так как foreachбудет преобразован во forвнутреннюю.
nawfal 15.12.2013 05:08:30

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

А вот и я ... Модифицированный хэш 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;
        }
    }
49
22.01.2009 04:55:49
Это создаст довольно уникальные хэши, но на самом деле не будет хорошо работать GetHashCode. Идея состоит в том, что хеш позволяет коллекции иметь быстрый метод проверки, byte[]совпадают ли два, перед использованием более медленного Equals. В этой реализации вы зацикливаете весь массив, поэтому для очень больших массивов проверка на равенство может быть намного быстрее. Это хороший способ для вычисления хеша общего назначения, но для того, как .Net фактически использует GetHashCodeэто, может фактически замедлить коллекции.
Keith 17.05.2012 13:06:26
@tigrou - Я не говорю, что это не полезный механизм хеширования, но вы не должны использовать его для GetHashCodeреализации, потому что все хэшированные коллекции .Net предполагают, что GetHashCodeэто будет на несколько порядков быстрее, чем Equals. Фактически, если GetHashCodeпроверка пройдена, они продолжат звонить, Equalsпотому что ожидается некоторое количество столкновений. Если оба метода зацикливают всю коллекцию, вы получаете очень медленно HashTableили Dictionary.
Keith 21.08.2012 21:29:27
@Keith - вы не правы здесь. Ключевым моментом является то, что GetHashCode () должен вызываться только один раз, тогда как Equals () должен вызываться для каждого сравнения. Так что для вычисления хеша вполне нормально иметь более длительное время выполнения, чем у равных. Фактически, встроенное хеширование строк .NET делает именно это.
kaalus 7.09.2012 22:02:57
@Keith: каалус правильный. Хороший хэш-код должен включать информацию из всего объекта, который должен быть хеширован, включая все свойства и значения полей. Невозможно избежать сканирования этой информации за вызов, если рассматриваемый объект не является неизменным и не кэширует хеш-код при создании.
Frank Hileman 15.03.2013 19:36:19
Стоит отметить, что на связанной странице (здесь кешированная версия - archive.is/MnmRY ) фактически используется uintтак, что будет производить разные хэши.
sclarke81 1.09.2015 08:02:46

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

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

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

3
12.03.2014 20:40:25
Не могли бы вы объяснить свой алгоритм хеширования
nicolay.anykienko 23.01.2018 01:17:22
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;
}
0
28.08.2014 21:22:58