Генерация хэш-суммы для нескольких целых чисел

Question

Я сталкиваюсь с проблемой наличия нескольких целых чисел, и мне нужно сгенерировать их, используя их. Например.

Int 1: 14
Int 2: 4
Int 3: 8
Int 4: 4

Hash Sum: 43

У меня есть некоторые ограничения в значениях, максимальное значение, которое может иметь атрибут и - 30, сложение всех из них - всегда 30. И атрибуты всегда положительные.

Ключ в том, что я хочу сгенерировать ту же хеш-сумму для схожих целых чисел, например, если у меня есть целые числа 14, 4, 10, 2, тогда я хочу сгенерировать ту же хеш-сумму, в случае выше 43. Но, конечно, если целые числа очень разные (4, 4, 2, 20), тогда у меня должна быть другая хэш-сумма. Также это должно быть быстро.

В идеале мне бы хотелось, чтобы выходные данные хэш-суммы находились в диапазоне от 0 до 512, и они должны быть равномерно распределены. С моими ограничениями у меня может быть около 5K различных возможностей, так что я хотел бы иметь около 10 на ведро.

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

Дополнительная информация

С этим связано то, что эти целые числа являются атрибутами для функции. Я хочу сохранить значения функции в таблице, но у меня недостаточно памяти для хранения всех различных параметров. Вот почему я хочу обобщить сходные атрибуты.

Причина, по которой 10, 5, 15 полностью отличаются от 5, 10, 15, заключается в том, что если вы представляете это в 3d, то обе точки совершенно разные

Дополнительная информация 2

Некоторые ответы пытаются решить проблему с помощью хеширования. Но я не думаю, что это так сложно. Благодаря одному из комментариев я понял, что это проблема алгоритма кластеризации. Если у нас есть только 3 атрибута, и мы представляем проблему в 3d, мне просто нужно разделить пространство на блоки.

Фактически это можно решить с помощью правил такого типа

if (att[0] < 5 && att[1] < 5 && att[2] < 5 && att[3] < 5)
     Block = 21


if ( (5 < att[0] < 10) &&  (5 < att[1] < 10) &&  (5 < att[2] < 10) &&  (5 < att[3] < 10))
     Block = 45

Проблема в том, что мне нужен быстрый и общий способ генерации тех, если я не могу написать все возможности.

Answer 1

Простое решение:

Преобразование целых чисел в строки, разделенные запятыми, и хеширование полученной строки с использованием общего алгоритма хеширования (md5, sha и т. Д.).

Если вы действительно хотите покататься самостоятельно, я бы сделал что-то вроде:

• Генерация большого простого числа P
• Генерация случайных чисел 0

Чтобы сгенерировать хеш, рассчитайте: сумма (a [i] * x [i]) mod P

Answer 2

Учитывая входы a, b, c и d, каждый из которых находится в диапазоне значений от 0 до 30 (5 бит), следующее будет производить число в диапазоне от 0 до 255 (8 бит).

bucket = ((a & 0x18) << 3) | ((b & 0x18) << 1) | ((c & 0x18) >> 1) | ((d & 0x18) >> 3)

Уместен ли общий подход, зависит от того, как интерпретируется вопрос. 3 младших значащих бита отбрасываются, группируя 0-7 в одном наборе, 8-15 в следующем и т. Д.

0-7,0-7,0-7,0-7 -> bucket 0
0-7,0-7,0-7,8-15 -> bucket 1
0-7,0-7,0-7,16-23 -> bucket 2
...
24-30,24-30,24-30,24-30 -> bucket 255

Тривиально протестировано с:

for (int a = 0; a <= 30; a++)
    for (int b = 0; b <= 30; b++)
        for (int c = 0; c <= 30; c++)
            for (int d = 0; d <= 30; d++) {
                int bucket = ((a & 0x18) << 3) |
                             ((b & 0x18) << 1) |
                             ((c & 0x18) >> 1) |
                             ((d & 0x18) >> 3);
                printf("%d, %d, %d, %d -> %d\n",
                         a,  b,  c,  d,   bucket);
            }

Answer 3

Вам нужна хеш-функция, которая зависит от порядка входов и где аналогичные наборы чисел будут генерировать одинаковый хеш? То есть вы хотите, чтобы 50 5 5 10 и 5 5 10 50 генерировали разные значения, но вы хотите, чтобы 52 7 4 12 генерировали тот же хеш, что и 50 5 5 10? Простой способ сделать что-то вроде этого:

long hash = 13;
for (int i = 0; i < array.length; i++) {
    hash = hash * 37 + array[i] / 5;
}

Это несовершенно, но должно дать вам представление о том, как реализовать то, что вы хотите. Он будет обрабатывать значения 50 - 54 как одно и то же значение, но он будет обрабатывать значения 49 и 50 как разные значения.

Если вы хотите, чтобы хеш не зависел от порядка входных данных (чтобы хэши 5 10 20 и 20 10 5 были одинаковыми), то один из способов сделать это - отсортировать массив целых чисел в порядке возрастания до применяя хеш Другим способом было бы заменить

    hash = hash * 37 + array[i] / 5;

с

    hash += array[i] / 5;

РЕДАКТИРОВАТЬ: Принимая во внимание ваши комментарии в ответ на этот ответ, похоже, что моя попытка выше может служить вашим потребностям достаточно хорошо. Это не будет ни идеальным, ни идеальным. Если вам нужна высокая производительность, у вас есть некоторые исследования и эксперименты.

Подводя итог, порядок важен, поэтому 5 10 20 отличается от 20 10 5. Кроме того, в идеале вы должны хранить каждый «вектор» отдельно в вашей хэш-таблице, но для обработки ограничений по пространству вы хотите хранить некоторые группы значений в одна запись в таблице.

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

Answer 4

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

EDIT: Поскольку вы не описываете, почему вы не хотите запускать саму функцию, я предполагаю, что она долго работает. Так как вы не описали широту набора аргументов.

Если ожидается каждое значение, тогда полная таблица поиска в базе данных может быть быстрее.

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

Answer 5

Еще один способ решения моей проблемы - использование многомерного масштабирования (MS). В MS мы начинаем с матрицы элементов, и нам нужно назначить местоположение каждого элемента в N-мерном пространстве. Уменьшая таким образом количество измерений.

http://en.wikipedia.org/wiki/Multidimensional_scaling

Answer 6

Вы хотите посмотреть геометрическое хеширование . В «стандартном» хешировании хочется

1. короткая клавиша
2. обратное сопротивление
3. сопротивление столкновению

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

Answer 7

Генерирование одной и той же хэш-суммы называется столкновением, и хеш иметь плохо. Это делает его менее полезным.

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

int SqueezedSum( int a, int b, int c, int d )
{
    return (a/11) + (b/7) + (c/5) + (d/3);
}

Это не хеш, но делает то, что вы описываете.

Answer 8

Вам необходимо определить, что вы подразумеваете под «подобным». Хеши, как правило, предназначены для создания уникальных результатов из уникального ввода.

Один из подходов - нормализовать ввод и затем сгенерировать хеш из результатов.