Решарпер делает так:

public override int GetHashCode()
{
   return _byteArrayValue.GetHashCode();
}

При этом стандартная реализация не обеспечивает идентичности по значению:

byte[] arr1 = new byte[] { 1, 2, 3 };
byte[] arr2 = new byte[] { 1, 2, 3 };

Console.WriteLine(arr1.GetHashCode()); // 21083178
Console.WriteLine(arr2.GetHashCode()); // 55530882

На SOF рекомендуют перебирать все элементы массива:

    public int GetHashCode(T[] array)
    {
        unchecked
        {
            if (array == null)
            {
                return 0;
            }
            int hash = 17;
            foreach (T element in array)
            {
                hash = hash * 31 + elementComparer.GetHashCode(element);
            }
            return hash;
        }
    }

Что не есть умно, так как массив может быть весьма длинным, а GetHashCode служит как раз для быстрой проверки на то что объекты не идентичны. Главное условие GetHashCode -- у одинаковых объектов оно всегда совпадает, а у разных объектов как правило не совпадает (но допуситмы коллизии, то есть может совпадать и у разных объектов).

По этому вычислять GetHashCode для массива путем вовлечения всех элементов -- глупо и бессмысленно. Согласны?

Т.к. GetHashCode возвращает int, то вовлечь достаточно 4 байта. Так же можно вовлечь длину массива (или 1 байт длины). Это будет и быстро и выполнять свои функции, то есть в большенстве случаев сработает. Согласны?

Здравствуйте, Shmj, Вы писали:

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

S>По этому вычислять GetHashCode для массива путем вовлечения всех элементов -- глупо и бессмысленно. Согласны?
В каком-то частном случае — не возражаю. В общем случае — не согласен. Общеупотребимы те способы вычисления хэша массива, которые при отличии даже в одном элементе, имеют тенденцию вычислять разное значение.

S>Т.к. GetHashCode возвращает int, то вовлечь достаточно 4 байта. Так же можно вовлечь длину массива (или 1 байт длины). Это будет и быстро и выполнять свои функции, то есть в большенстве случаев сработает. Согласны?
Могу согласиться лишь в том, что правильным подходом при выборе функции хэша в конкретном случае — является бенчмарк. Но т.к. я не видел бенчмарк для большинства случаев, лично мне сложно судить об этом большинстве.

ЗЫ. При увеличиении вероятности коллизии нелинейным образом возрастает необходимость выполнения сравнения, которое обычно дороже чем вычисление хэша.

Здравствуйте, samius, Вы писали:

S>В общем, верно. Но цель хэшфункции, как правило, как раз в минимизации коллизий.

Коллизий будет одинаково и при переборе всех элементов и при использовании только 4 байт.

S>В каком-то частном случае — не возражаю. В общем случае — не согласен. Общеупотребимы те способы вычисления хэша массива, которые при отличии даже в одном элементе, имеют тенденцию вычислять разное значение.

Это кто сказал?

Обычно разные массивы имеют разное начало или разный конец (в зависимости от направленности массива). По этому целесообразно взять 2 байта в начале 2 байта в конце.

Количество коллизий будет одинаково. Если вы задействуете все элементы, коллизии будут у даже не похожих массивов. Если только 4 байта -- коллизии будут у похожих массивов, у которых одинаковое начало и конец.

Кто сказал что одно лучше другого? Пусть уж лучше похожие массивы имеют одинаковый хеш-код.

S>ЗЫ. При увеличиении вероятности коллизии нелинейным образом возрастает необходимость выполнения сравнения, которое обычно дороже чем вычисление хэша.

А вот и нет. Операция сравнения работает пока не найдет разные элементы. То есть она редко перебирает все элементы массива. А вот неправильная операция вычисления хеш-кода перебирает элементы массива во всех случаях. По этому вместо ускорения получаем замедление.

Сорри, согласен. Но кто сказал что коллизий будет меньше, если вы переберете все элементы массива?

Здравствуйте, Shmj, Вы писали:

S>а GetHashCode служит как раз для быстрой проверки на то что объекты не идентичны.

