Построение хеш-функции для целочисленного массива

У меня есть массив int, я хочу создать для него хэш-функцию, чтобы два целочисленных массива с разными элементами приводили к одинаковым хеш-значениям для низкой вероятности, как лучше всего это сделать?

Длина массива может быть до 500, целое число может быть от 0 до 50.

Обратите внимание, что нет точной копии вопроса, так как природа целочисленного массива (длина и диапазон чисел) различна.

Я использую это раньше

public int GetHashCode(int[] data)

{
    if (data == null)
    return 0;

int result = 17;



foreach (var value in data)
{
    result += result * 23 + value;
}


return result;
}

но я обнаруживаю, что у него много столкновений.

Что я хочу решить, так это построить dictionary<int[], string>, чтобы когда целое число с одинаковыми значениями приводило к другому хэш-коду.


c# hash hashtable
person william007    schedule 26.02.2014    source источник
comment
что вы подразумеваете под ЛУЧШИМ? вообще без столкновений? маленькое использование оперативной памяти? НИЗКАЯ загрузка процессора? для низкого использования процессора / оперативной памяти суммируйте все элементы массива в длинном и надейтесь на лучшее. помните, что хеш-функция ВСЕГДА будет иметь некоторую коллизию, поэтому, если она говорит, что массив равен, вам придется проверить самостоятельно   -  person Lesto    schedule 26.02.2014
comment
@lesto Я знаю, что будет столкновение, я имею в виду уменьшить до минимума   -  person william007    schedule 26.02.2014
comment
Как разная длина и диапазон чисел делают его другим?   -  person Euphoric    schedule 26.02.2014
comment
@william007 so that two integer arrays with different elements do not result in the same hash values - невозможно, sum[n=0..50](500^n) намного превышает Int32.MaxValue   -  person decPL    schedule 26.02.2014
comment
@Euphoric, поскольку можно сделать хэш-код, который можно было бы оптимизировать для этого   -  person william007    schedule 26.02.2014
comment
Вопрос @decPL отредактирован   -  person william007    schedule 26.02.2014
comment
@ william007 Вы профилировали что-то, что нужно оптимизировать?   -  person Euphoric    schedule 26.02.2014
comment
@ william007 william007 увеличивая размер хеш-переменной (предлагаемое решение основано на int, я сказал использовать long long), затем протестируйте некоторую хэш-функцию, чтобы найти наилучшую для ваших нужд. см. partow.net/programming/hashfunctions/index.html   -  person Lesto    schedule 26.02.2014
comment
@lesto, но GetHashCode в C# возвращает int msdn.microsoft.com/en-us/library/   -  person william007    schedule 26.02.2014
comment
@ william007 Не могли бы вы поделиться некоторыми подробностями о ваших данных? Каков объем, сколько столкновений с использованием вашего подхода, можете ли вы оценить/описать распределение?   -  person decPL    schedule 26.02.2014
comment
@ william007: Почему именно связанный вопрос не является дубликатом? Вас действительно волнует вероятность столкновений? Сколько из этих массивов вы собираетесь хэшировать? Думали ли вы об использовании вместо этого контейнера с ключом? Какую проблему вы пытаетесь решить? Слишком много вопросов без ответов. Вы просите хэш, но не демонстрируете достаточных знаний по этому вопросу, поэтому я вовсе не уверен, что хеш — это правильное решение.   -  person Jon    schedule 26.02.2014
comment
@Jon, я добавил свою цель в последнее предложение   -  person william007    schedule 26.02.2014
comment
Это не дубликат, потому что этот вопрос касается идеального хэша для массива. Голосование за повторное открытие.   -  person Sergey Kalinichenko    schedule 27.02.2014
comment
Я не понимаю, где спрашивающий просит идеальный хеш, или даже как возможен идеальный хэш, учитывая количество степеней свободы вопроса.   -  person Dour High Arch    schedule 27.02.2014

Ответы (2)


arrow_upward
3
arrow_downward

два целочисленных массива с разными элементами не приводят к одинаковым хеш-значениям

Это невозможно для массивов с более чем одним элементом. Массив с N элементами имеет 32*N бита информации, вы не можете сопоставить его с 32 битами хэш-кода без потери некоторой информации, если только N=1.

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

Длина массива может быть до 500, целое число может быть от 0 до 50

Вам нужно примерно 2500 бит для представления такого массива; ваше хеш-значение имеет только 32 бита, поэтому у вас также будет много хеш-коллизий. Вы можете сделать идеальный хэш для массивов от нуля до пяти элементов со значениями 0..50, упаковав числа в int (используйте значение 51 для представления «отсутствующего значения», чтобы вы могли упаковать массивы разной длины). Как только вам нужно будет добавить шестое число к миксу, ваш хеш больше не будет идеальным.

person Sergey Kalinichenko    schedule 26.02.2014
comment
Спасибо, я знал эту информацию, просто я не уверен, как создать лучший хэш-код. - person william007; 26.02.2014
comment
@ william007 Хотя вы не можете сделать идеальный хэш, это не значит, что вы не можете сделать очень хороший. Например, ответ на предполагаемый дубликат (который на самом деле не является дубликатом) дает достаточно хороший и быстрый способ хеширования массива. - person Sergey Kalinichenko; 26.02.2014

arrow_upward
0
arrow_downward

500 значений от 0 до 50 означают, что вы можете сохранить сумму всех значений, умноженных на 50 и по положению (начиная с 0), также это можно обратить вспять для экстраполирования значений

просто проверьте длину размера, и это имеет место, и вы никогда не должны находить коллизии

person Lesto    schedule 26.02.2014
comment
Значения, умноженные на позицию, далеко не бесконфликтны: [0, 2, 1] и [0, 0, 2] дают один и тот же хэш. Значения, умноженные на 50 в N-й степени, не содержат коллизий, но 50^500... больше, чем long. - person Jon; 26.02.2014
comment
Если вы используете простую сумму, все массивы с одинаковыми числами в разном порядке будут давать один и тот же хэш-код. - person Sergey Kalinichenko; 26.02.2014
comment
Вы правы, я пропустил часть алгоритма, но все же возможно. Я обновлю свой ответ - person Lesto; 26.02.2014
comment
исправил мой ответ, но теперь я не уверен, что это может храниться долго или долго, нужно делать математику - person Lesto; 26.02.2014