Нет, GetHashCode служит для получения хэша. Это обычно нужно для типов, которые используются как ключи в хэш-таблице. Использование «для быстрой проверки на то что объекты не идентичны» — это злоупотребление. В некоторых случаях может использоваться в попытке оптимизации сравнения; например, когда хэш уже закеширован. Но в общем случае непосредственное сравнение вернёт результат быстрее (уже когда найдены первые несовпадающие поля; это относится не только к байтам в массиве), чем GetHashCode() который в любом случае перебирает все учитываемые им поля.

S>Т.к. GetHashCode возвращает int, то вовлечь достаточно 4 байта. Так же можно вовлечь длину массива (или 1 байт длины). Это будет и быстро и выполнять свои функции, то есть в большенстве случаев сработает. Согласны?

Допустим, у меня есть тип, в котором одно из полей массив байтов, возможно даже известного формата. Зачем мне для сравнения объектов этого типа использовать твой хитрый GetHashCode(), который учитывает размер, первый и два последних байта (причём учитывает их всегда), если я могу непосредственно в этом же порядке сравнить размер, первый и два последних байта массива, потом всё остальное? Непосредственное сравнение может сработать быстрее, выйти сразу же после несовпадения размеров. А GetHashCode() будет всегда читать ещё и три байта массива.

Здравствуйте, Shmj, Вы писали:

S>А вот и нет. Операция сравнения работает пока не найдет разные элементы. То есть она редко перебирает все элементы массива. А вот неправильная операция вычисления хеш-кода перебирает элементы массива во всех случаях. По этому вместо ускорения получаем замедление.

А ничего что сравнивать придется со всем содержимым бакета, пока совпадение не найдется, а не с единственным кандидатом?
Ну и сравнение это не единственная проблема коллизий. У ConcurrentDictionary, к примеру, коллизия приводит к использованию лока, в то время как без коллизий оно lock free.

Здравствуйте, Qbit86, Вы писали:

Q>Нет, GetHashCode служит для получения хэша. Это обычно нужно для типов, которые используются как ключи в хэш-таблице.

Я имел в виду что в хеш-таблице сначала ищется группа объектов по GetHashCode (предварительное сравнение на идентичность). При этом одному коду может соответствовать несколько объектов (коллизии). А потом уже для каждой коллизии производится точное сравнение методом Equals.

Я не предлагаю использовать GetHashCode вместо метода Equals.

Здравствуйте, AndrewVK, Вы писали:

S>>А вот и нет. Операция сравнения работает пока не найдет разные элементы. То есть она редко перебирает все элементы массива. А вот неправильная операция вычисления хеш-кода перебирает элементы массива во всех случаях. По этому вместо ускорения получаем замедление.

AVK>А ничего что сравнивать придется со всем содержимым бакета, пока совпадение не найдется, а не с единственным кандидатом?
AVK>Ну и сравнение это не единственная проблема коллизий. У ConcurrentDictionary, к примеру, коллизия приводит к использованию лока, в то время как без коллизий оно lock free.

Вопрос такой: кто сказал что при использовании всех элементов массива коллизий будет меньше, чем при использовании только 4 байт (берем 2 из начала и 2 из конца массива или лучше 0, 1/3, 2/3, последний байт)?

Здравствуйте, Shmj, Вы писали:

S>Вопрос такой: кто сказал что при использовании всех элементов массива коллизий будет меньше, чем при использовании только 4 байт

А кто сказал что их не будет меньше? Все зависит от конкретного содержимого и его статистических характеристик, универсального ответа нет. Поэтому функция получения хешкода и сделана заменяемой различными способами.

Здравствуйте, Shmj, Вы писали:

S>На SOF рекомендуют перебирать все элементы массива:

На SOF рекомендуют много всякой ерунды
На практике же перебор массива — слишком затратная операция чтобы при каждом обращении к GetHashCode ее выполнять. Хэши сложных объектов необходимо кэшировать, и использовать в реализации Equals.

S>Т.к. GetHashCode возвращает int, то вовлечь достаточно 4 байта. Так же можно вовлечь длину массива (или 1 байт длины). Это будет и быстро и выполнять свои функции, то есть в большенстве случаев сработает. Согласны?

У меня есть утиллитка для сборки хэшей, использование очевидно:

    public struct HashCode : IEquatable<HashCode>
    {
        public readonly int Value;

        public HashCode(int value)
        {
            Value = value;
        }

        public HashCode(string text, StringComparer comparer)
        {
            Value = (object)text != null ? comparer.GetHashCode(text) : 0;
        }

        public override string ToString() =>
            "HashCode: " + Value;

        public override int GetHashCode() =>
            Value;

        public override bool Equals(object other) =>
            other is HashCode && Equals((HashCode)other);

        public bool Equals(HashCode other) =>
            Value == other.Value;

        public static bool operator ==(HashCode a, HashCode b) =>
            a.Value == b.Value;

        public static bool operator !=(HashCode a, HashCode b) =>
            a.Value != b.Value;

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static implicit operator int(HashCode hashCode) =>
            hashCode.Value;

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public HashCode Add(int newValue) =>
            new HashCode(unchecked((Value << 5) + Value ^ newValue));

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public HashCode Add(bool flag) =>
            Add(flag ? 1 : -1);

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public HashCode Add<T>(T? obj)
            where T : struct =>
            obj.HasValue ? Add(obj.GetValueOrDefault().GetHashCode()) : this;

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public HashCode Add<T>(T obj)
            where T : class =>
            obj != null ? Add(obj.GetHashCode()) : this;

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public HashCode Add(string text, StringComparer comparer) =>
            (object)text != null ? Add(comparer.GetHashCode(text)) : this;

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public HashCode AddGeneric<T>(T obj) =>
            Add(EqualityComparer<T>.Default.GetHashCode(obj));

        public HashCode AddArray<T>(T[] arr)
        {
            if (arr == null) { return this; }

            var count = arr.Length;
            var hashCode = Add(count);
            if (count > 0) { hashCode = hashCode.AddGeneric(arr[0]); }
            if (count > 1) { hashCode = hashCode.AddGeneric(arr[count - 1]); }
            return hashCode;
        }
...

Под профайлером эта радость гонялась, проблем пока не видел.

Для byte[], вероятно стоит написать еще одну реализацию AddArray, которая возьмет длину и скомбинирует её с некоторыми значениями (например головой и хвостом) из массива.

Здравствуйте, Shmj, Вы писали:

S>Здравствуйте, samius, Вы писали:

S>>В общем, верно. Но цель хэшфункции, как правило, как раз в минимизации коллизий.

S>Коллизий будет одинаково и при переборе всех элементов и при использовании только 4 байт.
Только в теории, при равновероятном использовании всевозможных массивов (например, полученных полным перебором).

S>>В каком-то частном случае — не возражаю. В общем случае — не согласен. Общеупотребимы те способы вычисления хэша массива, которые при отличии даже в одном элементе, имеют тенденцию вычислять разное значение.

S>Это кто сказал?
Я. Полагаю, что вы придете к такому же заключению, просто погуглив.

S>Обычно разные массивы имеют разное начало или разный конец (в зависимости от направленности массива). По этому целесообразно взять 2 байта в начале 2 байта в конце.
В каких-то случаях целесообразно. А вот если взять дотнет строки, в которых лежит текст, то он уже совершенно не попадает в ваше понятие "обычного массива". Не говоря уж об xml.

S>Количество коллизий будет одинаково. Если вы задействуете все элементы, коллизии будут у даже не похожих массивов. Если только 4 байта -- коллизии будут у похожих массивов, у которых одинаковое начало и конец.
Мне не очевиден ваш критерий похожести массивов. И почему вы считате массивы double-ов {0, 1, 0} и {0, 0, 0} похожими?

S>Кто сказал что одно лучше другого? Пусть уж лучше похожие массивы имеют одинаковый хеш-код.
Я предлагаю не строить критерий похожести массивов на все случаи разом.

S>>ЗЫ. При увеличиении вероятности коллизии нелинейным образом возрастает необходимость выполнения сравнения, которое обычно дороже чем вычисление хэша.

S>А вот и нет. Операция сравнения работает пока не найдет разные элементы. То есть она редко перебирает все элементы массива. А вот неправильная операция вычисления хеш-кода перебирает элементы массива во всех случаях. По этому вместо ускорения получаем замедление.
Почему же неправильная? Она правильная, но не факт что оптимальная.

Что бы начать сравнивать два массива (даже если они отличаются по 3-му элементу, надо что бы в кэше оказались начала обоих массивов. На большом множестве коротких массивов вполне вероятно что сравнение с false результатом будет в 2 раза дольше вычисления хэша полной пробежкой чисто за счет промахов кэша.

S>Сорри, согласен. Но кто сказал что коллизий будет меньше, если вы переберете все элементы массива?
Давайте таки отталкиваться от конкретных задач, где в массивах лежат какие-то конкретные данные (строки, вектора, результаты двоичной сериализации, SQL запросы), а не сферокони. Для сфероконей — действительно не будет меньше.

Здравствуйте, Shmj, Вы писали:

S>Решарпер делает так:
S>При этом стандартная реализация не обеспечивает идентичности по значению.
Решарпер никогда не отличался аккуратностью советов, код за ним лучше перепроверять.


S>Что не есть умно, так как массив может быть весьма длинным, а GetHashCode служит как раз для быстрой проверки на то что объекты не идентичны.
Про "быструю проверку" Qbit86 уже выше написал, повторяться не буду.

Подвох в другом: hash-code по идее предназначен для неизменяемых (immutable) типов с value-семантикой, массив байт к ним явно не относится.
Я бы начал с факта "использовать массив в качестве ключа словаря — плохая идея" и дальше смотрел бы по обстоятельствам.


S>Т.к. GetHashCode возвращает int, то вовлечь достаточно 4 байта. Так же можно вовлечь длину массива (или 1 байт длины). Это будет и быстро и выполнять свои функции, то есть в большенстве случаев сработает. Согласны?
Зависит от характера данных. К примеру, если у тебя размер различается, неплохо бы включить в хэш длину массива. Если есть служебный заголовок / эпилог — лучше бы их пропустить ну и тыды.

Как уже намекнули, универсального решения нет. Вместо этого — IEqualityComparer<T>.

Здравствуйте, Shmj, Вы писали

Для byte[] есть криптография и HashAlgorithm . Например https://msdn.microsoft.com/ru-ru/library/system.security.cryptography.md5(v=vs.110).aspx

Правда они возвращают они возвращают массив byte. Для
ComputeHash Методы MD5 класса возвращает хэш-код в виде массива 16 байтов.
Но из них разными путями можно получить int

Ну про уникальность и скорость генерации можно посмотреть здесь http://stackoverflow.com/questions/16340/how-do-i-generate-a-hashcode-from-a-byte-array-in-c

Желательно, что бы скорость генерации Хэш кода была сопоставима с со скоростью сравнения массивов

Здравствуйте, Serginio1, Вы писали:

S> Для byte[] есть криптография и HashAlgorithm . Например https://msdn.microsoft.com/ru-ru/library/system.security.cryptography.md5(v=vs.110).aspx

Это еще дольше чем перебирать побайтово.

Здравствуйте, Shmj, Вы писали:

S>Здравствуйте, Serginio1, Вы писали:

S>> Для byte[] есть криптография и HashAlgorithm . Например https://msdn.microsoft.com/ru-ru/library/system.security.cryptography.md5(v=vs.110).aspx

S>Это еще дольше чем перебирать побайтово.

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

Здравствуйте, Shmj, Вы писали:

S>Главное условие GetHashCode -- у одинаковых объектов оно всегда совпадает
S>По этому вычислять GetHashCode для массива путем вовлечения всех элементов -- глупо и бессмысленно. Согласны?

Нет, это как раз и есть правильный метод. Нельзя сравнивать авто только по цвету кузова! Пока каждый элемент не будет пропарсен, вы не имеете никакого права говорить о совпадении.
Сравнение длин — это всего-лишь дополнительный трюк (которого в опр. условиях может хватить на 99% сравнений).

Здравствуйте, Shmj, Вы писали:

S>Решарпер делает так:

S>

S>public override int GetHashCode()
S>{
S>   return _byteArrayValue.GetHashCode();
S>}
S>

S>При этом стандартная реализация не обеспечивает идентичности по значению:

S>

S>byte[] arr1 = new byte[] { 1, 2, 3 };
S>byte[] arr2 = new byte[] { 1, 2, 3 };

S>Console.WriteLine(arr1.GetHashCode()); // 21083178
S>Console.WriteLine(arr2.GetHashCode()); // 55530882
S>

И правильно делает. Потому, что массив — не value-тип. Чтобы использовать его в словарях, надо сначала обеспечить иммутабельность.
А как только вы это сделаете (например, написав обёртку вокруг голого массива), то получите возможность сэкономить на сканированиях массивов благодаря предвычисленному хеш-коду.
Естественно, это даст выигрыш только в том случае, если массив участвует в более чем одном сравнении.